Home > Mobile >  Need to get rid of big for this Iterative MergeSort Algo to work with input size that isn't jus
Need to get rid of big for this Iterative MergeSort Algo to work with input size that isn't jus

Time:11-21


public class ChangeStatic {
    static int [] arr = {4, 2, 7, 6, 3, 0, 5, 1};
    public static void main(String[] args) {

        System.out.println("Original: ");
        for (int i = 0; i < arr.length; i  ) {
            System.out.print(arr[i]   " ");
        }
        Iteration();
        System.out.println();
        System.out.println("Sorted: ");
        for (int i = 0; i < arr.length; i  ) {
            System.out.print(arr[i]   " ");
        }
    }

 
    public static void Iteration() {
     
        int n = arr.length;
    
        int [] dest = new int[n];
     

      

      //after each iteration: chunks are sorted : in last iteration two biggest chucks are sorted
      
        for (int size = 2; size <= n; size*=2) {
        
        //after each iteration : move onto next chunk
        for (int left = 0; left size-1 < n; left = left   size) {      
          Merge(arr, dest, left, size/2);
        }
        
        int[] temporary = dest;
        dest = arr;
        arr = temporary; 
    }
       
        
    }
    
    //dest is where the finished set goes :  merge from source -> dest ()() -> (  )
    //start = index where first subarray starts
    //len = size of 1st subarray
    //len = sometimes also size of 2nd subarray but sometimes not
    public static void Merge(int [] source, int [] destination, int start, int len) {
      int i = start;
      int j =  start   len ;
  
      int k = i;
        int end_of_first = i len-1;
        int end_of_2nd = (j len-1 <= arr.length)    ?  j len-1   :   j len-2   ;                                        
  
      
      while (i <= end_of_first && j <= end_of_2nd) {
        if(source[i] < source[j]) {
          destination[k  ] = source[i  ];
        }
        else {
        destination[k  ] = source[j  ];
        } 

      }
      for(;i<=end_of_first; i  ) {
        destination[k  ] = source[i];
      }
      for(;j <= end_of_2nd; j  ) {
        destination[k  ] = source[j];
      }
    
    
    
    }
}

I realize one of the possible bugs is the fact that when there isn't an even distribution (say like 9 elements would have the righter most element hanging alone), the last subarray won't have the same size as the left subarray? How to get rid of this problem? As you can see I tried my best by playing around with the Ternary Operator but I'm far from correct. Currently my code only works for power of 2 inputs which is relatively easier to understand as it's a divide by 2 algorithm.

Tried using the Ternary Operator in different ways (above is just one of my attempts) to avoid the index out of bounds exception but Im missing the correct logic.

CodePudding user response:

Minimizing changes to the code, this should work:

      int end_of_first = (i len <= arr.length) ?  i len : arr.length ;                                        
      int end_of_2nd = (j len <= arr.length) ?  j len : arr.length ;
      // ...
      while (i < end_of_first && j < end_of_2nd) {
      // ...
      for(; i <end_of_first; i  ) {
      // ...
      for(; j < end_of_2nd; j  ) {
      // ...
  • Related