Warum ist die Laufzeit für das auf 3-Wege-Split basierende Quicksort in O(n*N)

Question

Erläutern Sie, warum die Laufzeit für das auf 3-Wege-Split basierende Quicksort in O(n*N) ist, wobei N die Anzahl der zu sortierenden Elemente und n die Anzahl der verschiedenen Schlüssel ist. Gehen Sie davon aus, dass der Algorithmus wie auch in der Vorlesung das letzte Element der Folge als Pivotelement wählt. Geben Sie außerdem eine unendliche Menge von Folgen an, so dass jeweils gilt: n<N/2 und die Laufzeit aus Ω(n*N).

Hoffentlich könnt ihr mir helfen, mir fällt hierzu nämlich gar nichts ein. = (

Comments

Der 3-Wege-Split unterscheidet sich dadurch, dass die Folge nicht in 2 sondern in 3 Teilfolgen geteilt wird. Daher müssen mindestens 2 Elemente die gleichen Schlüssel haben um Zeit zu sparen; wenn keine Schlüsel gleich sind, ist der Worst-Case-Fall identisch mit dem normalen Quicksort Alghorihtmus.

---

Klasse, vielen Dank! = )

---

Gerne, aber leider kann ich den zweiten Teil nicht.

---

Den kann ich leider auch nicht. :/ Ich hoffe der Rest reicht :D

---

Mal sehen, müsste aber ;)