14 lines
1.4 KiB
Plaintext
14 lines
1.4 KiB
Plaintext
Übungsblatt Sortierverfahren
|
|
|
|
Aufgabe 1: Sortieren Sie die Folge 5, 2, 8, 1, 9 mit Bubblesort. Notieren Sie nach jedem Durchlauf den Zustand der Folge und die Zahl der Vertauschungen. Nach Durchlauf 1: 2, 5, 1, 8, 9 (drei Vertauschungen). Nach Durchlauf 2: 2, 1, 5, 8, 9 (eine Vertauschung). Nach Durchlauf 3: 1, 2, 5, 8, 9 (eine Vertauschung). Durchlauf 4 bleibt ohne Vertauschung, das Verfahren endet.
|
|
|
|
Aufgabe 2: Zeigen Sie, dass Insertionsort auf einer Folge mit k Inversionen höchstens n minus 1 plus k Vergleiche benötigt. Hinweis: Jeder Vergleich, der zu einer Verschiebung führt, beseitigt genau eine Inversion.
|
|
|
|
Aufgabe 3: Führen Sie den Merge-Schritt für die sortierten Hälften 1, 4, 7 und 2, 3, 9 durch. Ergebnisfolge: 1, 2, 3, 4, 7, 9 mit fünf Vergleichen.
|
|
|
|
Aufgabe 4: Geben Sie für Quicksort mit Lomuto-Partitionierung und letztem Element als Pivot eine Eingabe der Länge 5 an, die den schlechtesten Fall erzeugt. Die bereits sortierte Folge 1, 2, 3, 4, 5 erzeugt Partitionen der Größen 4, 3, 2, 1 und damit quadratische Laufzeit.
|
|
|
|
Aufgabe 5: Bauen Sie aus der Folge 3, 7, 1, 9, 4 einen Max-Heap in Array-Darstellung. Ergebnis nach dem Heap-Aufbau: 9, 7, 1, 3, 4. Begründen Sie, warum der Aufbau von der Mitte an rückwärts in linearer Zeit gelingt.
|
|
|
|
Aufgabe 6: Welche der Verfahren Bubblesort, Insertionsort, Mergesort, Quicksort, Heapsort sind stabil? Stabil sind Bubblesort, Insertionsort und Mergesort; Quicksort und Heapsort sind nicht stabil.
|