Quicksort Algorithmus, Hilfe?
Irgendwie machen das alle anders. An meiner Uni wird das so gemacht:
Ich verstehe das nicht. Wenn die Zeiger übereinander laufen, dann kommt bei mir eine andere Zahlenfolge raus, als auf dem Bild. Außerdem weiß ich nicht, wie das Pivot in der Mitte platziert wurde.
Kann mir jemand bitte Schritt für Schritt erklären, wie hier gearbeitet wurde? Ich wäre so dankbar.
3 Antworten
Quicksort funktioniert ja in etwa so:
quicksort(E):
wenn |E| <= 1
return E
wähle Pivot-Element k aus E
füge alle Einträge aus E <= k zu L hinzu
füge alle Einträge aus E >= k zu R hinzu
return quicksort(L) + k + quicksort(R)
Bei dem Beispiel wurde im ersten Schritt das letzte Element als Pivot-Element gewählt. Also ist k1 = 3.
Jetzt kommen alle Elemente kleiner gleich 3 in die neue linke Liste L1 = (-3, 2, -6, 1), und alle Elemente größer gleich 3 in die neue rechte Liste R1= (8, 5, 9, 6).
Bearbeiten wir zuerst die linke Seite:
Wir wenden Quicksort auf (-3, 2, -6, 1) an und wählen k2 = 1 als Pivot. Daraus ergibt sich L2 = (-3, -6), R2 = (2).
Dann wenden wir wieder Quicksort auf L2 und R2 an. Für L3 ergibt sich: k3 = -6, L3 = leere Liste, R3 = -2.
Jetzt wenden wir wieder Quicksort auf L3 und R3 an. Beide Listen haben höchstens ein Element, d.h. wir sind fertig und setzen unsere Teilergebnisse zusammen:
(-6) + (-3) = (-6,-3),
eine Stufe darüber:
(-6,-3) + (1) + (2) = (-6, -3, 1, 2).
Jetzt sind wir wieder auf der höchsten Stufe, haben L1 fertig sortiert und bearbeiten als nächstes die rechte Teilliste R1 auf die selbe Weise. Am Ende wird die sortierte Liste dann zusammengesetzt:
(-6, -3, 1, 2) + (3) + (5, 6, 8, 9) = (-6, -3, 1, 2, 3, 5, 6, 8, 9)
Es scheint so als nehme man bei diesem Beispiel bei jedem Schritt stets das letzte Element der Liste als Pivot.
Wenn keine Informationen über die Daten vorliegen ist es jedoch ratsam das Pivotelement gleichverteilt zufällig zu wählen, um die Chance auf eine Worst-Case Laufzeit zu minimieren.
Das Schaubild passt nicht os recht zur Beschreibung. Der erste Swap sollte laut Beschreibugn des Algorithmus zwischen 1 und 9 stattfinden, sodaß die 1 sich auf der linkesten Position der linken Teilliste befinden müßte.
Um n log n zu erhalten sollte man das Pivotelemt aus 3 Elementen auswaehlen
verstehe das richtig , dass das erste Pivot Element zufällig ist ? Bzw das letzte gelesene ?