Zahlenfolgen, die zu n^2 Laufzeit beim Quicksort führen

**Nikolas**

Hallo

Ich bereite mich gerade auf meine Info2 Klausur vor und habe eine Frage gefunden, bei der ich erstmal keine Antwort habe:

Zitat:

Geben Sie drei unterschiedliche Zahlenfolgen der Länge 9 (mit den Elementen 1-9 ) an,
die bei der Sortierung mit Quicksort zu einer worst-case-Laufzeit f führen. (Als Pivotelement wird immer das Element am rechten Rand der Folge gewählt.)

Der Quicksort läuft um so schlechter, je ungleicher die beiden Teile nach einem Divide-Schritt sind. Im schlimmsten Fall habe ich also eine 'Hälfte' mit n-1 Elementen und eine mit einem Element. Das passiert sicher dann wenn ich eine sortierte Eingabe habe und Pivot wie angegeben wähle. Da es egal ist, ob die Folge aufsteigend oder absteigend sortiert ist, habe ich schon mal zwei Lösungen. (Jedenfalls, wenn man die Anzahl der Vergleiche zählt. Bei den Vertauschungen ist die in der richtige Reihenfolge sortierte Zahlenfolge deutlich besser).
Nur eine dritte fehlt mir.

Zahlenfolgen, die zu n^2 Laufzeit beim Quicksort führen

Zahlenfolgen, die zu n^2 Laufzeit beim Quicksort führen

Forumregeln