Deutsch
Menü

Datenstrukturen und Algorithmen

Welches Sortierverfahren hat auch im schlechtesten Fall die Komplexität O(n log n) und sortiert fast ohne zusätzlichen Speicher wie ein Arbeitsarray?

  1. AMergesort
  2. BHeapsort
  3. CQuicksort
Antwort und Erläuterung anzeigen

Antwort: B. Heapsort

Heapsort baut innerhalb des Arrays einen binären Heap auf, tauscht wiederholt das Maximum an der Wurzel mit dem letzten Element und verkleinert den Heap; es läuft daher auch im schlechtesten Fall in O(n log n) und braucht nur konstant viel zusätzlichen Speicher. Mergesort ist im schlechtesten Fall ebenfalls O(n log n), braucht auf einem Array aber einen Arbeitsbereich proportional zu n. Quicksort ist im Mittel O(n log n) und in der Praxis schnell, kann aber je nach Pivotwahl und Daten auf O(n²) absinken. Heapsort vergleicht allerdings weit auseinanderliegende Elemente, nutzt den Cache daher schlecht und ist auch nicht stabil.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. Die Datensätze (Name, Punktzahl) (A, 80), (B, 70), (C, 80), (D, 70) liegen in dieser Reihenfolge vor. In welcher Reihenfolge erscheinen die Namen, wenn mit einem stabilen Sortierverfahren aufsteigend nach Punktzahl sortiert wird?
  2. In welchem typischen Fall benötigt Quicksort O(n²) Zeit?
  3. Bei Mergesort werden die beiden sortierten Folgen 1, 4, 7, 9 und 2, 3, 8, 10 zu einer zusammengeführt (Merge), indem wiederholt die vordersten Elemente verglichen und das kleinere ausgegeben wird. Ist eine Folge leer, wird der Rest der anderen ohne Vergleich ausgegeben. Wie viele Vergleiche werden durchgeführt?
  4. Ein binärer Heap wird mit der Wurzel in a[0] in einem Array a[0], a[1], a[2], … gespeichert, wobei jede Ebene von oben beginnend von links nach rechts aufgefüllt wird. Welches sind die Kinder und der Elternknoten von a[4]?
  5. Ein Max-Heap, in dem der Wert jedes Elternknotens mindestens so groß ist wie die Werte seiner Kinder, wird in einem Array mit der Wurzel in a[0] gespeichert. Zum Heap 50, 30, 40, 10, 20, 35 wird 45 hinzugefügt, indem es ans Ende gesetzt und dann mit seinem Elternknoten vertauscht wird, solange es größer als dieser ist. Wie sieht das resultierende Array aus?