2 Quicksort, Pivotelement

Submitted by javafrage on Thu, 02/02/2012 - 18:02

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

Quicksort Lösung

 

Anonymous (not verified)

Tue, 06/02/2015 - 14:13

Permalink

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?

Für die Behandlung des Pivotelements gibt es unterschiedliche akzeptable Strategien. In der Musterlösung wurde wie folgt vorgegangen:

  • Beginne links im Sortierinterval und merke das erste Element welches größer-gleich als 5 ist.
    • Dies ist die 9. Halte mit der Suche an
  • Beginne rechts im Sortierinterval und suche (fallend) das erste Element welches kleiner als 5 ist.
    • Dies ist die 4. Halte mit der Suche an.
  • Tausche 4 mit 9

Setze die Strategie des Suchens von links und rechts fort

  • Vergleiche von links kommend das nächste Element (die 8) ob es größer gleich 5 ist und halte dann an.
  • Vergleiche von rechts kommend, fallend das nächste Element (die 3) ob sie kleiner ist als die 5 und halte dann an
  • Tausche 8 mit 3

Jetzt kommt es zum "Endspiel". Die beiden Zeiger der Suche von links und rechts treffen sich. Hier gibt es wieder Freiheitsgrade.

  • Man kann die 6 mit der 5 tauschen und dann die 5 aus den zukünftigen Suchintervallen ausschließen
  • Falls der Wert auf der fünften Position kleiner als das Pivotelement gewesen wäre hätte man es stehen lassen und die fünfte Position in das neue linke Sortierintervall einbezogen.