Sortieralgorithmen auf Listen analysieren (nur LK)

In unserem Notizverwalter hatten wir das Problem, dass uns keine Methode zum Sortieren der Listen bekannt war. Mit Trick 17 haben wir es aber dann doch mit der Listenmethode sort(null) hinbekommen. Aber ist das eine guter Sortieralgorithmus? Ist er schnell und gründlich? Was macht einen guten Algorithmus eigentlich aus?

Untersuchungsprinzip und Hilfsmittel

Unsere Ergebnisse sind sehr subjektiv. Die Qualität des Sortierens hängt von vielen Faktoren ab. Gesucht ist daher eine Qualitätsbeschreibung, die unabhängig von Hardwareeigenschaften funktioniert. 

Dazu betrachten und implementieren wir verschiedene Sortieralgorithmen in drei Szenarien:

• best case: die Daten liegen in der korrekten Sortierung vor
• worst case: die Daten liegen in der umgekehrten Sortierung vor
• average case: die Daten liegen weder in best noch worst case vor

Anschließend erfolgt das Messen von Zeiten für unterschiedlich große Datenmengen in den drei Szenarien, die grafische Darstellung, eine Hypothesenbildung, eine rechnerischen Abschätzung und eine Prognose über die Effizienz des Algorithmus.

1. Sortierverfahren: „Sortieren durch Austausch“ – RippleSort und BubbleSort

Beginnen wir mit der Untersuchung eines bekannten Verfahrens, welches verbal und als Struktogramm vorliegt – RippleSort

Das erste Element der Liste wird schrittweise mit allen nachfolgenden Elementen verglichen. Ist das erste Element größer als das Vergleichselement, so werden die Elemente getauscht. Nach dem ersten Listendurchlauf steht das kleinste Element der Liste am Listenanfang. Nun wird das zweiten Element nach gleichen Prinzip schrittweise mit allen nachfolgenden Elementen verglichen und ggf. mit dem Vergleichselement getauscht. Nach dem zweiten Listendurchlauf steht das zweitkleinste Element der Liste fest. Der Algorithmus wird solange fortgesetzt, bis alle Elemente der Liste mit den nachfolgenden Elementen nach diesem Prinzip behandelt wurden.

Der Name leitet sich von denen wie kleine Wellen nach vorn schiebenden Elementen ab.

Eine grafische Darstellung des verbalen Algorithmus zeigt folgendes Struktogramm.

Auswertung der Untersuchung von RippleSort in BlueJ bzw. in einer Simulation

Die Auswertung legt die Vermutung nahe, dass es zwischen der Anzahl der Vergleiche und der Anzahl der Elemente einen quadratischen Zusammenhang gibt, denn:

• Erhöht sich die Anzahl der Elemente um den Faktor 10, so erhöht sich die Anzahl der Vergleiche ca. um den Faktor 100.
• Erhöht sich die Anzahl der Elemente um den Faktor 5, so erhöht sich die Anzahl der Vergleiche ca. um den Faktor 25.
• Erhöht sich die Anzahl der Elemente um den Faktor 2, so erhöht sich die Anzahl der Vergleiche ca. um den Faktor 4.

Das heißt aber auch, dass es wahrscheinlich einen quadratischen Zusammenhang zwischen der Gesamtzeit des Sortierens der Liste und der Anzahl der Elemente gibt. Stellt man dies grafisch dar, so kann man einen Parabelast vermuten.

Bildet man den Proportionalitätsfaktor, so untermauert dieser die Hypothesen: V(n ) ~ n² bzw. T(n ) ~ n²

Können wir dies erklären?

1. Beim ersten Durchlaufen wird das erste Element mit allen weiteren Elementen verglichen, also mit n – 1 Elementen. 
2. Beim zweiten Durchlauf wird das erste Element nicht mehr berücksichtigt, es wird das zweite Element mit den nachfolgenden verglichen, also mit n – 2 Elementen. 
3. Beim dritten Durchlauf wird ... bis zum letzten Element. 

