Geschrieben von Phoney am 21.06.2007 um 14:59:
Quicksort
Hoi
Ich habe mich schon mitdem Quicksort beschäftigt, verstehe es aber nicht wirklich.
Ich kenne die Application
http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/quick/quick.htm unter Simulation (Aufteilungsverfahren).
http://irgroup.cs.uni-magdeburg.de/dt/vorlesungen/AuD_WS2006_2007_materialien/AuDTeil4b.pdf
[Seite 9]
Sind das irgendwie zwei verschiedene Quicksorts? Also es geht erst einmal um die Zahlenfolge
8 2 1 5 9 7 3
Wobei 5 das Pivotelement ist. Jetzt sagt die Application eben sehr detailliert, dass man von links das erste Element sucht, das größer als die fünf ist . Also die 8. Von ganz rechts geht man zum ersten Element, was kleiner gleich 5 ist. DAs ist die drei.
Also tauscht man 3 und die 8, es ergibt sich
3 2 1 5 9 7 8
Jetz muß man nach der Application noch mal das Gleiche machn. Dann kämen beide Zeiger sozusagen auf die 5 und diese würde man splitten
also müsste man mit Quicksort 3 2 1 und 9 7 8 sortieren
Wie sortiert man denn jetz 9 7 8? 7 is Pivotelement, 9 und die acht wird getauscht
8 7 9
Dann splitet man es auf, setzt es richtig zusammen
7 8 9.
Richtig?
Im PDF stehen aber folgende Rechenschritte:
8 2 1 5 9 7 3
5 is Pivotelement
8 2 1 3 9 7 5
2 1 3 8 9 7 5
2 1 3 5 9 7 8
und so weiter
Das verstehe ich aber leider gar nicht. Da steht zwar auch der Algorithmus, aber warum schreibt man das Pivotelement ganz nach rechts? Was passiert da?
Grüße,
Phoney