Quicksort 3 Median

Hey,

ich muss u.A. für eine Klausur in Form eine Tabelle aufzeigen wie der Quicksort 3 Median Algorhythmus arbeitet.

Dabei habe ich aktuell aber Probleme mit dem Verständnis, weshalb ich euch liebe Forenmitglieder bitten möchte mir die Funktionsweise zu erklären.

Also soweit mein Kenntnisstand ist:
- zunächst wird der Median ermittelt welcher sich aus (linker Rand+rechter Rand)/2 errechnet. d.h. (2+6)/2 -> 3 -> 4 Element (Index beginnend 0)
- Anschließend werden alle Elemente die > Median sind rechts vom Median geschrieben, die Elemente die > Median sind links

Aber wie geht es nun weiter?

Als Beispiel hätte ich die Folge
10,6,12,8,18,9,7,16,5,15,20

d.h. Median ist die 9?

Bitte um Hilfe

LG

hallo, spiel doch mal ein wenig mit diesem java applet rum (bei "sort kind" quicksort auswählen). dann wirst du deine aufzeichnungen sicherlich wieder verstehen. der quicksort algorithmus wird dort inklusive quelltext verständlich illustriert.

ghorst

deine bitte um hilfe ist ein wenig unspezifisch. du hast in deinem text erklärt, was da passiert. was genau willst du also wissen?

ghorst schrieb:

deine bitte um hilfe ist ein wenig unspezifisch. du hast in deinem text erklärt, was da passiert. was genau willst du also wissen?

Ob ich richtig liege....;)

Also ich habs glaube ich verstanden und zwar:
1.) Median ermitteln
2.) linker/rechter Randpunkt vergleichen hinsichtlich
links < Median && rechts > Median
3.) Wenn nicht erfüllt werden die Randpunkte miteinander vertauscht
4.) Prüfen ob der neue linke Randpunkt < Median ist, wenn nicht Element merken
5.) Prüfen ob der neue rechte Randpunkt > Median ist, wenn ja solange Arrayindex dekrementieren bis Gesetz verletzt ist
6.) Die beiden gespeicherten Elemente miteinander vertauschen
7.) Vorgang 1-6 solange wiederholen bis komplettes Array verarbeitet wurde
8.) Median wird nun mit dem rechten Randpunkt vertauscht
9.) Vorgang 1-7 wiederholen

Kurz:
- virtuelle Grenze Median
- Array wird in 2 Teilarray (1. < Median und 2. > Median)virtuell gesplittet und elementweise in Abhängigkeit vom Median verglichen. Passt ein Element nicht in die erwünschte Folge wird es ein Ersetzungskandidat

ghorst

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.

MFK

Schlumpfversteher schrieb:

Ob ich richtig liege....;)

Deine Liste sieht mehr oder weniger wie ein normaler Quicksort aus. Wenn du "Median-of-3" meintest, davon ist nichts zu sehen.

Beim Median of three wird der Median von drei Werten ermittelt: linkestes Element, Mitte, rechtestes Element. Dieser Median bildet dann das Pivot-Element.

Aber Achtung: diese Methode schützt nicht vollständig gegen die Struktur der Eingabedaten, googel mal nach "median of three killer sequences".

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-