Quicksort: Wählen Sie als Pivotelement den Median der Folge! Habe ich den Median richtig gewählt?

Question

Hallo Community = ),

wir haben eine Zahlenfolge  8, 7, 3, 4, 5, 11, 9, 2, 10, 6 gegeben und sollen diese sortieren.

Das Sortieren ist einfach, mir geht es um den Median. Ich würde als Media (in dieser Aufgabe also das Pivotelement) die Zahl 5 in der Zahlenfolge wählen. Ist das richtig=?

NACHTRAG: Es geht mir also nur darum, ob ich den Median richtig gewählt habe. = )

Answer 1

Du hast einfach die Zahl aus der Mitte genommen.

Du musst aber die Liste erst sortieren und dann die

Mitte nehmen. Das gibt den Mittelwert

von 6 und 7 also 6,5 .

Comments

Hallo mathef, danke für deine Hilfe, ich habe es mal versucht, habe aber glaube ich noch einen Fehler drin, weil ich nicht mit Quicksort sortieren kann (Wir sollen als Pivotelement für Quicksort den Median der Folge wählen) =(

Hier ist mein Vorgehen:

Also zunächst sortieren: 2, 3, 4, 5, 6, 7, 8,9 10, 11
Mitte wäre 6.5, da 6.5 nicht in der Liste steht, muss ich die kleinere Zahl als Pivoelement nehmen, also die 6.

Allerdings kann ich die Liste jetzt nicht mehr mit Quicksort sortieren, weil sie schon  sortiert ist.

---

Wenn du den Median hast, (das sortieren war da ja

nur so eine Art Nebenrechnung) dann musst du wieder zur

ursprünglichen Liste zurück und die dann mit dem

gewählten Pivotelement sortieren.

---

Ach so,

also kann ich Quicksort nun mit dem Pivotelement 6 "durchführen", das wäre dann richtig?

Damit ich das richtig verstanden habe, wenn ich meinetwegen die Folge 1, 2, 3, 4, 5 , 10 habe, wäre der Median ca. 4,2 und als Pivotelement bei Quicksort müsste ich dann bei der gerade genannten Folge 4 nehmen, nicht wahr?

Danke, du hast mir sehr weitergeholfen = )

---

Aus derselben wikipedia-Quelle

• Alle Werte werden (aufsteigend) geordnet.
• Wenn die Anzahl der Werte ungerade ist, ist die mittlere Zahl der Median.
• Wenn die Anzahl der Werte gerade ist, wird der Median meist als arithmetisches Mittel der beiden mittleren Zahlen definiert, die dann Unter- und Obermedian heißen.

Da die Anzahl der Werte bei dir gerade ist ist der letzte Punkt zutreffend.
Für eine Verwendung in einem Quicksort ist das Arthemtische Mittel allerdings
ungeeignet.
Du mußt dich für den Unter- oder Obermedian entscheiden. 6 oder 7.
Wahrscheinlich ist beides gleich gut.

Damit ich das richtig verstanden habe, wenn ich meinetwegen die
Folge 1, 2, 3, 4, 5 , 10 habe, wäre der Median ca. 4,2 und als Pivotelement
bei Quicksort müsste ich dann bei der gerade genannten
Folge 4 nehmen, nicht wahr?

Nein. Du kannst den
3. Wert ( Untermedian ) = 3
oder
4.Wert ( Obermedian ) = 4
wählen.

Answer 2

der Median ist nichts was man wählen kann, den gilt es zu bestimmen zu berechnen.

Da die  Liste eine gerade Anzahl von Elementen hat ist der Median der Muttelwert aus Unter- und Obermedian:

https://de.wikipedia.org/wiki/Median

Die sind hier 5 und 6.

Answer 3

Ich denke das die 3-Median-Methode gemeint ist. Du nimmt das rechte, linke und mittlere Element und schaust welches das Mittelgrößte ist. In deinem Fall 8, 5, 6 (wenn du bei der Ermittlung der mittlere Position abrundest) oder 8, 11, 6 (wenn du aufrundest). Somit ist das Pivot im ersten Fall 6 und im zweiten 8.