 Quicksort |
Phoney
Jungspund
Dabei seit: 13.12.2006
Beiträge: 20
 |
|
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/algo...quick/quick.htm unter Simulation (Aufteilungsverfahren).
http://irgroup.cs.uni-magdeburg.de/dt/vo...n/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
|
|
21.06.2007 14:59 |
|
|
dachdecker2
Moderator
Dabei seit: 14.09.2006
Beiträge: 20
|
|
Du hast die pdf-Datei falsch verstanden - neben dem Bild erklärt der Pseudocode, was gemacht wird.
8215973 Ist die zu Sortierende Folge.
1.) 5 wird als Pivot festgelegt (wie auch immer - zum Beispiel durch Zufall)
2.) Die Folge wird zunächst geteilt (Elemente links, Elemente rechts, Pivot),dazu tauschen die einfach das Pivot und das letzte Element:
821 397 5
3.) Jetzt geht es weiter, wie du erwartest (suche eine Zahl > 5 in 821397, suche eine Zahl < 5 in 798312, tausche die Treffer, brich ab wenn die Treffer in der korrekten Reihenfolge vorliegen)
321 897 5
4.) (die kleineren Elemente sind von den größeren getrennt) Lege das Pivot zwischen die kleineren und die größeren Elemente.
5.) Fahre mit 321 bzw 897 fort wie in 1.) beschrieben.
Warum das Pivot verschoben wird, siehst du in Schritt 3 - du durchsuchst die ganze Folge nach kleineren/größeren Zahlen - das betrifft nicht das Pivot, das nach diesem Schritt an die richtige Position gelegt wird.
__________________
Gruß, dachdecker2
http://rettedeinefreiheit.de
|
|
|
22.06.2007 08:53 |
|
|
|
