Quicksort "Code" erklären?
Hi Leute, ich habe ein Problem mit Quicksort code und zwar ich verstehe wie das irl gemacht wird aber für mich ist der Code schwer zu verstehen. Kann mir bitte jemand diesen Code erklären?
public class QuicksortSimple {
public void sort(int[] elements) {
quicksort(elements, 0, elements.length - 1);
}
private void quicksort(int[] elements, int left, int right) {
// End of recursion reached?
if (left >= right) return;
int pivotPos = partition(elements, left, right);
quicksort(elements, left, pivotPos - 1);
quicksort(elements, pivotPos + 1, right);
}
public int partition(int[] elements, int left, int right) {
int pivot = elements[right];
int i = left;
int j = right - 1;
while (i < j) {
// Find the first element >= pivot
while (elements[i] < pivot) {
i++;
}
// Find the last element < pivot
while (j > left && elements[j] >= pivot) {
j--;
}
// If the greater element is left of the lesser element, switch them
if (i < j) {
ArrayUtils.swap(elements, i, j);
i++;
j--;
}
}
// i == j means we haven't checked this index yet.
// Move i right if necessary so that i marks the start of the right array.
if (i == j && elements[i] < pivot) {
i++;
}
// Move pivot element to its final position
if (elements[i] != pivot) {
ArrayUtils.swap(elements, i, right);
}
return i;
}
}
Bitte den Code anständig formatieren (nutz die Funktion für Quellcode), damit er lesbarer wird.
Ich habe es eingefügt :)
2 Antworten
Hallo,
das ist einfach noch sehr unleserlich, daher wird in der Informatik der leicht verständliche Preudocode verwendet.
Quicksort ist ein rekursiver Algorithmus, das heisst er ruft sich selbst immer wieder auf, bis ein Array von n Elementen vollständig sortiert vorliegt. Das ist der Fall wenn links vom untersuchten Element kein größeres und rechts davon kein kleineres mehr vorhanden ist. Gestartet wird die Suche etwa in der Mitte der Elemente.
Zunächst die rekursive Prozedur. Man beachte den Selbstaufruf in dieser!
funktion quicksort(links, rechts)
falls links < rechts dann
teiler := teile(links, rechts)
quicksort(links, teiler - 1)
quicksort(teiler + 1, rechts)
ende
ende
Die folgende Implementierung der Funktion
teile
teilt das Feld so, dass sich das Pivotelement an seiner endgültigen Position befindet und alle kleineren Elemente davor stehen, während alle größeren danach kommen:
funktion teile(links, rechts)
i := links
// Starte mit j links vom Pivotelement
j := rechts - 1
pivot := daten[rechts]
wiederhole solange i < j // solange i an j nicht vorbeigelaufen ist
// Suche von links ein Element, welches größer oder gleich dem Pivotelement ist
wiederhole solange i < rechts und daten[i] < pivot
i := i + 1
ende
// Suche von rechts ein Element, welches kleiner als das Pivotelement ist
wiederhole solange j > links und daten[j] >= pivot
j := j - 1
ende
falls i < j dann
tausche daten[i] mit daten[j]
ende
ende
// Tausche Pivotelement (daten[rechts]) mit neuer endgültiger Position (daten[i])
// und gib die neue Position des Pivotelements zurück, beende Durchlauf
falls daten[i] > pivot dann
tausche daten[i] mit daten[rechts]
ende
antworte i
ende
Quelle des Pseudocodebeispiels: Wikipedia
lg
Harry
Da wird's erklärt.