Gibt es 2 verschiedene Ansätze für Quicksort?

[mittelding]

Hallo!

Momentan nerven mich Differenzen zwischen meinem Vorlesungsskript und dem, was man im Netz so findet. Thema ist Quicksort. Leider konnte ich, trotz Differenzen in der Ablauflogik, keine Fehler ausmachen.

Jetzt frage ich mich, ob ich gerade nur ein großes Brett vor dem Kopf habe, oder ob es sich einfach um zwei verschiedene Varianten handelt.

Angaben im Netz:


Man sucht sich ein Pivot-Element in der zu sortierenden Liste
Alle Elemente >= des Pivots landen rechts davon, alle Elemente <= landen links davon
Die Folge: das Pivot-Element ist jetzt bereits an der richtigen Stelle, man sortiert nun rekusriv die Teillisten links und rechts davon


Kurz: Pivot nach einem Durchgang bereits an richtiger Stelle, alles links davon ist kleiner, alles rechts davon größer (bzw. gleich). Das scheint die übliche Definition von Quicksort zu sein.

Schön und gut.

Nun zu meinem Skript. Dort wird nur gesagt, dass es am Ende eines Durchgangs 2 Listen gibt, in der linken ist alles <= des Pivots, in der rechten alles >= des Pivots.

Klingt identisch wie oben? Auf den ersten Blick schon. Ob das Pivot jetzt bereits an der richtigen Stelle steht nach Ende des Durchgangs, darüber wird keine Aussage gemacht. Dafür ist folgender Java-Algorithmus mitabgedruckt:


public static void quickSort(int left, int right) {
int pivot = a[(left + right)/2];
System.out.println("Pivot ist " + pivot);
int i = left, j = right;
// --- Partition ---
while (i <= j) {
while(a[i] < pivot) i++;
while(pivot < a[j]) j--;
if (i <= j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++; j--;
}
}


Wenn ich den Jetzt ausführe (oder alternativ auf dem Papier nachvollziehe), dann sind die Eigenschaften, die Im Netz genannt wurden, allerdings nicht erfüllt (obwohl am Ende alles sortiert ist).

Input: 5, 1, 2, 3, 4
Pivot sei 2.

Nach der gängigen Definition dürfte nach dem ersten Durchgang nur noch die 1 links neben der 2 stehen, rechts davon die 3, 4, 5. Was der Quicksort aus meinem Skript nach dem ersten Durchgang ausspuckt, ist aber folgendes:

2, 1, 5, 3, 4 (=> die 2 ist weder an ihrer endgültigen Stelle, noch ist die 1 links davon)

Das Skript widerspricht sich jedoch nicht, wenn man nun 2, 1 als linke und 5, 3, 4 als rechte Teilliste ansieht, so ist alles in der linken Liste <= als das Pivot und alles in der rechten >= als das Pivot. Nur dass das Pivot-Element jetzt nicht wirklich als Trenner zwischen den Listen zu erkennen ist, sondern es selbst irgendwo in einer der beiden Listen enthalten ist.

Liege ich richtig in der Annahme, dass das einfach nur eine andere Varante ist? Die Tatsache, dass es sich nicht mit den Eigenschaften deckt, die man überall lesen kann (Pivot am Ende eines Durchgangs an der richtigen Stelle) hat mich vorhin fast zur Verzweiflung getrieben.

Es scheint so, als würde in Variante 1 das Pivot wirklich ein physikalischer Trenner der beiden Teillisten sein, während bei der Variante aus meinem Skript der Pivot eher ein imaginärer Trenner ist (er ist später ja selbst wieder in den Teillisten enthalten).

Danke

[Marscel]

Die ursprüngliche Idee war meiner Ansicht nach, nach dem Durchlauf das Pivot an die richtige Stelle zu tauschen und echt links und rechts davon weiterzumachen.

Ohne Gewähr, aber wenn ich das so grob im Kopf überschlage, wird die Sortierung davon nicht beeinflusst, solange du Paritionen korrekt bestimmst und sich ein vorheriges Pivotelement dann evtl. durch ein anderes einsortiert.

[Trap]

Eigentlich hast du dir die Frage doch schon selbst beantwortet: Es gibt verschiedene Ansätze.

Wenn das Pivot in einer der 2 Mengen enthalten ist, ist egal an welcher Stelle es steht (das ist eine praktische Eigenschaft vom Pivot). Wenn es nicht in den Mengen enthalten ist, muss der nicht-rekursive Teil vom Code das Pivot-Element an die richtige Stelle setzen. Wann und wie das passiert, ist ziemlich egal solang es lineare Zeitkomplexität hat.

"Quicksort"-igkeit als Eigenschaft von Programmen ist aber keine besonders hilfreiche Idee. Erstens ist diese Eigenschaft nicht klar genug definiert um sie tatsächlich formell überprüfen zu können. Aber selbst wenn man es exakt definieren würde, wäre man damit nicht weiter, da es eine nicht-triviale Eigenschaft im Sinne des Satz von Rice wäre und damit im Allgemeinen eine unentscheidbare Fragestellung.

Man kann ja ausgehend von einer beliebigen Quicksort Implementierung beliebig viele weitere Programme mit gleicher Semantik (sie sortieren) und gleichem asymptotischen Laufzeitverhalten erzeugen. Einfach irgendwelche sich kompensierenden Operationen passender Zeitkomplexität hinzufügen (ganz anschaulich für den Anfang: reverse und rotate). Da irgendeine Grenze festzulegen was noch Quicksort ist und was grade nicht mehr, ist weder irgendwie nützlich noch praktisch machbar.

[Ectoplasma]

Im Grunde hat Trap schon Recht. Da sich bei obiger Implementierung das Laufzeitverhalten nicht ändert (Worst Case: O(n^2) Best Case: O(n * log(n)) und die Partitionierung stimmt, sollte obige Implementierung ein gültiger Quicksort sein.

Im Detail kann eine Implementierung immer leicht von der allgemein gültigen Definition abweichen. Das wirst du auch später immer wieder feststellen.