?
ghorst schrieb:
so spontan würde ich sagen: du liegst richtig. (die median variante von quicksort ist mir nicht bekannt, daher las ich nur deine schritte und bin der meinung, dass das zum erfolg führen sollte. ob das quicksort mittels median ist, kann ich aber nicht beurteilen.)
quicksort ist ein divide and conquer algo und du hast gut beschrieben, wie geteilt und wie erobert wird.
Das Java Applet stützt meine These, allerdings wird gemäß meines Aufschriebes generell immer am Anfang getauscht sobald linker Randpunkt bzw. rechter Randpunkt größer bzw. kleiner ist....
Schade das man im Applett nur Zufallswerte bekommt
Das Problem ist vielmehr z.B.
Wenn ich die Folge
10,6,12,8,18,9,7,16,5,15,20 habe und dann durch den ersten Durchgang das Ergebnis
5,6,7,8,9#10#,12,16,20,15,18 (#_# = Median)
Dann besteht das rechte Teilfeld aus:
12,16,#20#,15,18
Hier erfüllt die 15 nicht das Kriterium für Median < X
Die 12,16 stimmen dagegen das führt dazu das der Median mit X vertauscht wird
Neue Folge:
12,16,15,18,20
Jetzt sind aber 12,16,15 ein Teilfeld und die 20 ein Teilfeld...
Die 18 nunja weiss der Teufel....
Mir ist gerade nicht klar warum genau an der Stelle das splitten in Teilfelder stattfindet
Anmerkung:
Med3 Killersequenzen sind mir bekannt, spielen hier aber auch keine Rolle da es nur um ein Schaubild einer Folge geht auf die das Verfahren angewendet wird.
Das Pivot Element ist zunächst [(li+re)/2] wobei links vom Median ein Teilfeld < Median analog dazu rechts.
Wenn das Array vollständig durchgegangen wurde, wird der Median mit dem rechten Randpunkt vertauscht und im nun verkleinerten Teilfeld erneut der Median bestimmt-
