Vorlesung Informatik 2 Algorithmen und Datenstrukturen (09 - Weitere Sortierverfahren)Prof. Th. Ottmann
Merge-Sort (2)
Der nicht-rekursive Einstieg in Merge-Sort:
static void mergeSort(char[] a){ int hi = a.length-1; mergeSort (a, 0, hi); // die rekursive Variante } // mergeSort
Das Zusammen-Mischen der Teilfolgen kann nicht im gleichen Array erfolgen.
Es wird ein Hilfs-Array in der Größe der Ergebnisfolge benötigt.
Merge-Sort (3)
private static void mergeSort (char[] a, int lo, int hi){ if (lo < hi) { // Grosses Problem: int m = (lo + hi +1)/2; // Divide mergeSort (a, lo, m-1); // Conquer links mergeSort (a, m, hi); // Conquer rechts // Merge nach char [] temp = new char[hi-lo+1]; // Hilfs-Array for (int i=0, j=lo, k=m; i hi) || (j < m) && (a[j] < a[k])) // lazy! temp[i++] = a[j++]; // von links else temp[i++] = a[k++]; // von rechts for (int i=0; i
Merge-Sort (4)
Aufwandsabschätzung:
Die Folgen werden in allen Fällen (best, worst, average) immer gleichmäßig aufgeteilt.
Das Zusammen-Mischen erfordert einen linearen Aufwand in der Länge der Ergebnisfolge.
Für die Laufzeit ergibt sich: und somit
Platzbedarf: Es wird ein zweites Array benötigt sowie Speicherplatz (Stack) zur Verwaltung der rekursiven Aufrufe.
Merge-Sort (5)
Optimierungsansätze:
Der Merge-Sort Algorithmus – wie angegeben – ist übersichtlich und leicht verständlich. Er kann aber zu Lasten dieser Eigenschaften weiter optimiert werden.
Wie bei Quicksort, könnten weitere einfache Fälle direkt behandelt werden.
Das ständige Neu-Generieren (und Verwerfen) von Hilfs-Arrays verbraucht unnötig Zeit. Effizienter ist die (Wieder-) Verwendung eines einzigen Arrays der gleichen Größe wie das Ausgangs-Array. Zudem kann man Kopier-Operationen einsparen.
Ist eine Teilfolge beim Mischen ausgeschöpft, kann der Rest der anderen ohne unnötige Abfragen umkopiert werden.
Bemerkungen zur Anwendung:
Im Vergleich zu anderen Internen Sortierverfahren schneidet Merge-Sort nicht so gut ab, weshalb es selten tatsächlich eingesetzt wird.
Gut an Merge-Sort ist sein garantiertes worst case Verhalten.
Varianten von Merge-Sort werden häufig beim Externen Sortieren eingesetzt.
Distribution-Sort (1)
Bisher betrachtete Sortierverfahren sind Allgemeine Verfahren: Die erlaubten Operationen sind Schlüsselvergleiche und Elementvertauschungen.
Allgemeine Sortierverfahren benötigen im worst case immer Zeit in Ω(n log n), bei einigen kann O(n log n) garantiert werden.
Distribution-Sort (Sortieren durch Fach-Verteilen) kommt ganz ohne Vergleiche aus.
Dafür ist ein Zugriff auf die Struktur des Schlüssels erlaubt.
Die zu sortierenden Elemente werden mehrfach nach jeweils einem Teil des Schlüssels in Fächer verteilt und wieder zusammengetragen.
Vorbilder sind klassische mechanische Sortieranlagen etwa für Briefe nach Postleitzahlen.
Distribution-Sort (2)
Nachteile:
Es ist nicht ganz leicht, das Vorbild (Fach-Verteilen von Briefen) überhaupt auf den Rechner zu übertragen.
Im konkreten Fall kann es schwer (oder sehr aufwendig) sein, das Verfahren an einen
bestimmten Sortierschlüssel anzupassen.
Vorteile:
Die besondere Effizienz des Verfahrens.
Die Laufzeit von Distribution-Sort ist linear in der Größe der Eingabe.
Wenn anwendbar, ist Distribution-Sort auch in der Praxis den bisherigen Verfahren überlegen.
Distribution-Sort (3)
Prinzip beim Sortieren von Briefen:
Die letzte Ziffer der Postleitzahl sei die aktuelle Ziffer.
Verteile alle Briefe in 10 Fächer mit Nummern 1, 2, . . . , 10 entsprechend der aktuellen Ziffer.
Lege alle Briefe unter Beibehaltung der bisherigen Ordnung zusammen.
Ist die aktuelle Ziffer die erste Ziffer, dann sind alle Briefe fertig sortiert. Ist das nicht der Fall, wird die Ziffer links der aktuellen Ziffer zur neuen aktuellen Ziffer, und es geht weiter bei Schritt 2
Probleme bei der Umsetzung:
Man muss beachten, wie der Schlüssel aufgebaut ist (Folge von Ziffern, Bytes, Bits, . . . ) und ob die Sortierung nach den Teilen eine Sortierung der Schlüssel ergibt.
Dies ist etwa für Zahlen in Zweierkomplement-Darstellung nicht gegeben, kann durch Anpassung aber erreicht werden.
Bei Schlüsselzerlegung in Bytes z.B. benötigt man 256 Fächer, wovon jedes im Prinzip alle Datensätze aufnehmen können muss.
Durch Vorinspektion kann aber die # der Datensätze für jedes Fach – und damit seine Index-Position im Array – ermittelt werden.
Distribution-Sort (5)
count: - … a b c d e f g h …
# 1 0 1 1 1 1 3 1 1 2 # 1 1 2 3 4 5 8 9 10 12 Distribution-Sort für char[] mit 256 Fächern (1 Durchgang):
static void distributionSort (char[] a){ int hi = a.length-1; char[] b = new char[hi+1]; // Hilfs-Array zum Umkopieren int[] count = new int[256]; // Zaehler, 0 initialisiert for (int i=0; i <= hi; i++) count[ (int) a[i] ]++; // Zeichen zaehlen in Fach for (int i=1; i < 256; i++) count[i] += count[i-1]; // Akkumulieren for (int i = hi; i >= 0; i--) // von hinten nach vorne: b[--count[ (int) a[i] ]] = a[i]; // umsortieren von a nach b System.arraycopy(b,0, a,0, hi+1); // Array b nach a kopieren } // distributionSort
Distribution-Sort (6)
Diskussion:
Der angegebene Algorithmus distributionSort interpretiert einzelne Zeichen (char) als Bytes, funktioniert also nur bei Codierungen im Bereich 0, . . . , 255.
Bei längeren Schlüsseln, die wirklich zerlegt werden müssen, sind entsprechend mehr Durchgänge erforderlich.
Die Anzahl der Durchgänge ist eine Konstante.
Pro Durchgang werden linear viele Operationen ausgeführt.
Die Komplexität des Verfahrens ist in O(n).
Die Bedingung einer Zerlegbarkeit der Schlüssel in Teile, deren Sortierung die Ordnung auf den Schlüsseln erhält, muss erfüllbar sein, damit das Verfahren angewandt werden kann, wie etwa bei – 5-stelligen positiven Zahlen (Postleitzahlen) – Strings der Länge 20 (fest, aber beliebig) – ganzen und reellen Zahlen (nach Anpassung)
Das Verfahren lässt sich noch weiter optimieren, etwa durch Vermeiden des Rückkopierens aus dem Hilfs-Array. Statt dessen wird in aufeinander folgenden Durchgängen die Rolle der beiden Arrays vertauscht.
Distribution-Sort (7)
Distribution-Sort für char[] mit 2 Fächern (8 Durchgänge, 1 pro Bit):
static void distributionSortBit (char[] a){ int hi = a.length-1; char[] b = new char[hi+1]; // Hilfs-Array zum Umkopieren for (int j=0; j< 8; j++){ // fuer jedes Bit des Schluessels: int[] count = new int[2]; // Zaehler, 0 initialisiert for (int i=0; i <= hi; i++) count[ (a[i]>>>j) & 1 ]++; // Zeichen zaehlen in Fach for (int i=1; i < 2; i++) count[i] += count[i-1]; // Akkumulieren for (int i = hi; i >= 0; i--) // von hinten nach vorne: b[--count[(a[i]>>>j) & 1]] = a[i]; // umsortieren: a -> b char[] h = a; a = b; b = h; // Array-Referenzen umsetzen } //for } // distributionSortBit
Distribution-Sort (8)
Distribution-Sort für char[] mit 2 Fächern (8 × 2 Durchgänge, ohne count-Array):
static void distributionSortBit2 (char[] a){ int hi = a.length-1; char[] b = new char[hi+1]; // Hilfs-Array zum Umkopieren for (int j=0; j< 8; j++){ // fuer jedes Bit j des Schluessels: for (int k=1, m=hi; k >= 0; k--) // fuer k in {1,0} for (int i = hi; i >= 0; i--) // i Zeiger in a: if ((a[i]>>>j & 1) == k) // j-tes Bit == k? b [m--] = a [i]; // umsortieren a->b char[] h = a; a = b; b = h; // Array-Referenzen umsetzen } //for } // distributionSortBit2
Auswahl von Sortier-Verfahren
Welches ist das beste?
Bei wenigen Datensätzen ( 1000) ist die Laufzeit kaum problematisch, das einfachste Verfahren kann bevorzugt werden (Insertion, Selection, Bubble, . . . ).
Sind die Daten fast sortiert, sollte ein Verfahren genommen werden, das Vorsortierung ausnutzt (Insertion, Bubble, . . . ).
Sind sehr viele zufällig sortierte Elemente häufig zu sortieren, ist der Aufwand zur Anpassung von Distribution-Sort gut investiert.
Will man möglichst flexibel bleiben und hat keine Angst vor dem worst case, kann man Quick-Sort einsetzen.
In den restlichen Fällen wird man Shell-Sort, Merge-Sort oder Heap-Sort wählen.
Comments