Lektion 5: Sortieren

In dieser Lektion behandeln wir Algorithmen zum Sortieren einer Liste von Elementen.

Sortieren ist das vielleicht wichtigste Problem der Informatik mit vielfältigsten Anwendungen; eine Liste zuerst zu sortieren vereinfacht in vielen Fällen die weitere Verarbeitung. Aus den vielen Anwendungen ergeben sich eine Vielzahl von Anforderungsprofilen an gute Sortieralgorithmen, die kein Verfahren allein erfüllen kann; daher ist es wertvoll, die Vor- und Nachteile der verschiedenen Sortieralgorithmen zu verstehen.

Darüber hinaus lassen sich einige verwandte Probleme (z.B. zufälliges Permutieren und das Finden des Medians einer Menge) durch leicht abgewandelte Sortierverfahren lösen. Die Prinzipien der Algorithmen sind also über das Sortieren hinaus hilfreich.

Lernziele

• Funktionsweise und Charakteristika bekannter Sortieralgorithmen kennen
• auf Basis dieser ein geeignetes Sortierverfahren für eine Anwendung wählen können
• Priority Queues einsetzen können
• Denkweisen erlernen, um geforderte Performancecharakteristika als unmöglich zu entlarven (»untere Schranken«)

Fragensammlung für die Q&A Session

Tragt hier Fragen ein, die während der Vorbereitung aufkamen, und die ihr gerne klären möchtet. Bewertet außerdem die existierenden Fragen.

Hausordnung

• Es ist explizit erlaubt/erwünscht, Fragen aus den Aufgaben zur Vorbereitung unter den Videos zu übernehmen, wenn ihr diese der Q&A Session besprechen wollt.
• Auch wenn ihr gerade keine eigene Frage stellen möchtet, sind die Fragen der anderen oft hilfreiche Denkanstöße auch für euch. Deshalb, und um Fragen für die Q&A Sessions zu priorisieren, könnt ihr Fragen bewerten.
  Tragt dazu bei einer Frage entweder ein (zusätzliches) »+« ein, wenn ihr diese Frage interessant findet, oder ein (zusätzliches) »-«, wenn ihr sie nicht hilfreich findet (z.B. weil die Antwort direkt im Video gegeben wird). Listet zur besseren Übersicht zuerst alle »+«, dann alle »-«, jeweils in 5er Gruppen.
• Bevor ihr eine neue Frage eintragt, schaut ob eine existierende Frage eurer sehr nahe kommt; wenn ja, schreibt eure Frage als alternative Formulierung zu dieser Frage dazu.
• Wenn ihr der Meinung seid, ihr könnt eine Frage in wenigen Worten beantworten, so ergänzt eure Antwort unterhalb der Frage. Auch diese Antworten könnt ihr bewerten, wenn ihr sie hilfreich findet, oder Erwiderungen ergänzen, wenn ihr sie für falsch haltet.
• Seid konstruktiv.

Material

Zu dieser Lektion gehören recht viele Videos (viele davon sind recht kurz). Der Übersichtlichkeit halber sind sie in 4 Teile aufgeteilt:
Teil 1, Teil 2, Teil 3, Teil 4, optionale Themen.

Die Videos entstammen dem Coursera MOOC Algorithms Part I von Robert Sedgewick und Kevin Wayne.

Teil 1 – Einführung und Elementare Verfahren

Die erste Reihe von Videos beschreibt einfache, intuitive Verfahren zum Sortieren und verwandte Probleme.

1.1 – Sorting Introduction

Dieses Video beschreibt, was wir unter dem Problem »Sortieren« genau verstehen. Dabei wird Java's `Comparable`-Abstraktion eingeführt, die generische Sortiermethoden ermöglicht.

Aufgaben zur Vorbereitung:

1. Welche Methoden hat `Comparable`? Wie sieht eine Implementierung dieser Methoden aus (für eine Beispielklasse deiner Wahl)?
2. Welche Abstraktion führt Sedgewick darüber hinaus für seinen Code ein?
3. Müssen die zu sortierenden Elemente in einem Array vorliegen?

1.2 – Selection Sort

Dieses Video beschreibt Sortieren durch wiederholtes Suchen des Minimums.

Aufgaben zur Vorbereitung:

1. Welche Invariante erhält Selectionsort?
2. Wie viele Vergleiche und Swaps braucht Selectionsort?
3. Welche Eigenschaften der Eingabe beeinflussen die Kosten?

1.3 – Insertion Sort

Dieses Video beschreibt Sortieren durch Einfügen, den »Kartenspieleralgorithmus«.

Aufgaben zur Vorbereitung:

1. Welche Invariante erhält Insertionsort?
2. Wie viele Vergleiche und Swaps braucht Insertionsort?
3. Welche Eigenschaften der Eingabe beeinflussen die Kosten?
4. Was sind Inversionen?

1.4 – Shuffling

