Frage zur Funktionsweise des Quicksort Algorithmus

[0w3X]

Hallo,

zuerst einmal hoffe ich, dass ich hier im richtigen Forenbereich bin, falls nicht möchte ich mich schonmal entschuldigen.
Also meine Frage ist ob es eine gewisse Reihenfolge gibt wie die Zahlen um das Pivotelement sortiert werden.
Es werden ja alle Zahlen die größer als das Pivotelement sind rechts davon angeordnet und alle die kleiner sind links. Aber in welcher Reihenfolge werden die Zahlen rechts und links angeordnet?
Bsp.:

4 8 6 9 3 Wenn wir bei dieser Liste 6 als Pivot wählen in welcher Reihenfolge stehen dann die 3 und die 4 links neben der 6?



Danke im Voraus für alle Antworten!

 

[jumpin]

Hi

Soweit ich Quicksort in Erinnerung habe, ist nur durch die Angabe "Quicksort" nicht genau definiert, in welcher Reihenfolge 3 und 4 nun auftauchen, sie müssen einfach beide links von der 6 stehen. Du sortierst ja anschliessend links und recht weiter, also ...

Die Angabe "Quicksort" sagt ja z.B. auch nichts darüber aus, wie man das Pivot-Element auswählt.

Gruss - jumin

 

[0w3X]

Danke für die schnelle Antwort!
Heißt das jetzt, dass man sich, wenn man per Hand etwas nach diesem Algorithmus sortiert, sich die Reihenfolge aussuchen kann?

 

[Mr.Smith]

beginn: 4 8 6 9 3 (p=6)

4 3 6 9 8 (hab es gelernt mit zufälligem pivot (am besten wäre natürlich der median welcher zufälligerweise sogar 6 ist))

dann hast du linken indize, der solang nach rechts läuft bis er wo angekommen ist, was größer als pivot ist und rechts indize der solang nach links läuft bis er ne zahl findet die kleiner ist als pivot.

8 ist größer und 3 ist kleiner und beide noch nicht am pivot vorbei, daher werden die 2 getauscht.

4 und 3 sind kleiner und 9 und 8 sind größer.

sprich list 4 und 3 wird genommen und als neue teilliste sortiert, genausoe 9 und 8

4 3 -> 3 4 und 9 8 -> 8 9
dann wird die neue liste zusammengesetzt und tata
3 4 6 8 9

wenn die teillisten mehr elemente hätten, dann müsste wieder (entweder per median oder zufällig) hierfür ein neues pivot gewählt werden

 

[0w3X]

Also immer von außen nach innen die Zahlen die kleiner als Pivot sind direkt neben das Pivot?

Ergänzung (9. April 2016)

Alles klar!
Danke!

 

[jumpin]

Du kannst es dir bedingt aussuchen: Du musst es einfach immer gleich machen

Meistens wird das Pivot-Element zuerst ganz auf eine Seite getauscht (z.B. nach rechts), anschliessend umsortiert, dann das Pivot-Element wieder in die Mitte, bei deinem Beispiel:
4 8 6 9 3: Pivot-Element 6 ganz nach Rechts tauschen
4 8 3 9 6 -> Suche nun von links her das erste Element (x) grösser als 6, von rechts her das erste Element (y) kleiner als 6. Wenn x links von y steht, tauschen. Sonst: Pivot mit x tauschen.
Im Beispiel: x = 8, y = 3
4 3 8 9 6 -> x = 8, y = 3, aber x rechts von y -> Tausche x mit dem Pivot
4 3 6 9 8

Das Pivot-Element in der Mitte belassen funktioniert so nicht so einfach, man normalerweise nicht genau den Median trifft und man bei Listen mit einer geraden Anzahl Elementen Probleme bekommt.

 

[Mr.Smith]

hab noch nen altes in scheme gefunden müsste eigtl auch noch wo eins in java und c++ haben

; 2. Quicksort
; bekommt liste von reals
; gibt sie nach Wert aufsteigend sortiert zurück
; filtert alle die kleiner, gleich und größer sind in eine neue Liste
; am Ende werden alle die gleich (eine oder mehr glechzahlige listen) appendet

(: quicksort ((list-of real) -> (list-of real)))

