Hier ist meine Code-Implementierung für QuickSort-Algorithmus; Es funktioniert jedoch nicht für sortierte Arrays. Was könnte das Problem sein?QuickSort für sortiertes Array
public void insertionSort(ArrayList<String> data, int firstIndex,
int numberToSort) {
if (firstIndex + numberToSort > data.size())
System.out.println("Index is larger then the date size");
else {
for (int i = 1; i < numberToSort; i++) {
for (int j = 0; j < i; j++) {
if (data.get(firstIndex + j).compareTo(
data.get(firstIndex + i)) > 0)
Collections.swap(data, firstIndex + i, firstIndex + j);
}
}
}
}
@Override
public void quickSort(ArrayList<String> data, int firstIndex,
int numberToSort) {
if (firstIndex + numberToSort > data.size())
System.out.println("Index is larger then the date size");
else {
if (numberToSort <= 16)
insertionSort(data, firstIndex, numberToSort);
else {
int idx = partition(data, firstIndex, numberToSort);
int leftSeg = idx - firstIndex;
int rightSeg = numberToSort - leftSeg - 1;
quickSort(data, firstIndex, leftSeg);
quickSort(data, idx + 1, rightSeg); // This is where I get an error
}
}
}
@Override
public int partition(ArrayList<String> data, int firstIndex,
int numberToPartition) {
String pivot = data.get(firstIndex);
int TooBigNdx = firstIndex + 1;
int TooSmallNdx = firstIndex + numberToPartition - 1;
while (TooBigNdx < TooSmallNdx) {
while (TooBigNdx < TooSmallNdx
&& data.get(TooBigNdx).compareTo(pivot) <= 0)
TooBigNdx++;
while (TooSmallNdx > firstIndex
&& data.get(TooSmallNdx).compareTo(pivot) > 0)
TooSmallNdx--;
if (TooBigNdx < TooSmallNdx)
Collections.swap(data, TooBigNdx, TooSmallNdx);
}
if (pivot.compareTo(data.get(TooSmallNdx)) >= 0) {
Collections.swap(data, firstIndex, TooSmallNdx);
return TooSmallNdx;
}
return firstIndex;
}
Jedes Mal, wenn ich laufe, passiere ich unsortierte Array, es funktioniert gut. Doch mein Tester gibt mir einen AssertionError. Jede Hilfe wäre willkommen.
Es wäre sehr hilfreich, wenn Sie den tatsächlichen Fehler teilen könnten, den Sie sehen. Bitte besuchen Sie die [Hilfe] und lesen [fragen]. –