Quicksort Beispiel

[almig]

Hallo,

ich habe mal eine absolute Anfängerfrage:

Angenommen ich habe ein Array mit den Werten

5 4 3 2 1 0

Wie wende ich darauf den Quicksortalgorithmus an, so das danach die Werte aufsteigend sortiert sind?

[Klotzkopp]

Wie wende ich darauf den Quicksortalgorithmus an, so das danach die Werte aufsteigend sortiert sind?

So wie auf jedes andere Array auch. Sortieralgorithmen haben die Eigenschaft, mit jeder Art von Eingabedaten zu funktionieren.

Weißt du denn, wie Quicksort grundsätzlich funkioniert?

Hier findest du eine Animation und ein Beispiel für einen kompletten Sortierdurchlauf.

[almig]

Ja ich denke schon das ich Ihn begriffen habe....

Also z.Bsp.

5 4 3 2 1 0 mit Pivotelement = 3 wird dann zu

0 4 3 2 1 5

0 1 3 2 4 5

Aber wenn ich dann die beiden Teile 0 1 und 2 4 5 nochmal mit dem Algorithmus bearbeite, was dann?

Oder ist das in diesem Fall nicht nötig und es wird einfach noch die 2 auf die linke Seite von 3 genommen, so das sich dann die Folge 0 1 2 3 4 5 ergibt?

[Klotzkopp]

Aber wenn ich dann die beiden Teile 0 1 und 2 4 5 nochmal mit dem Algorithmus bearbeite, was dann?

Langsam, das sind nicht die Teillisten des ersten Durchgangs. Wenn das Pivotelement 3 ist, kann nicht 2 in der rechten Teilliste landen. Und wo ist überhaupt die 3 geblieben?

Das Pivotelement kannst du beim Teilen nur dann weglassen, wenn du es zwischen die Teillisten setzt. Das hast du aber nicht gemacht.

[almig]

mhm, so recht verstehe ich das nicht.

Könntest du evtl. den Quicksort des Arrays 5 4 3 2 1 0 kurz

runterschreiben? Dann würde ich es wahrscheinlich besser nachvollziehen können.

[Ezra]

Du teilst beim ersten Durchgang in die Partitionen:

0 1 2 | 3 4 5

(0 und 5, 1 und 4, 2 und 3 werden getauscht. Bei 2 und 3 überkreuzen sich die Zähler --> Partitionierung erfolgt also dort)

Jetzt ist es zwar schon sortiert (was an der Wahl des Pivots und der umgekehrten Ausgangssortierung liegt), aber es würde nun bspw mit der linken Partition und einem neuen Pivot (vermutlich 1, wenn Du als Pivot immer das mittlere Element nimmst) rekursiv fortgefahren und erneut in Partitionen aufgeteilt werden. Ist dieses vollständig abgearbeitet, folgt die rechte Partition mit dem Pivot 4 usw.

[almig]

Ok, und was ist wenn ich z.Bsp. als Pivotelement die 0 wähle?

Dann gehe ich so vor:

5 4 3 2 1 0

1 4 3 2 5 0

1 2 3 4 5 0

Danach werden alle Zahlen > 0 auf die rechte Seite von 0 gelegt.

Wäre das auch möglich?

[Klotzkopp]

Dann gehe ich so vor:

5 4 3 2 1 0

1 4 3 2 5 0

1 2 3 4 5 0

Ich weiß nicht, was du da machst, aber Quicksort ist es nicht. Wenn du die 0 als Pivotelement wählst, findet der linke Zähler die 5, und der rechte gar nichts, es wird also zunächst einmal nichts vertauscht. Dann wird das Pivotelement selbst an die richtige Stelle gepackt (sonst würde das nicht terminieren), d.h. die 5 und die 0 werden vertauscht. Damit ist die 0 an der richtigen Stelle, die linke Teilliste ist leer, und die rechte Teilliste ist 4 3 2 1 5.

[almig]

mhm ok und wie ist es damit:

[ 5 4 3 2 1 0 ]

Pivotelement ist 3.

Dann 5 und 0, 4 und 1 vertauschen und die 2 noch mit auf die linke Seite:

[ 0 1 2 ] 3 [ 4 5 ]

[ 0 1 2 3 4 5 ]

[Klotzkopp]

[ 5 4 3 2 1 0 ]

Pivotelement ist 3.

Dann 5 und 0, 4 und 1 vertauschen und die 2 noch mit auf die linke Seite:

"2 noch mit auf die linke Seite" kommt aber bei Quicksort nicht vor. Du kannst nicht einfach irgendwelche Schritte für Spezialfälle dazuerfinden, denn dann ist das kein Algorithmus mehr.

Entweder du bringst das Pivotelement an die richtige Stelle (d.h. 2 und 3 vertauschen), dann hast du [0 1 2] 3 [4 5], oder nicht, dann hast du [0 1 3 2] [4 5].

[Ezra]

