Also wenn du die 8 weglässt, dann würde ich sagen ist die 7 schon sortiert, sprich wenn du es implementierst, was ich noch nicht gemacht habe, würde ich sagen, wenn links oder rechts mal nix findet, dann zahl sortiert, und mit neue pivot(s) wählen gehts dann weiter
hmm, nee, haut irgendwie noch net hin. Ich krieg z.b. folgenden Ablauf:
4 3 2 1
li = 4, re = %
tausche größeres (4) mit pivot (1)
1 3 2 4
linke hälfte leer
rechte hälfte:
1 3 2 4
li = %, re = 2
tausche größeres (2) mit pivot (4)
1 3 4 2
linke hälfte nur 1 element (3)
rechte hälfte nur 1 element (2)
fertig:
1 3 4 2 (nicht sortiert!)
rot: aktueller arbeitsbereich
%: out of range
bold: pivot
Glaub fehler war beim 2. Schritt.
Ich habe so das Gefühl, wenn man mit einem nix findet, dass man dann das Pivot nehmen muss. In dem Fall würde man es mit sich selber tauschen (bleibt also stahen) und macht mit Pivot 2 weiter.
Nur so ne Idee, keine Garantie.
hm… vllt musst du, da du das Pivot immer rechts wählst, folgendes annehmen:
li = [zahl], re = % → tausche Pivot mit grösserem
li= %, re = [zahl] → Pivot ist sortiert, wähle neues Pivot.
Ich rede mir das jetzt nur so ein …
Aktueller Stand der Dinge:
ich hab den qsort jetzt einfach mal von der Folie abgetippt und mit meiner Funktion einen Zeitvergleich gemacht… Gut, 30ms sind dann doch etwas schneller als 260ms 8-(
Ein Pivot-Element aus der Mitte ist dabei etwa 5ms schneller gegenüber einem am Ende. (Gemessen bei 400 Zufallszahlen zwischen 0 und 1000. Das Ergebnis wurde selbstverständlich geprüft.)
Ich hab zwar noch nicht verstanden, welche Bedeutung die Variablen im Algorithmus genau haben, dafür kann ich jetzt den Quicksort aus der Vorlesung erklären. Jedenfalls wenn das Pivot-Element immer rechts ist. Also… (ich kann diese Zahlenfolge bald auswendig 
)
2 3 8 5 6 4 1 7
pivot: 7, li: 8, re: %
Hier neu: out of range ist alles außerhalb der jeweiligen ‘Hälfte’ um das PE herum. Der Links-Zeiger bleibt links und der Rechts-Zeiger bleibt rechts. Nix mehr mit auf einer Seite rumtauschen…
re ist %, also tauschen wir li mit pivot. Danach ist das Element an der aktuellen Stelle von pivot bereits sortiert. (Hier grün markiert.)
2 3 7 5 6 4 1 8
pivot: 1, li: 2, re: %
Wir merken langsam, dass re bei dieser Wahl des PE immer % sein muss.
Auch hier wird wieder li mit pivot vertauscht.
1 3 7 5 6 4 2 8
pivot: 2, li: 3, re: %
Vertausche wieder li mit pivot.
1 2 7 5 6 4 3 8
1 2 3 5 6 4 7 8
pivot: 7, li: %, re: %
Beide Zeiger haben keinen falschen Wert gefunden, also geht’s diesmal ohne Vertauschen weiter in die linkte Hälfte. (Die rechte Hälfte muss zwar theoretisch auch berücksichtigt werden, ist hier aber logischerweise immer leer.)
1 2 3 5 6 4 7 8
pivot: 4, li: 5, re: %
1 2 3 4 6 5 7 8
1 2 3 4 5 6 7 8
Ich werd mir das jetzt mal mit einem PE aus der Mitte durchmalen, aber ich denk es wird genauso laufen. Ich hoffe, dass dieses Verfahren jetzt etwas klarer wurde. (Bin ja froh, dass ich es selbst mal verstanden hab - auf dem Papier jedenfalls…)
update: Jo, ging genauso mit nem anderen PE. Muss halt bloß die einzelnen Bereiche einzeln unabhängig voneinander bearbeiten.
Dann mach mal bitte mit deiner Mathode die Reihe
4-6-3-7-2-1-8-5
Ich komm da dann auf nix richtiges.
Hab noch nen anderen Vorschlag:
Alle gefundenen Paare tauschen solange sich diese nicht gekreuzt haben.
Nächstes paar suchen.
Tausch mit Pivot Element:
Falls das Paar links von Pivot: Tausch mit größerem.
Falls das Paar rechts von Pivot: Tausch mit kleinerem.
Funzt jedenfalls bisher ganz gut
Achja und wenn kein Element gefunden ist für links oder rechts, nur tauschen wenn das eine gefundene und das Pivot Element nicht in richtiger Reihenfolge sind (z.B gefundenes links von Pivot und größer als Pivot → Tausch; gefundenes rechts von Pivot und größer als Pivot → Kein Tausch)
Ähm, also, naja… ich hab’s doch nicht verstanden 
Das sagt der Folien-Algorithmus (jede Zeile ist ein rekursiver Aufruf):
4, 6, 3, 7, 2, 1, 8, 5
swap 6, 5
swap 7, 1
4, 5, 3, 1, 2, 7, 8, 6
swap 4, 2
swap 5, 1
2, 1, 3, 5, 4, 7, 8, 6
swap 2, 1
1, 2, 3, 5, 4, 7, 8, 6
swap 5, 4
1, 2, 3, 4, 5, 7, 8, 6
swap 4, 4
1, 2, 3, 4, 5, 7, 8, 6
swap 7, 6
1, 2, 3, 4, 5, 6, 8, 7
swap 8, 7
Ergebnis:
1, 2, 3, 4, 5, 6, 7, 8
anyone?
Ach ja, wenn man das PE in die Mitte wählt, isses eine Zeile weniger…
[edit: die swaps hab ich nachträglich eingefügt]
4-6-3-7-2-1-8-5 5 Pivot
4-6-3-7-2-1-8-5 Paar: 6,1 nicht gekreuzt → Swap
4-1-3-7-2-6-8-5 Paar: 7,2 Nicht gekreuzt: SWAP
4-1-3-2-7-6-8-5 Paar: 2,7 gekreuzt, links von Pivot → mit größerem(7) Tauschen. damit ist 5 am richtigen Platz.
4-1-3-2-5-6-8-7 Pivot 2
4-1-3-2-5-6-8-7 Paar: 1,4 , nicht gekreuzt → SWAP
1-4-3-2-5-6-8-7 Paar: 1,4 gekreuzt. beide links vom Pivot → SWAP mit größerem (2,4) → 2 am richtigen platz
1 alleine → 1 richtig
1-2-3-4-5-6-8-7 Pivot:4
1-2-3-4-5-6-8-7 Paar: 3,% links von pivot und kleiner → Kein SWAP, 4 richtig, 3 richtig weil alleine
1-2-3-4-5-6-8-7 Pivot 7
1-2-3-4-5-6-8-7 Paar: 6,8 gekreuzt, beide links von pivot → SWAP mit größerem (8), 7 richtig, 6 und 8 richtig weil alleine
1-2-3-4-5-6-7-8
Habs noch mir paar andern Reihen ausprobiert, funzt einwandfrei.
Also: bei nicht gekreuzten Paaren immer swappen, beim Paar nach dem Kreuzen:
beides links: SWAP mit größerem
beides rechts: SWAP mit kleineren.
Nur eins gefunden: Swap nur wenn Reihenfolge nicht stimmt.
Toll, ich glaub ich mal nachher auch nochmal was
Also ich hab jetzt den Algo von der Folie im Kopf. Sollte jetzt also theoretisch die Vorlesungs-Version kapiert haben (hoffe ich… 
)
Und die sagt: mit dem L/R-Zeigern darfst du ruhig gleich auf dem PE anfangen, nicht erst links daneben. Demnach würde die 5 in deinem ersten Swap gleich berücksichtigt und du könntest dir das spätere max(l, r) und tauschen mit dem PE sparen. Im Folien-Algo ist nichtmal die Position des PE gespeichert, geschweige denn wird da ein größeres/kleineres Element für einen Tausch ausgesucht (das dauert doch alles viel zu lang! )
Hmm, ich mal das lieber gleich…
4 6 3 7 2 1 8 5 - pivot: 5, li: 6, re: 5
Da li <= re: Tausche 6, 5
Schiebe li und re jeweils 1 weiter
4 5 3 7 2 1 8 6 - pivot: 5, li: 7, re: 1
Da li <= re: Tausche 7, 1
Schiebe li und re jeweils 1 weiter
4 5 3 1 2 7 8 6 - pivot: 5, li: 7, re: 2
Kein Tausch
Linke Hälfte: (von Anfang bis re)
4 5 3 1 2 7 8 6 - pivot: 2, li: 4, re: 2
Da li <= re: Tausche 4, 2 (und li, re weiterschieben…)
[b]2[/b] [u]5[/u] 3 [u]1[/u] 4 7 8 6 - pivot: 2, li: 5, re: 1
Da li <= re: Tausche 5, 1 (...)
[b]2[/b] [u]1[/u] [u]3[/u] 5 4 7 8 6 - pivot: 2, li: 3, re: 1
Kein Tausch
[i]Linke Hälfte: (von Anfang bis re)[/i]
[u]2[/u] [b][u]1[/u][/b] 3 5 4 7 8 6 - pivot: 1, li: 2, re: 1
Tausche 2, 1
[b][u]1[/u][/b] [u]2[/u] 3 5 4 7 8 6 - pivot: 1, li: 2, re: 1
Kein Tausch
[i]Linke Hälfte ist nur ein Element
Rechte Hälfte ist nur ein Element[/i]
[i]Rechte Hälfte: (von li bis Ende)[/i]
1 2 3 [u]5[/u] [b][u]4[/u][/b] 7 8 6 - pivot: 4, li: 5, re: 4
Tausche 5, 4
1 2 3 [b][u]4[/u][/b] [u]5[/u] 7 8 6 - pivot: 4, li: 5, re: 4
Kein Tausch
[i]Linke Hälfte: (von Anfang bis re)[/i]
1 2 [u]3[/u] [u][b]4[/b][/u] 5 7 8 6 - pivot: 4, li: 4, re: 4
Tausche 4, 4
Naja, jetzt kommt nicht mehr viel...
[i]Rechte Hälfte ist nur ein Element[/i]
Rechte Hälfte: (von li bis Ende)
1 2 3 4 5 7 8 6 - pivot: 6, li: 7, re: 6
Tausche 7, 6
1 2 3 4 5 6 8 7 - pivot: 6, li: 8, re: 6
Kein Tausch
Linke Hälfte ist nur ein Element
Rechte Hälfte: (von li bis Ende)
1 2 3 4 5 6 [u]8[/u] [u][b]7[/b][/u] - pivot: 7, li: 8, re: 7
Tausche 8, 7
Und jetzt kommt hier auch nichts mehr...
rot: aktueller Arbeitsbereich
bold: Pivot
linie: li/re-Zeiger
grün: fertig sortiert
Wenn du dir die einzelnen Swaps von deinem Programm ausgeben lässt, kommst du auf das gleiche. (siehe vorheriger Beitrag)
(Sorry für den langen Beitrag diesmal…)
Wow, Krieg der Erklärungen :cheesy:
Hast du auch mal probiert, ein Programm dafür zu schreiben? Ich hab mal versucht, deine Erklärung zu coden, hab aufgegeben, als es mir zu kompliziert wurde und ein paar Fragen offen blieben. Dein Verfahren ist z.B. darauf angewiesen, dass das Pivot-Element immer rechts ist, oder? Und ich hab zwar gesehen, dass du beim ersten Teilen bereits die 5 als ‚sortiert‘ markiert hast, allerdings ist mir noch nicht so ganz klar, wie genau ich dann den neuen Arbeitsbereich für die Rekursion ermitteln soll. Einfach die obere Grenze der linken Hälfte um eins verringern?
Wenn man sich den Algorithmus von dem Sort Applet einmal einprägt ist das alles ganz einfach.
Ich denk mir immer das PE transparent und dann abwechselnd von rechts und links die jeweiligen Element an die Stelle vom PE schreiben und das PE an die freigewordene Stelle. Irgendwann stehts dann schon am richtigen Ort und man kann mit den zwei neuen Bereichen weitermachen :*)
@augenmann : dir is schon aufgefallen, dass das mit von rechts und von links anfangen relativ zum pivot element is, oder ? du sollst gucken ob rechts vom piv eine zahl < piv und links davon eine zahl >= piv is und dann vertauschen
@alle : leicht andere vorgehensweise im applet ! das applet guckt immer einzeln, ob die elemente links groesser sind und ob die rechts kleiner sind, vertauscht aber nicht , sondern schiebt jeweils von links hinter das piv oder von rechts vor das piv. also ist der wesentliche unterschied der dass im skript gesagt wird : wir tauschen zahlen und im aplet gesagt wird wir schieben (also nicht gleichzeitig an zwei zahlen fummeln). Ihr werdet feststellen (wenn ihr euch das mal genau anschaut (auch die stoyansche implementierung) dass das applet unter umstaenden mehr schritte benoetigt, eben weil nicht direkt getauscht wird.
Ich glaub das is wohl das, was hier soviel verwirrung ausloesst ?
naja, das Applet tauscht ja auch, nur eben in zwei Schritten…
Ich hoffe nur, dass bei der Auswertung der Klausur der Korrekteur auch weiss, dass man das auch so wie im Applet machen kann 
Also mir langts jetzt langsam, mit dem ganzen geswappe. Ich merk mir das jetzt einfach so: Nimm Pivot, setzte alle die kleiner sind links, alle die größer sind rechts. Damit ist Pivot an richtiger Stelle und man macht mit den Teilintervallen weiter.
Ob man das jetzt so wie Yves, wie Ich oder wie im Applet macht ist ja wohl egal. Hauptsache der Sinn von Quicksort wurde verstanden, oder etwa nicht?
ganz deiner meinung sei
Ja mir ist schon aufgefallen, dass man normalerweise links und rechts vom Pivot schaut, aber es ging um die Klausuraufgabe in der das Pivot immer das rechteste Element ist, sprich weiter rechts zu schauen war nicht sinnvoll… oder so
Also gut, ich hab mir das Applet jetzt auch mal angeschaut… Hmm, ist das sicher ein Quicksort? Was das Teil da treibt hab ich ja noch nie gesehen… (und die Klausur-Auswerter?)
Aber weiß zufällig jemand, ob auch irgendwo in einer Klausur ein Algorithmus/Java-Programm zum Quicksort gefragt ist? Auf dem Zettel selber Zahlen rumschieben kann man wahrscheinlich fast machen wie man mag, aber die konkrete Implementierung in was Rechner-lesbares muss halt auf jeden Fall funktionieren.
@str1ch444
swap’n heisst einfach nur tauschen
oder verwirrt dich das kreuzen ?
die meinen nur das man das pivot tauscht falls sich der linke und der rechte zeiger kreuzen. das war alles auf die klausuraufgabe bezogen.
ich fands eigentlich ganz interessant das die das angesprochen haben, also die klausuraufgabe …
implementiere das einfach mal, dann siehste genau das die meinen.
kopf-quicksorten wäre wohl zu einfach für eine klausur denk ich.
kann einer von euch dem qsort mal posten oder ihn mir schicken:
thecansteiner@web.de
irgendwo steh ich beim implementieren aufm schlauch oder bin einfach zu dumm… und auch zu faul malehrlichsei