MergeSort - ArraysOutOfBoundsException

Question

Изучал алгоритмы сортировки через бесплатный онлайн-курс, где преподаватель использовал метод main(), чтобы показать, как печатать результаты.

Решил использовать JUnit-тест вместо основного метода.

Однако, я получаю следующее StackTrace:

java.lang.ArrayIndexOutOfBoundsException: 8 
    at MergeSort.sort(MergeSort.java:30) 
    at MergeSort.sort(MergeSort.java:14) 
    at MergeSort.sort(MergeSort.java:14) 
    at MergeSortTest.sort(MergeSortTest.java:14) 

MergeSort.java (фактическая реализация):

import java.util.Arrays; 

public class MergeSort { 

    public static String sort(int[] array, int[] tmpArray, int lowIndex, int highIndex) { 
     int midIndex =0; 
     int lowIndex1 = 0; 
     int lowIndex2 = 0; 
     int i = 0; 

     // Divide up sets using recursion 
     if (highIndex > lowIndex) { 
      midIndex = (highIndex + lowIndex)/2; 
      sort(array, tmpArray, lowIndex, midIndex); 
      sort(array, tmpArray, midIndex + 1, highIndex); 
     } 

     lowIndex1 = lowIndex; 
     lowIndex2 = midIndex+1; 

     System.arraycopy(array, 0, tmpArray, 0, array.length); 

     // Merge elements 
     while(lowIndex <= midIndex && lowIndex2 <= highIndex) { 
      if (tmpArray[lowIndex1] <= tmpArray[lowIndex2]) { 
       array[i] = tmpArray[lowIndex1]; 
       lowIndex1++; 
      } 
      else { 
       array[i] = tmpArray[lowIndex2]; 
      } 
      i++; 
     } 
     while (lowIndex1 <= midIndex) { 
      array[i] = tmpArray[lowIndex1]; 
      i++; 
      lowIndex1++; 
     } 
     while (lowIndex2 <= highIndex) { 
      array[i] = tmpArray[lowIndex2]; 
      i++; 
      lowIndex2++; 
     } 
     return Arrays.toString(array); 
    } 
} 

MergeSortTest.java:

import java.util.Arrays; 

import org.junit.Test; 

public class MergeSortTest { 

    int[] array = new int[] {6, 4, 10, 9, 3, 7, 2, 1}; 
    int[] sortedArray = new int[] {1, 2, 3, 4, 6, 7, 9, 10}; 
    int[] tmp = new int[array.length]; 

    @Test 
    public void sort() { 
     System.out.println("Unsorted array: " + Arrays.toString(array)); 
     String value = MergeSort.sort(array, tmp, 0, array.length - 1); 
     assert(value == Arrays.toString(sortedArray)); 
     System.out.println("Sorted array: " + value); 
    } 
} 

Что я, возможно, делать не так?

Answer 1

// Merge elements 
     while(lowIndex <= midIndex && lowIndex2 <= highIndex) { 
      if (tmpArray[lowIndex1] <= tmpArray[lowIndex2]) { 
       array[i] = tmpArray[lowIndex1]; 
       lowIndex1++; 
      } 
      else { 
       array[i] = tmpArray[lowIndex2]; 
      } 
      i++; 
     } 

должен быть

// Merge elements 
     while(lowIndex <= midIndex && lowIndex2 <= highIndex) { 
      if (tmpArray[lowIndex1] <= tmpArray[lowIndex2]) { 
       array[i] = tmpArray[lowIndex1]; 
       lowIndex1++; 
      } 
      else { 
       array[i] = tmpArray[lowIndex2]; 
       lowIndex2++; // add this one 
      } 
      i++; 
     } 

Answer 2

Я нашел четыре проблемы с реализацией слиянием сортировки.

Во-первых, условие в следующем while цикле неправилен:

// Merge elements 
    while(lowIndex <= midIndex && lowIndex2 <= highIndex) { 

Вы приращением lowIndex1 в петле, не lowIndex, так что цикл должен выглядеть следующим образом:

// Merge elements 
    while(lowIndex1 <= midIndex && lowIndex2 <= highIndex) { 

Во-вторых, как отметил @andy, вам необходимо увеличить lowIndex2 в предложении else в заявлении if в вашем while.

В-третьих, вы используете переменную i, чтобы отслеживать, где записать в array отсортированные значения из объединения двух отсортированных подразделов вашего массива. Ваш метод sort сортирует часть массива от lowIndex до highIndex включительно, так что вам нужно инициализирует i к lowIndex, не 0, чтобы убедиться, что ваш код записывает объединенные элементы в нужном месте и в array.

И, наконец, что должно произойти, если highIndex равно lowIndex? В этом случае вы сортируете одноэлементный раздел вашего массива. В его нынешнем виде ваш код оставит midIndex равным 0. Остальная часть вашего кода требует от lowIndex и highIndex, и если lowIndex больше 0, это будет больше недействительным. Конечно, вы можете сортировать 1-элементную коллекцию, ничего не делая, поэтому в этой ситуации можно пропустить слияние. Я рекомендовал бы добавить return заявление в else статье:

if (highIndex > lowIndex) { 
     midIndex = (highIndex + lowIndex)/2; 
     sort(array, tmpArray, lowIndex, midIndex); 
     sort(array, tmpArray, midIndex + 1, highIndex); 
    } else { 
     // Nothing to do, we only have one element to sort 
     return Arrays.toString(array); 
    } 

Я сделал эти четыре изменения в коде и обнаружили, что ваш JUnit тест пройден. Я также написал дополнительные тесты для других массивов и обнаружил, что они тоже прошли.