Eine Liste zufällig zu permutieren, sodass alle möglichen Reihenfolgen der Elemente gleich wahrscheinlich sind, ist ein typischer Baustein in (Monte-Carlo) Simulationen – und leicht falsch zu machen! Dieses Video zeigt, wie es richtig geht.

Aufgaben zur Vorbereitung:

1. Welche zwei Verfahren zum random shuffling werden vorgestellt?
2. Wie effizient sind sie?
3. Alle solche Verfahren müssen auf Zufallszahlen zugreifen können. Welche Arten von Zufallszahlen werden in den vorgestellten Verfahren verwendet?

Teil 2 – Mergesort und Theorie

Dieser Teil behandelt Mergesort, die informationstheoretische untere Schranke fürs Sortieren, sowie zwei Aspekte, die beim Sortieren von Objekten wichtig sind: selbst-definierte Ordnungsrelationen und Stabilität von Sortierverfahren.

2.1 – Mergesort

Dieses Video stellt Mergesort vor, neben Quicksort (s.u.) das wichtigste Verfahren in der Praxis.

Aufgaben zur Vorbereitung:

1. Was versteht man unter merging? Beschreibe die Idee anhand zweier Stapel von Papierdokumenten (sagen wir Rechnungen, die nach Datum sortiert werden). Welche Voraussetzungen muss die Eingabe erfüllen, und was gilt dann nach dem merge?
2. Wie wird aus merge der Mergesort?
3. Wie könnte man Mergesort statt als rekursive Methode mit einem Stack implementieren?
4. Wie viele Vergleiche verwendet Mergesort? Vergleiche die Anzahl für N=1000 mit der für Selectionsort.
5. Wie kann man diese Vergleichsanzahl mathematisch beweisen? Skizziere die verwendeten Methoden.
6. Welche Optimierungen von Mergesort schlägt Sedgewick vor?

2.2 – Sorting Complexity

In diesem Video wird bewiesen, dass eine gewisse Mindestanzahl von Vergleichen nötig sein muss, um korrekt sortieren zu können.

Das Argument selbst ist nicht besonders trickreich, liefert aber doch eine nicht-triviale Aussage: Es ist im Allgemeinen nicht möglich, mit einer fixen Anzahl von Durchläufen über eine Liste zu sortieren. Solche Aussagen bezeichnet man als untere Schranken (lower bounds) eines Problems (hier des Sortierens). Die Möglichkeit, solche starken, allgemeingültigen Unmöglichkeitsaussagen mathematisch zu beweisen, grenzt die (theoretische) Informatik klar von den Ingenieurswissenschaften ab, wo i.d.R. eine große Lücke zwischen Stand der Technik und harten physikalischen Grenzen verbleibt (z.B. Wirkungsgrad von Verbrennungsmotoren vs. Perpetuum Mobile)

Aufgaben zur Vorbereitung:

1. Was sind decision trees?
2. Was ist das decision tree model?
3. Was ist die präzise Aussage der informationstheoretischen unteren Schranke?
   • Für welche Algorithmen gilt die Aussage?
   • Für welche Eingabegröße N gilt die Aussage?
   • Für welche Eingaben einer gegebenen Größe N gilt die Aussage?
   • Welches Kostenmodell wird betrachtet? (Was heißt das für die Laufzeit?)
4. Was bedeutet das für Mergesort?

2.3 – Comparators

Dieses Video beschreibt die Comparator API in Java.

Hinweis: Das Beispiel am Ende (polar order, slide 47-48) bezieht sich auf eine Anwendungen des Sortierens (Berechnen von convex hulls mittels Graham scan), die wir hier nicht behandeln. Das Beispiel könnt ihr also ignorieren.)

Aufgaben zur Vorbereitung:

1. Welche Methoden hat das Interface Comparator?
2. Was sind Vorteile gegenüber dem Implementieren von Comparable?

2.4 – Stability

In diesem Video wird erklärt, was es heißt, dass ein Sortierverfahren stabil ist, und welche unserer Algorithmen diese Eigenschaft haben.

Aufgaben zur Vorbereitung:

1. Was ist Stabilität?
2. Für welche Anwendungen ist ein stabiles Sortierverfahren nötig? Gib ein Beispiel.
3. Welche uns bekannten Verfahren sind stabil?
4. Demonstriere an einem stabilen Algorithmus deiner Wahl, dass man Stabilität leicht einbüßen kann, wenn man Details im Code (unachtsam) ändert.

Teil 3 – Quicksort und Praxis

Teil 3 der Sortierlektion behandelt Quicksort, die schnellste Methode in der Praxis.

3.1 – Quicksort

Dieses Video stellt Quicksort vor.

Aufgaben zur Vorbereitung:

1. Was versteht man unter partitioning? Beschreibe die Idee anhand eines Stapels von Rechnungen mit Datum und eines Stichtages. Welche Voraussetzungen muss die Eingabe erfüllen, und was gilt dann nach dem partitioning?
2. Wie wird aus partitioning der Quicksort?
3. Wie könnte man Quicksort statt als rekursive Methode mit einem Stack implementieren?
4. Inwiefern hat Quicksorts Struktur Ähnlichkeit mit Mergesort? Was ist anders?
5. Wie viele Vergleiche verwendet der randomisierte Quicksort
   • minimal,
   • maximal,
   • in Erwartung?
