Bestimmen Sie den 22-t kleinsten Schlussel mitels der Median der Mediane Strategie.

Question

Hallo, hier die komplette Afugabenstellung:

Bestimmen Sie den 22-t kleinsten Schlussel mitels der Median der Mediane Strategie. Sobald eine Folge weniger als 7 Elemente hat, soll der i-t kleinste Schlussel direkt bestimmt werden. Achten Sie darauf, die Aufteilung in Teilfolgen wie bei Quicksort zu machen. Achten Sie weiterhin darauf, dass Ihr Lösungsweg nachvollziehbar aufgeschrieben ist.

Gegeben ist folgende Folge:

15 1 25 7 22 16 0 3 5 21 23 9 17 19 13 6 10 26 2 14 20 4 24 11 8 18 12 27

Ich habe dann den Median der Mediane bestimmt: v=18

Dann habe ich die Folge mit Quicksort in zwei Teilfolgen F1 und F2 mit v=18 als Pivotelement geteilt:

15 1 12 7 8 16 0 3 5 11 4 9 17 14 13 6 10 2 18 19 20 23 24 21 22 26 25 27

F1 enthält 18 Elemente mit Schlüsseln < v = 18. Ich muss also rekursiv in F2 den 22-18=4-t kleinsten Schlüssel suchen.

Median der Mediane von F2: 25

Dann habe ich die Folgen wieder in zwei Teilfolgen F1' und F2' mit v=25 als Pivotelement geteilt:

19 20 23 24 21 22 25 26 27

Da F1' jetzt nur noch 6 Elemente enthält die kleiner als 25 sind, soll ich nun laut Aufgabestellung das i-t kleinste Element (In meinem Fall das 4. kleinste) direkt bestimmen. Soll ich nun einfach die Folge sortieren und dann das Element an Index 3 zurückgeben?

Answer 1

Wieso stellst du deine Frage nicht im Illias System?

Du musst nicht den 22-18. Schlüssel sondern den
22-(18+1). Schlüssel suchen (schau in unserem Skript oder denke kurz selbst drüber nach)
Du hast ja nicht nur die 18 Elemente die kleiner sind als das Pivot-Element weggeworfen
sondern auch das Pivot-Element selbst.

Edit:
Und zur Rückgabe:
Einfach sagen was das 22. kleinste Element ist.
Nicht den Index, so hat er es ja auch im Vorlesungbsp gemacht.
In was für ein Index das Element steht geht nicht aus der Vorlesung hervor
und kommt auf die konkrete Umsetzung an.

Comments

Stimmt, du hast Recht! Hatte total vergessen, dass es ja noch ein Forum im ILIAS gibt :D Danke.