Quicksort: Was passiert nachdem das Pivotelement getauscht wird und die 2 Seiten geteilt wurden?

... komplette Frage anzeigen

4 Antworten

Quicksort funktioniert rekursiv. Das funktioniert so:

Wenn eine Folge nur ein Glied enthält, ist sie sortiert.

Wenn eine Folge mehrere Glieder enthält, wird bei Quicksort ein Pivotelement ausgesucht (dafür gibts verschiedene Vorgehensweisen, z.B. immer das letzte Element oder ein zufälliges etc.). Danach werden die Elemente, die kleiner als das Pivotelement sind und die, die größer sind entsprechend eingeordnet (so wie es bei dir oben geschehen ist). Dann weiß man:

Links vom Pivotelement sind nur kleinere Elemente und rechts davon nur größere. Jetzt wendet man Quicksort auf die linkte und die rechte Teilfolge an. Das macht man rekursiv immer weiter und muss dann die sortierten Teilfolgen nur zusammensetzen.

In deinem Fall wird jetzt also Quicksort auf die linke und rechte Teilfolge angewendet, dann werden die beiden (sortierten) Folgen mit dem Pivotelement in der Mitte "zusammengeklebt" und die Gesamtfolge ist sortiert.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von bishare
05.11.2015, 21:52

Ahh zu kompliziert... Bei meinem Beispiel würde er jetzt zuerst die 6 als Pivotelement setzen, aber da passiert nichts, weil keine kleinere Zahl gefunden wurde. Danach setzt er die 18 als Pivotelement: Er schaut sich die 6 (?) zuerst an danach die 44 und dann die 12 und wieder die 12. er tauscht 18 und 12 und dann macht er das gleiche mit der 18 

Würde es so funktionieren? Das Pivotelement wird nicht überprüft oder? (hab noch nie den code angeschaut) und macht er die linke und die rechte (94,55,67) gleichzeitig, also setzt er dann 2 Pivotelemente oder macht er es von links nach rechts .

0

Du solltest nicht über den Terminus „Pivotelement“ nachdenken, sondern darüber, dass du eine zufällige Zahlenfolge mit dem Quicksort-Algorithmus sortieren sollst. Ob man nun eine der Zahlen als Pivotelement oder Salatgurke bezeichnet, ist völlig unwichtig!

Wenn also diese Salatgurke ausgewählt wurde, werden alle Zahlen, die kleiner als die Salatgurke sind, in die Klein-Gruppe sortiert und alle größeren Zahlen in die Groß-Gruppe. Dann wird eine weitere Gurke in der Klein-Gruppe definiert und wieder sortiert bis die Klein-Gruppe sortiert ist. Danach wird die Groß-Gruppe sortiert!

https://de.wikipedia.org/wiki/Quicksort

Antwort bewerten Vielen Dank für Deine Bewertung

Danach sortierst Du 6 18 12 42 mit Quicksort. Und Du sortiest 94 55 67 mit Quicksort. Das Element 44 bleibt da, wo es ist. Weil alle Elemente links davon kleiner, die anderen aber größer sind.

Du machst so lang weiter, bis alle verbleibenden Folgen entweder 0 oder 1 Element haben.

Antwort bewerten Vielen Dank für Deine Bewertung