Der gesamte Sortiervorgang ist also nach V(n ) = ((n – 1) + (n – 2) + ... + 2 + 1) Vergleichen beendet.
Die in der Formel enthaltene Summierung lässt sich mithilfe der Gaußschen Summenformel umschreiben zu
V(n ) = ½(n² - n) ≈ ½n².

Diese Überlegung kann man für den worst case auch für die Vertauschungen machen. Auch dort ergibt sich ein quadratischer Zusammenhang. Da jeder Vergleich und eine Vertauschung eine bestimmte Anzahl von Rechentakten benötigt, können diese als eine Abschätzung der Laufzeit eines Algorithmus unabhängig von der Taktfrequenz eines Prozessors verwendet werden. 

Die Laufzeit eines Algorithmus kann durch die Anzahl der für den Algorithmus notwendigen Elementaroperationen beschrieben werden.

In der Regel interessiert nicht die exakte Anzahl Elementaroperationen, sondern eine grobe Abschätzung mithilfe einer oberen Schranke. Man nutzt dazu Klassenbezeichnungen mithilfe des Landau-Symbols O. In unserem Fall liegt eine quadratische Funktion vor. Dies wird als O(n²) abgeschätzt und bedeutet, dass sich die Laufzeit des Algorithmus höchstens wie n² verhält. Damit haben wir einen Ausdruck, der die zeitliche Qualität eines Algorithmus beschreibt. 

RippleSort hat im worst, average und best case ein Laufzeitverhalten von O(n²).

Sortieren durch Austauschen zweier Elemente lässt sich aber auch noch anders realisieren – BubbleSort

Beim Durchlaufen der Liste werden die jeweiligen Nachbarelemente miteinander verglichen und ggf. ausgetauscht. Am Ende des ersten Laufs befindet sich das größte Element am Listenende. Dieser Vorgang wird nun erneut gestartet, allerdings diesmal bis zum vorletzten Element. Danach hat man das zweitgrößte Element gefunden. Der ganze Vorgang wird nun so oft wiederholt, bis die gesamte Liste sortiert ist.

Der Name leitet sich von Luftblasen ab, die je nach Größe nach oben steigen.

Unserer Implementation von RippleSort folgend, könnte BubbleSort ebenfalls durch zwei geschachtelte Zählschleifen realisiert werden, also so:

Die Analyse von best, worst und average case führt uns für diese Implementation zu einem Laufzeitverhalten von O(n²), welches sich in Analogie zu Ripplesort erklären lässt.

Unsere Implementierung hat aber noch Verbesserungspotential: Wird ein Durchlauf ohne jeglichen Tausch absolviert, so sind die Daten sortiert und der Sortiervorgang kann also beendet werden. Daher bietet sich statt einer Zählschleife eine weniger starre Schleife an, in deren Kopf dies als flexible Abbruchbedingung notiert werden kann. 

Damit erreicht BubbleSort im best case das Laufzeitverhalten von O(n ).

2. Sortierverfahren: „Sortieren durch Auswählen“ - SelectSort

3. Sortierverfahren: „Sortieren durch Einfügen“ - InsertSort

Zusammenfassung des Laufzeitverhaltens der bisher untersuchten Verfahren

Im worst case und (nicht näher untersuchten) average case liegt stets eine quadratische Laufzeit vor. Bedeutet dies, dass es keine besseren Sortieralgorithmen gibt oder müssen wir einfach nur einen anderen Denkansatz verwenden?

4. Sortierverfahren: „Sortieren durch Mischen“ - MergeSort

Das MergeSort-Verfahren nutzt das fundamentale informatische Prinzip „Teile und Herrsche“. 
Es findet eine Zerlegung des Problems der Größe n (Sortierung von n Elementen) in zwei Teilprobleme kleinerer Größe (Sortierung der Hälfte der n Elemente) statt, die jeweils gelöst und anschließend zu einer Gesamtlösung des Grundproblems zusammengesetzt werden.

Der prinzipielle Ablauf erfolgt in 3 Schritten:

1. Zerlegung der Menge in zwei Teilmengen
2. Sortierung der beiden Teilmengen
3. Mischen der Teilmengen zu einer Menge, wobei nur die beiden ersten Elemente der Teilmengen miteinander verglichen werden und das kleinere der beiden in die Gesamtmenge übernommen wird. Dieser Vorgang wird sooft wiederholt, bis keine Elemente mehr in den Teilmengen vorhanden sind. Sollte eine Teilmenge leer sein, können alle Elemente der anderen Teilmenge zur  Gesamtmenge hinzufügt werden. 

Dieser prinzipielle Ablauf wird jedoch rekursiv ausgeführt, d. h. die Zerlegung wird solange fortgesetzt, bis nur noch ein Element der Menge übrig ist. Dieses ist dann bereits sortiert und man kann die Rekursion mit dem Mischen auflösen.

Beispiel: 

Unsere Implementation besteht nun aus zwei Teilen. Dies ist dem rekursiven Algorithmus geschuldet. Zunächst das Struktogramm mit dem Teilen der Liste, dem rekursiven Aufrufen von Mergesort für die beiden Teillisten und das anschließende Zusammenfügen der sortieren Teillisten durch Mischen. 

Für das Mischen ist nachfolgendes Struktogramm zu nutzen. 

Untersuchung des Laufzeitverhaltens von MergeSort im worst-case

Mergesort zerlegt eine Liste wiederholt in zwei gleich große Teillisten, bis jede Teilliste nur noch ein Element enthält. Anschließend werden die Teillisten schrittweise wieder zu einer sortierten Liste zusammengeführt.

Für die Anzahl der Zusammenführungsebenen gilt:

• Um zwei Teillisten zu einer zu vereinen, ist eine Ebene notwendig.
• Um vier Teillisten zu einer zu vereinen, sind zwei Ebenen notwendig.
• Um acht Teillisten zu einer zu vereinen, sind drei Ebenen notwendig. usw.

Zwischen der Anzahl der Teillisten und der Anzahl der Ebenen besteht somit folgender Zusammenhang: Teillisten = 2^Ebenen. 
Durch Umstellen ergibt sich: Ebenen = log₂ Teillisten

Eine Ausgangsliste mit n Elementen wird in n Teillisten mit jeweils einem Element zerlegt. Für deren schrittweise Zusammenführung sind bei fortgesetzter Halbierung näherungsweise log₂ n Ebenen erforderlich. Auf jeder Ebene werden insgesamt n Elemente verarbeitet. Der Zeitaufwand für das Zusammenführen lässt sich daher pro Ebene mit O( n) abschätzen.

Aus der Anzahl der Zusammenführungsebenen und dem Aufwand pro Ebene ergibt sich die Zeitkomplexität von Mergesort: O(n·log₂n). 

Hinweis: In der Literatur wird häufig die Basis des Logarithmus weggelassen. Man meint den 2er-Logarithmus. 

Zusammenfassung des Laufzeitverhaltens der untersuchten Verfahren

Iterative und rekursive Algorithmen

Sowohl Iteration als auch Rekursion ermöglichen es, wiederkehrende Berechnungen oder Verarbeitungsschritte auszuführen.

	Iteration	Rekursion
Beschreibung	Wiederholung einer Anweisungsfolge mithilfe einer bedingten Schleife	Eine Funktion ruft sich selbst mit veränderten Parametern auf, bis ein Abbruchfall erreicht ist.
Prinzip	Schrittweise Wiederholung	Zerlegung des Problems in Teilprobleme (Teile und Herrsche)
Abbruch	Schleifenbedingung	Basisfall/Rekursionsabbruch
Beispiel	Berechnung der Fakultät durch fortlaufende Multiplikation 5! = 5 · 4 · 3 · 2 · 1 n! = n · (n-1) · (n-2) · … · 2 · 1	Berechnung der Fakultät durch Rückführung auf die Fakultät der vorhergehenden Zahl 5! = 5 · 4! n! = n · (n-1)! mit n (natürliche Zahlen) und 0! = 1
Struktogramm
Java	public int fak_iterativ(int n) {   int ergebnis = 1;   for (int i = n; i >= 1; i--) {     ergebnis = ergebnis * i;   }   return ergebnis; }	public int fak_rekursiv(int n) {   if (n == 0) {     return 1;   }   else {     return n * this.fak_rekursiv(n-1);   } }