Warum extrahierst Du eigentlich das Pivot, Klotzkopp?

Es funktioniert doch so: Alles was größergleich dem Pivot ist wird nach rechts getauscht. Alles was kleinergleich dem Pivot ist wird nach links getauscht. Man kann sich zwei Zeiger vorstellen - der eine läuft von links los und der andere von rechts. Sobald einer der beiden das Pivot trifft, tauscht er es also in jedem Fall rüber. Die Partitionsgrenzen liegen aber dort, wo sich die Zeiger überkreuzen. In diesem Beispiel ist das Pivot in der rechten Partition.

Eine Extrahierung erfolgt nur in dem Sonderfall, wenn beide Zeiger gleichzeitig auf dem Pivot landen würden, dieses mit sich selbst tauschen und dann eins weiter gesetzt werden. Dann steht das Pivot außerhalb der beiden sich bildenden Partitionen.

Oder gibt es da Quicksort-Variationen die das anders handhaben?

[Klotzkopp]

Die bei Wikipedia beschriebene Variante tauscht nur dann, wenn die Elemente echt größer bzw. echt kleiner sind als das Pivotelement.

Das spart Vertauschungen, es kann aber passieren, dass die Grenze ganz am Rand liegt. Dann würde der Algorithmus nicht terminieren. Das kann man verhindern, indem man das Pivotelement rausnimmt, und damit garantiert, dass die Teilmengen kleiner als die Usprungsmenge sind.

[almig]

Also dann wäre meine Lösung richtig?

Mit 2 rüber nehmen habe ich eigentlich gemeint das 2 und 3 vertauscht werden.

Und danach, nach den Tauschvorgängen, werden die 2 Teile wieder verbunden:

aus [ 0 1 2 ] 3 [ 4 5 ] wird [ 0 1 2 3 4 5 ].

Bearbeitet 5. Juli 2009 von almig

[Klotzkopp]

Also dann wäre meine Lösung richtig?

Naja, zumindest ist sie unvollständig. Quicksort erkennt nicht auf magische Weise, dass die verbliebenen Teillisten bereits sortiert sind, der Algorithmus läuft weiter bis zum bitteren Ende. Auch wenn nichts mehr vertauscht wird, es wird weiter geteilt, bis die Teillisten eine triviale Größe erreicht haben.

Und danach, nach den Tauschvorgängen, werden die 2 Teile wieder verbunden:

aus [ 0 1 2 ] 3 [ 4 5 ] wird [ 0 1 2 3 4 5 ].

Du brauchst nichts zu verbinden, weil nie etwas getrennt wurde. Quicksort arbeitet "in-place".

[almig]

Ok dann drücke ich es mal so aus:

wenn ich so vorgehen würde in einer Klausur

[ 5 4 3 2 1 0 ] Pivot = 3

[ 0 1 2 ] 3 [ 4 5 ]

[ 0 1 2 3 4 5 ]

natürlich noch mit der Angabe das 2 und 3 vertauscht werden und genauerer Beschreibung was mit was getauscht wird, würde das wohl die volle Punktzahl geben ?

[Klotzkopp]

würde das wohl die volle Punktzahl geben ?

Vermutlich nicht, weil du die Teillisten, die sich aus dem ersten Schritt ergeben, nicht sortiert hast.

[almig]

omg, ich werde an dem quicksort echt noch zugrunde gehen :upps

Kannst du mir einen Gefallen tun, und bitte mal den kompletten Algorithmus für das Array [ 5 4 3 2 1 0 ] runterschreiben.

Ich muss einfach mal die komplette richtige Lösung zum nachvollziehen sehen.

[Klotzkopp]

Du musst doch einfach nur denselben Algorithmus auf die gefundenen Teillisten [ 0 1 2 ] und [ 4 5 ] anwenden.

[almig]

Ja aber [ 0 1 2] und [ 4 5 ] ist doch schon in der richtigen Reihenfolge.

Ich glaube ich habe einen logischen Denkfehler drin....

[Klotzkopp]

Ja aber [ 0 1 2] und [ 4 5 ] ist doch schon in der richtigen Reihenfolge.

Na und?

In der Beschreibung von Quicksort steht nicht: "Prüfe, ob die Liste bereits sortiert ist, und falls ja, brich ab."

Der Algorithmus prüft das nicht, er macht weiter.

Ich sagte es doch schonmal:

Auch wenn nichts mehr vertauscht wird, es wird weiter geteilt, bis die Teillisten eine triviale Größe erreicht haben.

[almig]

Das heißt dann:

[ 5 4 3 2 1 0 ] Pivot = 3, 5 und 0, 4 und 1 und 3 und 2 vertauschen.

[ 0 1 2 ] 3 [4 5]

Dann Pivot = 1 und 4

[ 0 ] 1 [ 2 ] 3 [ 4 ] [ 5 ] so?

Dann wieder

[ 0 1 2 3 4 5 ]