Quicksort mit rechtem Pivot

12.09.2014, 14:33	Auf diesen Beitrag antworten »
Haevelin	Quicksort mit rechtem Pivot Für einen Quicksort habe ich ausgehend von dem rechten Element als Pivot das Pivot vertauscht. Also etwa 2 4 3 7 1 8 5 mit rechtem Pivot 5 so habe ich 5 und 7 vertauscht und dann folgendes Resultat: 2 4 3 5 1 \| 8 7 Jetzt weiter so: 1 \| 4 3 5 2 \| 7 8 1 \| 2 \| 3 5 4 \| 7 8 1 \| 2 \| 3 \| 4 5 \| 7 8 Kann man so vorgehen?


12.09.2014, 23:14	Auf diesen Beitrag antworten »
as_string	Nein, das ist kein Quicksort! Du nimmst 5 als Pivot. Jetzt suchst Du so lange von links, bis Du eine Zahl findest, die größer (oder größer gleich, je nachdem...) als das Pivot 5 ist. Das ist die 7. Du tauschst jetzt aber nicht das Pivot mit dieser 7! Sondern Du suchst jetzt von rechts (also eins links von der 5) nach links nach einer Zahl, die kleiner als 5 ist, das ist die 1. Jetzt vertauschst Du die 7 und die 1. Normalerweise würdest Du jetzt von links weiter suchen, bis Du da wieder eine größer 5 und dann rechts wieder eine kleiner 5 findest. Da 7 und 1 schon benachbart waren, bist Du aber schon fertig. Du hast jetzt zwei Teillisten mit Zahlen, die kleiner sind als 5, dann welche die größer sind und dann die 5: 2 4 3 1 \| 7 8 und das Pivot 5, also nur 7 und 1 vertauscht. Jetzt musst die 5 zwischen diese beiden Unterlisten. Da beide Unterlisten so wie so noch nicht sortiert sind, kannst Du einfach die erste Zahl von der rechten Liste nehmen (also die 7) und die dann mit der 5 tauschen, also hast Du: <2 4 3 1> 5 <8 7> Also 7 und 5 vertauscht. Jetzt gehst Du mit den beiden Teillisten weiter. Links ist also 2 4 3 1 und Pivot ist wieder 1. Du suchst von links nach rechts ach einer Zahl die größer ist (das ist gleich die erst, die 2) und von rechts nach einer, die kleiner ist (gibt es keine), also läuft man von rechts nach links komplett durch. Also gibt es nur 2 4 3 für die rechte Liste und Pivot 1. Jetzt wieder die 2 (also erste Zahl von der rechten Liste) mit dem Pivot vertauschen: 1 <4 3 2> Jetzt geht es mit 4 3 2 weiter, also Pivot 2 und sowohl 4 3 ist größer also 2, also wieder nur rechte Liste und 4 mit Pivot vertauschen: 2 <3 4> Wenn man nur noch zwei in einer Liste hat, tauscht man, wenn die Reihenfolge falsch ist, sonst nicht. 3 ist kleiner 4, also stimmt schon alles, dann lässt man die Liste wie sie ist (Rekursion ist in diesem Ast jetzt beendet). Man hat also inzwischen: 1 2 3 4 aus der rechten Liste und geht mit der 8 7 weiter. Hier sind es auch nur noch zwei Elemente, 8 mit 7 verglichen; falsche Reihenfolge, also tauschen, dann hat man rechts 7 8 Und schon ist man fertig. mit 1 2 3 4 5 7 8 Gruß Marco
14.09.2014, 19:11	Auf diesen Beitrag antworten »
Haevelin	Im Netz findet sich aber eine zu meiner analoge Lösung unter: Quicksortbeispiel
16.09.2014, 15:53	Auf diesen Beitrag antworten »
as_string	Mmh... vielleicht ist es im Prinzip auch äquivalent... Ich glaube, ich hatte Dein Vorgehen auch erst falsch verstanden. Fakt ist, ich kenne es so, dass man das Pivotelement aus dem eigentlichen Sortieren erst immer raus nimmt und dann am Ende in die Mitte der beiden Listen bringt. Kann sein, dass das bei Deiner Technik auch immer automatisch so mit sortiert wird dann, keine Ahnung. Die Zahlenfolge ist auch irgendwie ungünstig, weil ja ganz oft das Pivot-Element dann das kleinste in der (Rest-)Liste ist und deshalb gar nichts anderes getauscht werden muss. Deshalb dachte ich, dass Dein Vorgehen nur deshalb aus Zufall funktioniert hat... Gruß Marco
Anzeige

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »