Vorlesung Informatik 2 Algorithmen und Datenstrukturen (09 - Weitere Sortierverfahren)Prof. Th. Ottmann
Vorlesung Informatik 2 Algorithmen und Datenstrukturen (09 - Weitere Sortierverfahren)
Prof. Th. Ottmann
Heap Sort (1)
Definition. Eine Folge F = (k1, k2, . . . , kn) von Schlüsseln ist ein (Max-) Heap, wenn für alle gilt: ki k2i und ki k2i+1.
Bsp: 1 2 3 4 5 6 7 g e f d b a c g f e b c d a Heap Sort:
Effizientes Verfahren zum Sortieren (auch im worst case in O(n log n))
Prinzip: Sortieren durch wiederholtes Auswählen des Maximums (ähnlich Selection Sort)
Besonderheit: Verwendung einer Datenstruktur Heap, welche die Bestimmung des Maximums effizient unterstützt
Heap-Bedingung
Heap Sort (2)
1 2 3 4 5 6 7 7 6 5 2 3 4 1 7 6 5 2 3 4 1 1 2 3 5 4 6 7 Veranschaulichung des Heaps durch Binär-Baum mit Positionsnummern:
Level i hat 2i Knoten (außer dem letzten)
Knoten sind von oben nach unten und von links nach rechts nummeriert.
Knoten i hat Knoten 2i als linken und Knoten 2i + 1 als rechten Nachfolger und Knoten als Vorgänger (falls jeweils vorhanden).
Aus der Heap-Bedingung ki k2i und ki k2i+1 folgt:
Das Maximum steht an der Wurzel (an Index 1) und kann sofort entfernt werden.
Doch wie erhält man wieder einen Heap für den Rest?
Heap Sort (3)
Das Element von der größten verbleibenden Index-Position wird nach Pos. 1 bewegt und dann versickert. Sobald wieder ein Heap entstanden ist, kann das nächste Maximum entfernt werden, bis der Heap leer ist. 1 4 5 3 6 2 1 4 5 3 6 2 a c d b f e f a d b c e 1 4 5 3 6 2 f c d b a e 1 4 5 3 2 1 4 5 3 2 d a b c e e a b c d 1 4 3 2 a d b c 1 4 3 2 a d b c 1 3 2 b a c 1 3 2 c a b d f e
Heap Sort (4)
Versickern bedeutet: Vertauschen mit dem größeren der Nachfolger, solange dieser größer als das zu versickernde Element ist.
Verfahren zum Versickern des ersten Elements in einem Array a in den Grenzen j und t:
private static void percolate (char[] a, int j, int t){ int h; while ((h=2*j) <= t){ // h: linker Nachfolger if (h < t && a[h+1] > a[h]) h++; // h: größerer Nachfolger if (a[h] > a[j]) { // versickern nötig? swap (a, h, j); // ja: vertauschen j = h; // und weiter } else break; // nein: fertig } } // percolate
Anzahl der Vergleiche und Vertauschungen, um ein Element in n Elemente zu versickern: O(log n)
Heap Sort (5)
static void heapSort (char[] a){ int j, hi = a.length-1; for (j = hi/2; j >= 1;) // alle Pos. j = [n/2] .. 1: percolate (a, j--, hi); // versickere im Array j ... N for (j = hi ; j > 1;) { // alle Pos. j = n ... 2: swap (a, 1, j); // vertausche Maximum nach j percolate (a, 1, --j); // versickere im Array 1 ... (j-1) } } // heapSort
Frage: Wie aufwendig ist der Heap-Aufbau durch iteriertes Versickern? Sortieren mit Hilfe eines Heaps:
Erst muss ein Heap erstellt werden.
Dann kann man immer wieder das jeweilige Maximum entnehmen.
Da bei n Elementen diejenigen mit den Positionen bereits die Heap-Bedingung erfüllen, kann man bei der Heap-Erstellung mit dem Versickern beim Element mit der Nr. beginnen.
Heap Sort (6)
Heap-Aufbau durch iteriertes Versickern: 0 20 1 21 2 2² k = 3 2k Knoten
Anzahl der Knoten insgesamt: n = 2k+1 - 1
Anzahl der Vergleiche zum Aufbau:
Der Heap-Aufbau erfolgt also in linearer Zeit.
Heap Sort (7)
Laufzeit für Heap Sort insgesamt: O(n log n).
Platzbedarf: n für das Array sowie zusätzlich: O(1).
Frage: Kann Heap Sort noch verbessert werden?
Beobachtungen:
Der konstante Faktor c des Verfahrens hängt von der Tiefe ab, um die versickert werden muss.
Im schlimmsten Fall wird immer das kleinste Element bis ganz unten versickert.
Auch die erwartete Tiefe beim Versickern ist hoch.
Pro Niveau, um das ein Element versickert wird, treten 2 Schlüsselvergleiche auf, um den größeren der Nachfolger zu bestimmen und um festzustellen, ob weiter versickert werden muss.
Verbesserungsidee:
Bestimme den größeren der Nachfolger eines Elementes mit einem Schlüsselvergleich.
Versickere auf jeden Fall (auch wenn das Element zu groß ist).
Unten angekommen, lasse das Element wieder aufsteigen, soweit nötig.
Bottom-Up Heap Sort (1)
Bemerkung:
Die gefundene Stelle für das Element stimmt mit derjenigen der Versickerungsprozedur überein.
Satz. Das verbesserte Verfahren Bottom-up Heapsort benötigt zum Sortieren einer Folge von n Schlüsseln im schlechtesten Fall nur 1.5 n log n + 2n Schlüsselvergleiche.
Im Mittel benötigt Bottom-up Heapsort nur n log n + O(n) Schlüsselvergleiche.
static void bottomUpheapSort (char[] a){ int j, hi = a.length-1; for (j = hi/2; j >= 1;) percolateb (a, j--, hi); // versickere (mod) von j bis hi for (j = hi ; j > 1;) { swap (a, 1, j); // größeres nach j percolateb (a, 1, --j); // versickere (mod) } } // bottomUpheapSort
Bottom-Up Heap Sort (2)
private static void percolateb (char[] a, int j, int t){ int h; while ((h=2*j) <= t){ // h: linker Nachfolger if (h < t && a[h+1] > a[h]) h++; // h: größerer Nachfolger swap (a, h, j); // tausche auf jeden Fall j = h; // und weiter } bubbleUp (a, j); // tausche wieder zurück wenn nötig } // percolateb private static void bubbleUp (char[] a, int j){ char x = a[j]; // Position für x gesucht for (; j > 1 && a[j/2] < x; j/=2) // bis nach oben, falls nötig: a [j] = a [j/2]; // ziehe Elemente herunter a[j] = x; // positioniere x } // bubbleUp
Quicksort (1) Sortieren durch Teilen
Divide-&-Conquer Prinzip
Sehr gute Laufzeit im Mittel, schlechte Laufzeit im worst case. Quicksort Eingabe: unsortierte Liste L
sortierte Liste if (|L| <= 1)
return L
else waehle Pivotelement p aus L
L< = {a in L | a < p}
L> = {a in L | a > p}
return
[Quicksort(L<)] + [p] + [Quicksort(L>)] Lin L< p p L> Quicksort Quicksort
Quicksort (2) Implementation
class QuickSort extends SortAlgorithm {
static void sort (Orderable A[]){
/* sortiert das ganze Array */
sort (A, 1, A.length-1);
}
static void sort (Orderable A[], int l, int r){
/* sortiert das Array zwischen Grenzen l und r */
if (r > l) { // mind. 2 Elemente in A[l..r]
int i = divide(A, l, r);
sort (A, l, i-1);
sort (A, i+1, r);
}
}
static int divide (Orderable A [], int l, int r) {
/* teilt das Array zwischen l und r mit Hilfe
des Pivot-Elements in zwei Teile auf und gibt
die Position des Pivot-Elementes zurueck */
...
}
} Eingliederung in ein Rahmenprogramm:
Quicksort (3) Der Aufteilungsschritt
divide(A; l; r):
- liefert den Index des Pivotelements in A
- ausführbar in Zeit O(r – l) l r
Quicksort (4) Implementation: Aufteilungsschritt
static int divide (Orderable A [], int l, int r) {
// teilt das Array zwischen l und r mit Hilfe
// des Pivot-Elements in zwei Teile auf und gibt
// die Position des Pivot-Elementes zurueck
int i = l-1; // linker Zeiger auf Array
int j = r; // rechter Zeiger auf Array
Orderable pivot = A [r]; // das Pivot-Element
while (true){ // "Endlos"-Schleife
do i++; while (i < j && A[i].less(pivot));
do j--; while (i < j && A[j].greater(pivot));
if (i >= j) {
swap (A, i, r);
return i; // Abbruch der Schleife
}
swap (A, i, j);
}
}
Quicksort (5) Analyse
Günstigster Fall: Schlechtester Fall: log n Tmin = O(n log n) n Tmax = O(n2)
Quicksort (6)
Die Wahl von w (das Pivot-Element) ist entscheidend für die Effizienz: Sind Fl und Fr annähernd gleich groß, resultiert Laufzeit in O(n log n).
Eine gute Wahl von w wäre ein mittleres Element, allerdings aufwendig zu bestimmen.
Ein einfacherer Ansatz ist die Wahl des (von der Größe her) mittleren von drei Elementen, die links, rechts und in der Mitte der Folge stehen. Dabei werden sie direkt schon sortiert, womit kleine Probleme (bis zur Größe 3) bereits gelöst sind.
Quicksort (7) Medium-of-Three Variante
private static void quickSort (char[] a, int lo, int hi){ int li = lo; int re = hi; int mid = (li+re)/2; if (a[li] > a[mid]) swap(a, li, mid); // Kleines Problem if (a[mid] > a[re] ) swap(a, mid, re); // und Vorsortieren if (a[li] > a[mid]) swap(a, li, mid); // per Bubble Sort if ((re - li) > 2){ // Großes Problem: char w = a[mid]; // Divide: do{ while (a[li] < w) li++; // suche li while (a[re] > w) re--; // suche re if (li <= re) swap (a, li++, re--); // vertausche } while (li <= re); // bis fertig if (lo < re) quickSort (a, lo, re); // Conquer links if (li < hi) quickSort (a, li, hi); // Conquer rechts } // Merge unnötig } // quickSort
Quicksort (8)
Laufzeit-Abschätzung:
Erfolgt die Aufteilung der Folgen jeweils gleichmäßig (best case), so gilt: T(n) = T(n/2) + O(n) und damit T(n) = O(n log n)
Im ungünstigsten Fall (worst case) liegt das Pivot-Element ganz links oder rechts: T(n) = T(1) + T(n - 2) + O(n) und dann T(n) = O(n2)
Mittelt man über sämtliche Permutationen von n Schlüsseln und nimmt an, dass die Wahl des Pivot-Elementes immer zufällig erfolgt (average case), so ergibt sich für die Anzahl von Schlüsselvergleichen:
Merge-Sort (1)
Merge-Sort ist wie Quicksort ein Divide-&-Conquer Verfahren, anders als dieses aber mit simplem Divide- und komplizierterem Merge-Schritt.
Die Datensätze der zu sortierenden Folge werden, wenn sie nicht klein genug zum direkten Sortieren sind, in zwei annähernd gleich große Teilfolgen aufgeteilt.
Die Teilfolgen werden nach dem gleichen Verfahren sortiert.
Anschließend werden die sortierten Teilfolgen zusammengemischt (merge).
Beim Mischen müssen jeweils nur die ersten Elemente beider Folgen verglichen werden, das kleinere wird entfernt und kommt in die Ergebnisfolge.
Ist eine der Teilfolgen ganz ausgeschöpft, müssen die restlichen Elemente der verbleibenden Teilfolge nur noch umkopiert werden.
Eine Teilfolge mit nur einem Element ist bereits sortiert.
Comments