(check-expect (quicksort (list)) (list))
(check-expect (quicksort (list 1)) (list 1))
(check-expect (quicksort (list 1 2 3 4)) (list 1 2 3 4))
(check-expect (quicksort (list 4 3 2 1)) (list 1 2 3 4))
(check-expect (quicksort (list 3 5 2 5 3 1 4 6 4)) (list 1 2 3 3 4 4 5 5 6))
bis hier waren nur tests und typ festlegung für quicksort (kriegt liste von real werten und gibt ne liste von realwerten zurück, das jetzt ist der quicksort

(define quicksort
(lambda (lis)
( if (empty? lis)
empty
(append (quicksort
(filter (lambda (x) (< x (first lis) )) lis))
(filter (lambda (x) (= x (first lis) )) lis)
(quicksort
(filter (lambda (x) (> x (first lis) )) lis))))))

; Extrahiere die Elemente von xs, die Prädikat p? erfüllen
(: filter ((%a -> boolean) (list-of %a) -> (list-of %a)))
(define filter
(lambda (p? xs)
(cond ((empty? xs) empty)
((pair? xs)
(if (p? (first xs))
(make-pair (first xs) (filter p? (rest xs)))
(filter p? (rest xs)))))))



muss mal wieder dr.racket installieren hab sooo viel Scheme vergessen^^ dabei konnt ich das mal so gut


jetzt versteh ich wieder wie es funzte
recht kurzer und knackiger code.
filterfunktion filtert alle die kleiner als pivot und größer als pivot sind in ne neue liste. pivot ist immer erstes element.
die kleineren dann wieder rek. und die größeren rek. wenn ne liste kein element mehr enthält, dann isses fertig.

 

[kuddlmuddl]

https://www.youtube.com/watch?v=ywWBy6J5gz8

 

[VikingGe]

4 3 6 9 8 (hab es gelernt mit zufälligem pivot

Ich hab hier ne Implementierung rumfliegen, bei der ich drei Elemente überprüfe und davon den Median nehme:
- Das erste Element
- Das letzte Element
- Das Element in der Mitte

Hat den Vorteil, dass man bei bereits sortierten Listen immer Best-Case-Laufzeit erreicht und in allen anderen Fällen die Wahrscheinlichkeit für den Worst Case deutlich reduziert.
Median der gesamten Liste bestimmen ist etwas unpraktikabel.

 

[maxwell-cs]

Median der gesamten Liste bestimmen ist etwas unpraktikabel.

wieso, geht doch in linearer Zeit

 

[Affe007]

Hier kannst du dir anschauen wie übliche Sortier-Algorithmen sortieren

https://www.youtube.com/watch?v=ZZuD6iUe3Pc

 

[NemesisFS]

Optimal ist Quicksort mit dem Median. Den in jedem Schritt zu berechnen ist allerdings zu teuer, die Laufzeit davon ist linear, sodass das Ergebnis in O(n^2 log(n)) (edit: Die asymptotische Laufzeit ist O(n log(n)), der konstante Faktor aber sehr groß) ist. Andere Schemata zur Pivotwahl sind:

• Zufall: 1.386 n log(n)
• Median-of-Three: 1.188 n log(n)
• Pseudomedian-of-Nine: ?

Zufall ist in manchen Fällen nicht benutzbar, sei es, weil die Software deterministisch sein muss (sicherheitskritische Anwendungen, dort nutzt man ohnehin eher Heapsort afaik) oder weil der gemeinsame Zufallsgenerator das Bottleneck wird. Der Pseudomedian-of-Nine ist ein rekursiver Median-of-Three der für größere Arrays besser sein soll, auch wenn ich auf die schnelle keine konkreten Zahlen finden konnte. Wegen des konstanten Overheads bei Quicksort nutzt man im Allgemeinen für kleine Teilarrays ohnehin Insertionsort.

 

[fz21z]

Der Prof. hier hat ne gute Seite, wird auch verständlich mit Schaubildern erklärt.
http://www.inf.fh-flensburg.de/lang/veranst/alg/index.htm

 

[maxwell-cs]

Optimal ist Quicksort mit dem Median. Den in jedem Schritt zu berechnen ist allerdings zu teuer, die Laufzeit davon ist linear, sodass das Ergebnis in O(n^2 log(n)) ist.

wieso das?
Median berechnen ist linear, der Rest der Iteration (aufteilen nach links und rechts) auch, also kostet es nur einen konstanten Faktor und man errreicht O(n logn).
Natuerlich ist die praktische Laufzeit dieser Variante schlecht, weil die Konstanten deutlich schlechter sind und durch die Mediansuche dominiert werden duerften..

 

[NemesisFS]

...

Tatsache, mein Fehler.