0
Ich versuche, eine Merge-Sort für statische Listen (ArrayLists) zu implementieren. Ich habe sowohl die TopDown als auch die BottomUp Implementierung. Ich glaube jedoch, dass die Zusammenfassung Merge Sort nicht funktioniert. Ich sage das, weil ich beide Implementierungen mit der gleichen ungeordneten Liste getestet habe, was zu der Annahme führte, dass die Merge-Methode die ist, die nicht funktioniert. Ich kann den Fehler nicht finden. Die privaten Methoden sind in verschiedenen Klassen. Ich lege sie zum leichteren Lesen hier zusammen. Hier ist der Code. Vielen Dank im Voraus.Merge Sort List Implementierung TopDown + BottomUp + Zusammenfassung MergeSort
public <T> void merge(@NotNull Comparator<T> comparator, @NotNull List<T> list, int lo, int mid, int hi) {
// // Merge a[lo..mid] with a[mid+1..hi].
List<T> aux = new ArrayList<>(list);// Copy a[lo..hi] to aux[lo..hi].
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) // Merge back to a[lo..hi].
if (i > mid)
list.set(k, aux.get(j++));
else if (j > hi)
list.set(k, aux.get(i++));
else if (comparator.compare(list.get(i), list.get(j)) > 0)
list.set(k, aux.get(j++));
else
list.set(k, aux.get(i++));
}
public <T> void sort(@NotNull Comparator<T> comparator, @NotNull List<T> list) {
sort(comparator, list, 0, list.size() - 1);
}
//TopDown
private <T> void sort(@NotNull Comparator<T> comparator, @NotNull List<T> list, int lo, int hi) { // Sort a[lo..hi].
if (hi <= lo) return;
int mid = lo + (hi - lo)/2;
sort(comparator, list, lo, mid); // Sort left half.
sort(comparator, list, mid+1, hi); // Sort right half.
merge(comparator, list, lo, mid, hi); // Merge results
}
//BottomUp
private <T> void sort(@NotNull Comparator<T> comparator, @NotNull List<T> list) {
for (int mid = 1; mid < list.size(); mid = mid + mid)
// mid: subarray size
for (int lo = 0; lo < list.size() - mid; lo += mid + mid) { // lo: subarray index
merge(comparator, list, lo, lo + mid - 1, Math.min(lo + mid + mid - 1, list.size() - 1));
}
}
Was ist abstrakte Zusammenführung Sortierung? – rcgldr
Ist die Methode "Zusammenführen" für beide Zusammenführungssortierer verwendet. –
Sowohl von oben nach unten als auch von unten nach oben können Sie die gleiche Zusammenführungsfunktion verwenden. Bottom-up-Aufruf muss auch prüfen, ob es nur eine Kopie der linken Hälfte gibt: merge (..., min (lo + mid -1, list.size() - 1), ...). Es wäre besser, eine einmalige Zuweisung von aux in der Sortierfunktion der obersten Ebene vorzunehmen und sie dann als einen Parameter an die Sortierung nach oben oder unten zu übergeben. Der aktuelle Code weist bei jeder Zusammenführungsoperation eine vollständige Kopie der Liste zu, die langsam ist und bei der eine große Liste nicht mehr ausreicht. – rcgldr