Пользовательский алгоритм слияния-сортировки не работает

Question

Я начал изучать структуры данных и алгоритмы. Я понимаю логику Merge-Sort и пыталась скопировать один из них самостоятельно без ссылок. Он генерирует ошибку ArrayIndexOutOfBounds. Я понимаю ошибку, но просто не мог ее заметить. Вот мой маленький код:

package merge.sort; 


public class MergeSort { 


//implementing the merge sort Alogrithm 

public int[] mergeSort (int [] numbers){ 
    //first step: break the array cosistently into sub-parts untill you arrive at base case. 


    if(numbers.length <= 1){ 
      return numbers; 



    } 

    else { 

     int [] output = new int[numbers.length]; 

     int[] firsthalf = new int[numbers.length/2]; 

     int[] secondhalf = new int[numbers.length/2]; 


    System.arraycopy(numbers, 0, firsthalf, 0, firsthalf.length); 

    System.arraycopy(numbers, firsthalf.length, secondhalf, 0, secondhalf.length); 



     System.out.println("\nSorted 1: "+mergeSort(secondhalf)[0]+"\n\n"); 
     System.out.println("Sorted 2:"+mergeSort(secondhalf)[0]+"\n\n"); 

     int i = 0; 
     int j = 0; 

     for (int k = 0; k < numbers.length; k++){ 
      if(mergeSort(firsthalf)[i] < mergeSort(secondhalf)[j]){ 
      output[k] = mergeSort(firsthalf)[i]; 
      i++; 
      } 

      else{ 
      output[k] = mergeSort(secondhalf)[j]; 
      j++; 
      } 

     } 

     return output; 

    } 

} 

public static void main(String[] args) { 
    MergeSort test = new MergeSort(); 

    int[] positions = {4,2,7,9}; 
    //int[] positions = {1}; 
    int[] sorted = test.mergeSort(positions); 

    System.out.print("The positions in sorted order:"); 
    for(int i =0; i<sorted.length; i++){ 
     if (i==sorted.length -1){ 
      System.out.print(sorted[i]+"."); 
     } 
     else{ 
      System.out.print(sorted[i]+","); 
     } 

    } 

} 

} 

Answer 1

Вам необходимо обработать случай, когда у вас есть нечетное число чисел. Таким образом, firsthalf.length должен быть числом.length/2 (который округляется вниз), а secondhalf.length должен быть остатком.

int[] firsthalf = new int[numbers.length/2]; 
int[] secondhalf = new int[numbers.length - firsthalf.length]; 

Например, если у вас есть 5 номеров, firsthalf.length будет 2 и secondhalf.length будет 3.

Кроме того, он является более эффективным, не вызывать на первойполовины слияния и второйполовине над и над еще раз. Просто назовите его один раз:

int[] sortedfirsthalf = mergeSort(firsthalf); 
int[] sortedsecondhalf = mergeSort(secondhalf); 

Затем обратитесь к этим массивам, а не к. слияние (первойполовины).

Наконец, при слиянии двух, если вы дойдете до конца одного массива, будьте осторожны, не индексировать мимо конца этого при выполнении дальнейших сравнений:

for (int k = 0; k < numbers.length; k++){ 
    if(i >= sortedfirsthalf.length) 
    { 
     output[k] = sortedsecondhalf[j]; 
     j++; 
    } 
    else if(j >= sortedsecondhalf.length) 
    { 
     output[k] = sortedfirsthalf[i]; 
     i++; 
    } 
    else if(sortedfirsthalf[i] < sortedsecondhalf[j]) 
    { 
     output[k] = sortedfirsthalf[i]; 
     i++; 
    } 
    else 
    { 
     output[k] = sortedsecondhalf[j]; 
     j++; 
    } 
} 

Смотрите, если вы можете оптимизировать его дальше ,