MergeSort - ArraysOutOfBoundsException

Question

Untersuchung von Sortieralgorithmen über einen kostenlosen Online-Kurs, bei dem der Kursleiter die Methode main() verwendete, um zu zeigen, wie die Ergebnisse gedruckt werden.

Entschieden, einen JUnit-Test anstelle einer Hauptmethode zu verwenden.

Allerdings erhalte ich die folgende 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 (tatsächliche Umsetzung):

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); 
    } 
} 

Was bin ich vielleicht falsch machen?

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++; 
     } 

sollte

sein

// 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

ich vier Probleme mit Ihrem merge-sort Umsetzung gefunden.

Zuerst wird die Bedingung in der folgenden while Schleife ist falsch:

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

Du lowIndex1 innerhalb der Schleife erhöht wird, nicht lowIndex, so dass die Schleife wie folgt aussehen sollte:

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

Zweitens, wie von @andy hervorgehoben, müssen Sie lowIndex2 in der else Klausel der if Anweisung in IhreminkrementierenSchleife.

Drittens verwenden Sie die Variable i, um zu verfolgen, wo Sie die sortierten Werte aus dem Zusammenführen der zwei sortierten Unterabschnitte Ihres Arrays in array zurückschreiben können. Ihre sort Methode sortiert den Abschnitt des Arrays von lowIndex bis highIndex einschließlich, so dass Sie i zu lowIndex, nicht initialisieren müssen, um sicherzustellen, dass Ihr Code die fusionierten Elemente an der richtigen Stelle in array schreibt.

Schließlich, was passiert, wenn highIndex gleich lowIndex ist? In diesem Fall sortieren Sie einen Einzelelementabschnitt Ihres Arrays. So wie es steht, wird Ihr Code midIndex auf 0 gesetzt lassen. Der Rest Ihres Codes benötigt midIndex zwischen lowIndex und highIndex, und wenn lowIndex größer als 0 ist, wird dies nicht mehr wahr sein. Natürlich können Sie eine 1-Element-Sammlung sortieren, indem Sie nichts tun. In dieser Situation ist es also in Ordnung, die Zusammenführung zu überspringen. Ich würde empfehlen, eine return-Anweisung in einer else Klausel hinzu:

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); 
    } 

Ich habe diese vier Änderungen an Ihren Code und festgestellt, dass Ihr JUnit-Test bestanden. Ich habe auch zusätzliche Tests für andere Arrays geschrieben und festgestellt, dass diese auch bestanden haben.