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.

[jfheins]

Wenn das:
1 2 3 4 5 6 7 8 9
und das:
9 8 7 6 5 4 3 2 1
zu einer Worst-Case-Laufzeit führt, sollte das:
2 1 3 4 5 6 7 8 9
und das:
8 9 7 6 5 4 3 2 1
doch auch ein Worst-Case Verhalten provozieren, oder?

Edit: Oder eine dieser Folgen:

2 3 4 5 6 7 8 9 1

8 7 6 5 4 3 2 1 9

5 4 6 3 7 2 8 1 9

Ist doch gar nicht so schwer :stupid:

Die Bedingung ist ja im Grunde, dass bei einer beliebigen jeder Zahl alle Zahlen links davon entweder alle größer oder alle kleiner sind ;)

[Nikolas]

> Die Bedingung ist ja im Grunde, dass bei einer beliebigen Zahl alle Zahlen links davon entweder alle größer oder alle kleiner sind

Das hast du aber schön gesagt :shock: :mrgreen:

Jetzt seh ichs auch. Danke schön. Ich habe einfach übersehen, dass ich nach der Wahl jedes Pivotelements neu entscheiden darf, ob die Zahlen links davon alle größer sind, oder kleiner und diese Wahl nicht für alle gilt, was dann ausschließlich auf meine Lösungen geführt hat.

Vielen Dank

[jfheins]

Zitat:

Zitat von Nikolas

> Die Bedingung ist ja im Grunde, dass bei einer beliebigen Zahl alle Zahlen links davon entweder alle größer oder alle kleiner sind

Das hast du aber schön gesagt :shock: :mrgreen:

Jetzt seh ichs auch. Danke schön. Ich habe einfach übersehen, dass ich nach der Wahl jedes Pivotelements neu entscheiden darf, ob die Zahlen links davon alle größer sind, oder kleiner und diese Wahl nicht für alle gilt, was dann ausschließlich auf meine Lösungen geführt hat.

Vielen Dank

Freut mich, geholfen zu haben :)

Aber ich habe meine Aussage nochmal korrigiert, damit sie auch richtig ist :mrgreen:

Diese Fragen, die immer eine Antwort mehr fordern als offensichtlich sind, mag ich auch nicht gerne :mrgreen: