Quicksort Frage

[Tiji]

Hallo,

ich verstehe den Quicksort nicht so ganz. Und zwar habe ich mir eine Zahlenfolge ausgedacht und versucht das Prinzip darauf anzuwenden. Das Pivotelement soll bei mir zwischen 3 zufälligen Zahlen der Folge das Mittlere sein.

Folge:

6 9 3 7 8 1 1 2 5 7 Pivot ist bei mir hier 7

6 5 3 7 8 1 1 2 9 7 Vertauscht 5 und 9

6 5 3 7 2 1 1 8 9 7

Ab hier bin ich mir schon nicht mehr sicher, wird jetzt die 8 mit der 2 vertauscht ?

Und wie ist das wenn ich nur noch 2 Zahlen auf einer Seite übrig habe und versucht mit meiner Methode das Pivotelement zu ermitteln. Brauche ich dazu eine extra Abfrage oder gibt es bessere Möglichkeiten ein geeignetes Pivot zu ermitteln.

Wäre freundlich, wenn mir einer mal die Folge auf einer Seite durchmacht.

Danke schonmal im vorraus ^^

[carstenj]

Hi,

du tauscht die 7 mit der 2. Dann sieht das so aus:

6 5 3 2 8 1 1 7 9 7

Danach die 8 mit der 1:

6 5 3 2 1 1 | 8 7 9 7

Danach ist der linke Zeiger auf der 1, und der rechte auf der 8, dann ist dein Ziel ja erstmal erreicht: Alle Zahlen links vom linken Zeiger sind kleiner als das Pivot Element, alle Zahlen rechts davon größer oder gleich.

Im Grunde steht das so bei Wikipedia:

Quicksort

Der Knackpunkt ist eben genau das Ermitteln des Pivotelements.