Wählt man beim Quicksort das Pivotelement immer am gleichen Rand des Intervals, so gibt es Zahlenreihen die nur sehr ineffizient sortiert werden.
Für welche Zahlenreihen trifft dies zu? Geben Sie ein Beispiel an.
Die Antwort finden Sie auf der nächsten Seite (URL rechts unten klicken).
Niveau | 2 |
Schwierigkeitsgrad | mittel |
Zeit | 2 Minuten |
Antwort zu Frage 1: Quicksort
- Printer-friendly version
- Log in to post comments
- 5435 views
Lösung Quicksort
Wir sind nach mehreren anläufen jedes mal auf die Lösung "2 1 3 4 5 9 8 7 6" gekommen. Warum ist bei Ihnen die 3 und 4 bzw. die 9 und 8 vertauscht?
Antwort
Für die Behandlung des Pivotelements gibt es unterschiedliche akzeptable Strategien. In der Musterlösung wurde wie folgt vorgegangen:
Setze die Strategie des Suchens von links und rechts fort
Jetzt kommt es zum "Endspiel". Die beiden Zeiger der Suche von links und rechts treffen sich. Hier gibt es wieder Freiheitsgrade.