Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Quicksort - Wer kann mir weiterhelfen ? -
Hi,
hat von euch jetzt schon jemand diesen Quicksort-Algorithmus
gecheckt ? Ich weiß nicht, ich bleib da immer wieder hängen.
Kann mir jemand vielleicht die Folge (4,9,3,2,5,1) schrittweise
erklären. Wie wähle ich da das Pivot-Element aus, und wann muss ich es tauschen ?
Meldet euch halt mal !
ciao humml 8-(
hi laesterhumml,
das thema hatten wir schonmal in einem anderen thread: http://uni.unclassified.de/forum/thread.php?id=588
v. a. der verweis auf
http://math.hws.edu/TMCM/java/xSortLab/
ist super. schau dir das applet dort mit quicksort etwa 20 mal an, dann verstehst du, wie du das machen musst. ansonsten halt nochmal konkretere fragen stellen, weil es nicht so einfach ist, den algorithmus einfach so mal zu erklaeren…
20 mal ? 8-(
die sortier algorithmen sind alle sehr sehr einfach (nur implementierung find ich teilweise einwenig komisch)
du siehst bestimmt nur den wald voller bäume nicht, also keine sorge 
die korrekte auswahl des pivaut elements ist stoff von theoinf 2 or 3 … kannste also per zufall machen.
wenn ich das jetzt noch richtig im kopf hab, nimmt man da doch immer das in der mitte, oder? naja, ich konnte jetzt vor ein paar tagen zumindest schonmal auf dem papier quicksorten. auch wenn ich für meine handlungen noch keinen algorithmus gefunden hab 
ich nehm auch immer die mitte, aber man kann (ohne diese tolle theo inf herleitung) genauso gut jede andere nehmen. oder täusche ich mich ? hmm mal probieren …
Die Auswahl des Pivotelements ist eigentlich unerheblich, allenfalls für Optimierungen wichtig. Soweit ich mich erinnern kann haben wie immer das “Rechteste” genommen, das ist AFAIK leichter zu implementieren.
Prinzip des Quicksort ist folgendes.
Du gibst dich erstmal damit zufrieden, dass du ein Element in der Mitte hast und für dieses Element sagen kannst, dass alle links davon kleiner sind und alle rechts davon größer.
Danach machst du das nochmal für die Menge links von diesem Element und dann rechts davon.
Dieses ominöse Element ist das Pivot-Element, und mit dem Zeigerwandern stellst du den Zustand her, da du ja immer dann tauscht, wenn der Zustand für 2 Elemente nicht erfüllt ist.
Nochmal Quicksort
hallöchen zusammen,
also @steppenwolf : ich hab mir dieses verwirrende Applet jetzt oft genug angesehen, durchgeblickt habe ich allersdings nicht. Und den alten Thread habe ich auch schon entdeckt.
@frahi :
Ist es nicht so, das ich das Pivot-Element(EX) nach Knuth als erstes wähle, und nach Hoare beliebig. Erst dann suche ich die rechte Seite des EX, ob da ein kleineres ist. Dann die linke, ob da ein größeres ist. Wenn beides zutrifft, tausche ich die beiden aus. Bis Folgendes dasteht :
Ekleiner < EX < Egößer ???
Aber was passiert, wenn dieser Fall auftritt, und die Elemente rechts und links von EX noch nicht sortiert sind ? Z.B. so :
12|15|8|18 < 20 < 30|22|26|27
Muss ich dann ein neues Pivot (EX) in der unsortierten Reihe auswählen, und diesen Vorgang solange wiederholen, bis alle sortiert sind ?
Kann mir da jemand zustimmen, oder gibts andere Vorschläge ?
thx humml :#: :motz: :wand:
@hummel: zustimm
Ist doch diese tolle “Teile-und-Herrsche” Regel
Ich hab das so verstanden:
Beliebiges P.Element wählen, mitte ist ideal. So lange um das P.Element tauschen, bis entweder L und R am P.Element ankommen, oder das P.Element getauscht wird. Wird das P.Element getauscht, kann man dieses fixieren, denn es ist jetzt an der richtigen Position ist. Jetzt erhält man 2 Teile, in denen man wieder mit einem beliebigen P.Element anfängt.
In der Klausuraufgabe vom 09.2002 war nur verlangt, dass das P.Element immer das rechteste sein soll…
Wir können ja mal von der 09.02 Klausur die Quicksort Reihe durchgehen, weil irgendwie verwirrt mich das mit dem Pivotelement ganz rechts. Die Rehe fängt an:
2 3 8 5 6 4 1 7 (7 ist Pivot)
2 3 7 5 6 4 1 8 (7&8 getauscht)
2 3 1 5 6 4 7 8 (1&7 getauscht; 7&8 fertig; 4=PE)
2 3 1 4 6 5 7 8 (4&5 getauscht; 4 fertig; 1,5=PE)
1 3 2 4 5 6 7 8 (1&2, 5&6 get.; 1,5,6 fertig; 2=PE)
1 2 3 4 5 6 7 8 (2&3 get.; 2,3 fertig; PE={}=>fertig!)
stimmt das so ungefähr, oder wie sind bei euch die Schritte?
das ganz rechte, ok
weil die 8 größer war, ok
warum 1<->7 ?
woher weißt du an der stelle, dass die 4 fertig ist?
hä?
confused
das ganz rechte, ok
weil die 8 größer war, ok
warum 1<->7 ?
Ich dachte das so:
Die 7 ist noch Pivot, von links bleibt der Zeiger wieder auf der 7 stehen und von recht bei der 1.
woher weißt du an der stelle, dass die 4 fertig ist?
weil der zeiger von links und rechts auf dem PE steht? (Ehrlich gesagt, keine Ahnung…)
hä?
rechte seite ist vertauscht&fertig (beide zeiger auf PE)
und auf der linken seite ist die 1 fertig (links davon ist kein bereich mehr und rechts davon ist die 2 neues PE)
confused
Naja, das war jetzt nur noch die zwei mit der drei vertauscht
Aber nimm das jetzt nicht für Gesetz, ich hab keine Ahnung ob das nicht totaler Bockmist ist, deswegen wollt ichs hier ja diskutieren. Wie ist denn deine Lösung?
Also läuft das jetzt allgemein so, dass ich mit einem Zeiger von links ankomm und mit einem von rechts und wenn auf beiden Seiten was nicht passt, wird getauscht. Wenn auf einer Seite was nicht passt, wird halt mit dem PE getauscht. Richtig?
Aber läuft der Algorithmus, den wir mal hatten (und wie er ja eigentlich auch funktionieren sollte) nicht rekursiv für jeden Teilbereich? Also wär das ja äußerst umständlich, das jetzt (nur weil’s ne Tabelle ist) alles parallel auszurechnen…
2 3 8 5 6 4 1 7 (7 ist Pivot, finde von rechts kleiner Pivot, von links grösser)
2 3 8 5 6 4 1 7 (8 und 1 werden getauscht)
2 3 1 5 6 4 8 7 (7 ist Pivot, finde von rechts kleiner, von links grösser, da überkreuz von l+r jetzt tausch!)
2 3 1 5 6 4 7 8 (7 ist fertig, 8 auch da sie alleine steht und somit sortiert ist, neues Pivot 4, überkreuz von l+r, tausch 4 und 5)
2 3 1 4 6 5 7 8 (4 fertig, neue Pivots 5 und 1)
1 3 2 4 5 6 7 8 (tausch 5 und 6, 5 fertig, 6 auch da alleine steht, tausch 1 und 2, neues Pivot 2)
1 2 3 4 5 6 7 8
Sobald das Pivot getauscht wird ist es an der richtigen Stelle, getauscht wird das Pivot mit dem grösseren, und nur wenn die Zeiger l und r überkreuz stehen oder an einander vorbeilaufen oder wie auch immer man das bezeichnen will.
Werd ich wohl die meisten edits schaffen
Augenmann, bist du dir denn wenigstens sicher? Weil zB von Zeile 2 nach 3 tauscht du ja die Zahlen innerhalb des linken Bereiches. Wenn das PE in der Mitte ist haben wir ja immer von links und rechts etwas vertauscht, oder hab ich das falsch in Erinnerung?
[edit:] okay, ich hab mir das SortApplet angeschaut, und die Lösung vom Augenmann stimmt imo.
naja wenn du das pivot an einer seite fixierst, so wie in der aufgabenstellung verlangt, dann kann man schwerlich was um das pivot herumtauschen 
bin mir auch sicher das das stimmt.
[quote=Augenmann]
2 3 8 5 6 4 1 7 (7 ist Pivot, finde von rechts kleiner Pivot, von links grösser)
2 3 8 5 6 4 1 7 (8 und 1 werden getauscht)
2 3 1 5 6 4 8 7 (7 ist Pivot, finde von rechts kleiner, von links grösser, da überkreuz von l+r jetzt tausch!)[/quote]
@augenmann oder jemanden, der das checkt :
Was findest du denn rechts von 7, das kleiner ist als 7 ? Da steht doch nix mehr !!! Wie gehst du hier vor ? Das mit der 8 lass ich mir noch eingehen, aber ich hätte an dieser Stelle nur die 7 mit der 8 getauscht :
2 3 1 5 6 4 7 8 Wäre das falsch ? Wie setzt du denn deine Zeiger,wenn du nur vertauschst, wenn beide “überkreuz” stehen ?Kuckst du abwechseln rechts u. links, oder schaust du erst auf eine Seite, bis du fündig wirst?
ciao humml :rolleyes:
Richtig! kA wie ich das am besten erkläre, das mit dem links und rechts bezieht sich in dieser Aufgabe zwar auf das PivotElement, aber nicht links und rechts von diesem.
Also nochmal ganz langsam
2 3 8 5 6 4 1 7 Beginne von rechts und suche ein Element, kleiner als Pivot:
2 3 8 5 6 4 1 7 Beginne von links und suche ein Element grösser als Pivot:
2 3 8 5 6 4 1 7 Tausche beide:
2 3 1 5 6 4 8 7 Beginne von rechts und suche ein Element kleiner als Pivot:
2 3 1 5 6 4 8 7 Beginne von links und suche ein Element grösser als Pivot:
2 3 1 5 6 4 8 7 Achtung, rechts und links stehen jetzt überkreuz, d.h. tausche grösseren mit dem Pivot:
2 3 1 5 6 4 7 8 Alles was jetzt links vom Pivot steht ist kleiner als das Pivot, alles was rechts steht grösser. Da Pivot getauscht worden ist, ist es an der richtigen Stelle. Neue Pivots sind
2 3 1 5 6 4 7 8 ||| 4 und 8. Da 8 das einzige Element ist, ist es sortiert, somit weiter bei der 4: Suche ein Element von rechts, dass kleiner als Pivot ist:
2 3 1 5 6 4 7 8 Suche ein Element von links das grösser als Pivot ist:
2 3 1 5 6 4 7 8 Achtung, links und rechts stehen überkreuz, tausche Pivot mit dem grösseren:
2 3 1 4 6 5 7 8 ||| 4 ist jetzt sortiert, usw…
Ich hoffe jetzt sind alle zweifel ausgeräumt. Der Einfachheit halber mach die Aufgabe mal auf Papier und nenne den Zeiger der von links kommt L und den der von rechts kommt R. Tauschen ist immer dann angesagt, wenn L rechts von R steht oder andersrum Solange das nicht der Fall ist, bewegt sich das PivotElement nicht.
Aber ich denke du hast das schon richtig verstanden, musst nur berücksichtigen, dass man auch innerhalb einer Seite tauschen kann, da muss nicht immer das Pivot beteiligt sein…
Das Pivot ist sozusagen nur der Maßstab, deswegen ist es auch vollkommen egal welche Zahl du als Pivot nimmst. Das Pivot Element nimmst du sozusagen raus und schaust dann von einer Seite solange bis du etwas kleineres/bzw grösseres (je nach der Seite von der du kommst) findest und setzst dass dann an die Stelle vom Pivot. dann kommst du von der anderen Seite und suchst wieder etwas grösseres/kleineres und setzt das an die neue freie Stelle.
Wenn sich dann deine Grenzen überlappen, dann steht links vom Pivot alles kleinere und rechts davon alles grössere. ergo: das Pivot ist jetzt an der richtigen Stelle, und du musst den linken UND den rechten Bereich wieder ordnen (Hier beginnt dann die Rekursion…)
Also erstmal vielen Dank euch für die anschauliche Erklärung des ganzen Ablaufs!
Aber jetzt hab ich ein Problem, einen spezielfall in meiner Implementierung zu bearbeiten:
Was passiert, wenn ich die 8 jetzt einfach mal weglasse. Dann steht die größte Zahl (7) ganz rechts und wird da auch bleiben. Damit ist:
Array = 2 3 5 6 4 1 7
pivot = 7
rechts = 1
links = ??? (Es gibt kein Element > pivot)
Frage: Wo soll in diesem Fall der links-Zeiger stehen (bleiben) und was ist danach zu vertauschen oder wo muss ich weiter rekursieren?
Ansonsten bin ich bloß mal gespannt, ob der Quicksort wirklich so richtig schnell ist… Ich mach das Programm jetzt erstmal in PHP, da kann ich es mit meiner ‘eigenen’ Sortierungs-Funktion testen. Und die hab ich gestern gerade erst um ca. 1/3 beschleunigt…
update: Ich hab mich grad selber noch etwas an der Lösung bzw. am Neu-Ausdenken des Algorithmus betätigt, bin damit allerdings furchtbar in die Wüste gerannt. Also ich hab keine Lösung dafür.
Aber seid ihr euch sicher, dass der hier vorgestellte qsort auch der ist, den unsere Profs kennen? Auf den Folien wird nämlich strikt der links/rechte Bereich um das PE durchsucht. OK, ist ziemlich sinnlos, wenn das PE ganz rechts ist, und daher find ich auch die Idee schon ziemlich sinnlos, aber wer weiß…
Und mit dem Algorithmus auf der Folie konnte ich nix anfangen. Der ist dermaßen konfus formuliert… 