6. Wie kann man die erwartete Vergleichsanzahl mathematisch beweisen? Skizziere die verwendeten Methoden.
7. Welche Optimierungen von Mergesort schlägt Sedgewick vor?

3.2 – Duplicate Keys

Dieses Video thematisiert den Effekt, den Elemente mit gleichem Schlüssel auf die Performance von Sortieralgorithmen haben. Es wird eine verallgemeinerte untere Schranke präsentiert, die mit 3-way Quicksort (fat-pivot Quicksort) in der Praxis erreicht werden kann.

Aufgaben zur Vorbereitung:

1. Wann sind zwei Elemente gleich bzgl. compareTo in Java?
2. In welchen Anwendungen ist mit vielen solchen Duplikaten zu rechnen?
3. Welchen Einfluss haben Duplikate auf die Anzahl Vergleiche in
   • Mergesort und
   • Quicksort (so wie bei Sedgewick implementiert)?
4. Was ist die Idee bei 3-way partitioning? Wie sieht die Invariante aus?
5. Was besagt die untere Schranke für Multimengen?
6. Nimm an, wir sortieren eine Liste mit 500 Frauen und Männern nach Geschlecht (♂ < ♀ und vereinfachend gebe es hier nur männlich und weiblich); wie viele Vergleiche sind dazu mindestens nötig? Mach eine Überschlagsrechnung! Wie viele Vergleiche würde Mergesort in etwa benötigen?
7. Was ist über die Anzahl Vergleiche von 3-way Quicksort bekannt?

3.3 – System Sorts

In diesem Video beschreibt Sedgewick die Sortiermethoden der Java Library und was für solche industrial-strength Implementierungen zu beachten ist.

Aufgaben zur Vorbereitung:

1. Welche API stellt Java zum Sortieren bereit?
2. Welche Eigenschaften von Sortierverfahren können in Anwendungen eine Rolle spielen?

Teil 4 – Priority Queues und Heapsort

In Teil 4 fügen wir unserer Liste von abstrakten Datentypen die Priority Queue hinzu, die in diversen Anwendungen und für spätere Algorithmen hilfreich ist. Auf Priority Queues basiert auch Heapsort, unser erster Sortieralgorithmus, der linearithmische Worst-Case Laufzeit garantiert und dabei ohne zusätzlichen Speicherplatz auskommt. Auch wenn Heapsort in der Praxis eine untergeordnete Rolle spielt, ist er Perle und Meilenstein der Algorithmik.

4.1 – Priority Queue API

Dieses Video definiert die API von Priority Queues und nennt einige ihrer Anwendungen. Es werden außerdem primitive Implementierungen der API vorgestellt, die aber den Laufzeitanforderungen der Anwendungen nicht gerecht werden.

Aufgaben zur Vorbereitung:

1. Welche Operationen bieten MaxPQ bzw. MinPQ
2. Warum verwendet der topM test client eine MinPQ um die M größten Transactions zu finden – ist das ein Fehler?
3. Welche elementaren Implementierungen werden vorgestellt? Welche Laufzeiten (order of growth) haben dann die PQ Operationen?

4.2 – Binary Heaps

In diesem Video wird die Datenstruktur binary heap präsentiert, mit der sich eine effiziente Priority Queue konstruieren lässt.

Hinweis: Die in manchen Anwendungen von PQs zusätzlich verwendeten Methoden, die erlauben, die Priorität von schon in der Queue befindlichen Elementen zu modifizieren, werden hier (noch) nicht besprochen.

Aufgaben zur Vorbereitung:

1. Was ist ein binary tree (Binärbaum) nach der Definition aus dem Video? Seid präzise und gebt Beispiele.
2. Was ist ein vollständiger Binärbaum? Wie viele topologisch verschiedene (d.h. ohne Labels der Knoten zu berücksichtigen) vollständige Binärbäume mit N Knoten gibt es?
3. Wann ist ein Binärbaum heap-ordered? Was bedeutet das für den Schlüssel in der Wurzel?
4. Wie repräsentiert Sedgewick einen vollständigen Binärbaum als Array? Warum geht das, ohne explizit zu speichern, wo die Kinder eines Knotens gespeichert sind?
5. Was tut die swim Operation im binary heap? Welche Bedingungen verlangt swim zu Beginn (Vorbedingungen, preconditions), und was ist nach Beendigung von swim sichergestellt (Nachbedingungen, postconditions)?
6. Was tut sink? Was sind die Vor- und Nachbedingungen?
7. Wie funktioniert insert für binary-heap MaxPQs?
8. Wie funktioniert delMax für binary-heap MaxPQs?
9. Welche Laufzeit (order of growth) haben die Operationen?
10. Was ist immutability? Was kann schiefgehen, wenn die Keys einer PQ nicht immutable sind?