In diesem Kapitel wollen wir einige ausgewählte Algorithmen vorstellen und deren Umsetzung in Java zeigen. Das Ziel ist dabei das Kennenlernen von Basisalgorithmen, die als Grundlage für erste praktische Übungen dienen können. Besonders geeignet für diese Zwecke sind naturgemäß Verfahren zum Suchen und Sortieren, da diese Problemstellungen allen vertraut sind und die klassischen Verfahren auch ohne besondere Grundkenntnisse verständlich sind. Darüber hinaus wollen wir anhand dieser Algorithmen die theoretischen Betrachtungen der nächsten Kapitel vorbereiten, indem wir den Begriff der Komplexität einführen.
In diesem Kapitel (und den folgenden) werden wir eine Mischung aus Pseudocode-Notation und der Notation imperativer Algorithmen zur abstrakten Beschreibung von Algorithmen verwenden. Zusätzlich werden wir immer noch jeweils eine Java-Implementierung angeben, wobei jedoch nicht die Eleganz oder Wiederverwendbarkeit der Lösung im Mittelpunkt steht, sondern eine einfache und leicht verständliche Fassung. Später im Kapitel zu den Datenstrukturen werden wir Implementierungen behandeln, die allgemeiner einsetzbar sind.
Eine der häufigsten Aufgaben in der Informatik ist das Suchen von Daten. Es gibt hierzu eine Vielzahl von Verfahren für die unterschiedlichsten Aufgaben. Wir wollen zunächst nur den einfachsten Fall betrachten: Das Suchen in sortierten Folgen. Natürlich könnten wir auch auf das Suchen in unsortierte Folgen eingehen, allerdings werden wir sofort sehen, dass hier nicht viel zur Verbesserung der Suche getan werden kann.
Suchen in sortierten Folgen
Ein typisches Beispiel für das Problem des Suchens in sortierten Folgen ist das Finden eines Eintrags im Telefonbuch. Ein Telefonbuch enthält eine Folge von Einträgen aus Namen und Telefonnummern, wobei die Einträge nach den Namen geordnet sind.
Zur Vereinfachung gehen wir im Weiteren von einigen Annahmen aus. Eine Folge wird als Feld von numerischen Werten repräsentiert und auf ein einzelnes Element der Folge F kann über den Index i (notiert als F[i] mit 1 ≤ i ≤ n) zugegriffen werden. Das erste Element ist demnach F[1], das letzte entsprechend Element F[n]. Weiterhin sind für die Feldelemente die bekannten Vergleichsoperatoren =, < und > definiert. Wir betrachten also nur den für die Suche relevanten Teil eines Eintrags – den Suchschlüssel. Ein derartiger Schlüssel entspricht in unserem Telefonbuchbeispiel dem Namen eines Teilnehmers. Allerdings stellt die Beschränkung auf den Schlüssel kein wirkliches Problem dar, da die zusätzlichen Elemente keinen Einfluss auf die eigentliche Suche haben.
Die einfachste Variante des Suchens ist nahe liegend: Wir durchlaufen einfach die Folge sequenziell beginnend mit dem ersten Element. In jedem Schritt vergleichen wir das aktuelle Element mit dem Suchschlüssel. Sobald das gesuchte Element gefunden wurde, können wir die Suche beenden. Andernfalls wird als Ergebnis ein spezielles Element NO_KEY zurückgegeben. In Algorithmus 5.1 ist die sequenzielle Suche in Pseudocode-Notation angegeben. Da die einzige Vergleichsoperation der Test auf Gleichheit ist, funktioniert dieses Verfahren auch bei unsortierten Folgen.
algorithm SeqSearch (F, k) → p
Eingabe: Folge F der Länge n, Suchschlüssel k
Ausgabe: Position p des ersten Elementes aus F,
das gleich k ist, sonst NO_KEY
for i := 1 to n do
if F[i] = k then
return i
fi
od;
return NO_KEY
Aufwand
Durchschnittlicher Aufwand
Eines der wichtigsten Kriterien für die Beurteilung von Suchverfahren ist der Aufwand. Wir können den Aufwand einfach anhand der Anzahl der notwendigen Schritte mit den Vergleichen bestimmen, die in unserem Fall der Anzahl der Schleifendurchläufe entspricht. Sinnvollerweise betrachten wir diesen Aufwand nicht absolut, sondern in Abhängigkeit von der Länge n der Folge. Im besten Fall – das gesuchte Element ist gleich das erste in der Folge – benötigen wir nur einen Schritt, im schlechtesten Fall – das gesuchte Element ist nicht in der Folge enthalten – natürlich n Schritte. Interessanter ist jedoch der Durchschnittswert. Gehen wir davon aus, dass jedes Element gleich oft gesucht wird, so sind im Fall einer erfolgreichen Suche (n + 1)/2 Schritte notwendig, da ja der Suchschlüssel an jeder Position zwischen 1 und n auftreten kann. Bei einer erfolglosen Suche bleibt es natürlich beim schlechtesten Fall (Tabelle 5–1).
Tab. 5–1 Aufwand der sequenziellen Suche bei einer Folge der Länge n
|
Anzahl der Vergleiche |
bester Fall |
1 |
schlechtester Fall |
n |
Durchschnitt (erfolgreiche Suche) |
(n + 1)/2 |
Durchschnitt (erfolglose Suche) |
n |
Betrachten wir nun die Implementierung des vorgestellten Suchverfahrens in Java. Wir gehen dabei weiter von der bereits getroffenen Annahme aus, dass wir in Folgen von Zahlen suchen.
Repräsentation einer Folge
Entsprechend den Java-Konventionen ist zunächst eine Klasse – in unserem Fall die Klasse SeqSearch – zu definieren. Die Suchverfahren werden jeweils als eine Klassenmethode implementiert. Hinzu kommt noch die Methode main, die als »Hauptprogramm« den Testrahmen für unsere Suchmethoden bildet. Als Datenstruktur für die Repräsentation einer Folge verwenden wir der Einfachheit halber ein Feld (Array) von int-Werten. Wir werden später in Kapitel 13 noch andere Datenstrukturen kennen lernen, die mit nahezu beliebigen Objekte umgehen können und dadurch flexibler einsetzbar sind.
Eine Besonderheit gegenüber unserer bisher verwendeten Pseudocode-Notation ist, dass die Zählung der Feldelemente in Java bei 0 beginnt (siehe auch Abschnitt 2.5.2). Mit diesem Wissen lässt sich der Suchalgorithmus nun einfach in Java umsetzen (Programm 5.1).
public class SeqSearch {
public final static int NO KEY = − 1;
static int search(int[ ] array, int key) {
for (int i = 0; i < array.length; i++)
if (array[i] == key)
return i;
}
public static void main(String[ ] args) {
if (args.length != 1) {
System.out.println("usage: SeqSearch <key>");
return;
}
int[ ] f = { 2, 4, 5, 6, 7, 8, 9, 11 };
int k = Integer.parseInt(args[0]);
System.out.println("Sequenziell: " + search(f, k));
}
}
In der Klasse SeqSearch ist eine Konstante NO_KEY definiert, die als Ergebnis zurückgegeben wird, wenn der gesuchte Wert nicht im Feld gefunden wurde.
Die Methode search wird schließlich in der Klassenmethode main aufgerufen, um das Feld f nach dem Schlüsselwert k zu durchsuchen. Dieser Wert ist als Parameter beim Programmaufruf anzugeben. Da die Programmparameter als Feld args von Zeichenketten übergeben werden, ist zuvor noch eine Konvertierung in einen int-Wert mithilfe der Methode parseInt der Klasse java.lang.Integer vorzunehmen. Somit bedeutet der Programmaufruf
> java SeqSearch 4
die Suche nach dem Wert 4 in der gegebenen Folge.
Binäres Suchen
Es ist leicht einzusehen, dass das sequenzielle Durchsuchen nicht die beste Variante ist. Schließlich würde niemand in einem Telefonbuch die Einträge von vorn beginnend systematisch mit dem gesuchten Namen vergleichen. Vielmehr schlägt man das Buch auf, vergleicht, ob sich der gesuchte Eintrag vor oder hinter der aktuellen Stelle befindet, überspringt wieder einige Seiten, vergleicht wieder usw. Der zu durchsuchende Bereich wird auf diese Weise immer halbiert – daher heißt dieses Verfahren auch binäres Suchen. Voraussetzung dafür ist aber, dass die Folge sortiert vorliegt! Wir können den Algorithmus somit wie folgt grob beschreiben:
Iterative Variante
Mittleres Element
Es gibt nun verschiedene Varianten der Realisierung. Wir werden an dieser Stelle nur die iterative Variante vorstellen. Algorithmus 5.2 zeigt das Vorgehen. Es werden zwei Variablen u und o benötigt, die die untere und obere Grenze des zu durchsuchenden Bereichs der Folge darstellen. Aus diesem Bereich wird zunächst der Index m des mittleren Elementes bestimmt. Anschließend wird der Wert des mittleren Elementes F[m] mit dem Suchschlüssel verglichen. Ist der Schlüssel kleiner als das mittlere Element, so müssen wir im linken Bereich weitersuchen, d.h., wir setzen die obere Grenze o auf den Index des mittleren Elementes und fahren fort. Andernfalls müssen wir in der rechten Teilfolge weitersuchen, indem wir die untere Grenze u auf m setzen.
Die Suche ist beendet, wenn entweder der Wert des Elementes F[m] gleich dem Suchschlüssel oder u ≥ o ist, d.h., wenn der Suchbereich keine Elemente mehr enthält.
algorithm BinarySearch (F, k) → p
Eingabe: Folge F der Länge n, Suchschlüssel k
Ausgabe: Position p des ersten Elementes aus F,
das gleich k ist, sonst NO_KEY
u := 1, o := n;
while u < = o do
m := (u + o)/2;
if F[m] = k then
return m
else if k < F[m] then
o := m − 1
else
u := m + 1
fi
od;
return NO_KEY
Das Prinzip soll anhand eines Beispiels verdeutlicht werden. Wir gehen von der sortierten Folge in Abbildung 5–1 aus und suchen nach dem Element 8. Die untere Grenze u ist zunächst 1, die obere Grenze o wird auf 10 gesetzt. Daraus ergibt sich für die mittlere Position entsprechend 5. Da der Suchschlüssel größer als das Element an dieser Position ist, müssen wir in der rechten Hälfte weitersuchen. Für den nächsten Schritt wird demnach u := 6 und m := 8 gesetzt. Da 8 kleiner als das Element F[8] ist, wird der Suchbereich auf den linken Teil ([6, 7]) eingeschränkt, wo das gesuchte Element schließlich gefunden wird.
Abb. 5–1 Binäres Suchen in einer sortierten Folge
Rekursive Variante
Die rekursive Variante des binären Suchens kann leicht abgeleitet werden, indem als Parameter des Algorithmus die unteren und oberen Grenzen des zu durchsuchenden Bereiches übergeben werden und anstelle der Aktualisierung der oberen bzw. unteren Grenze der Algorithmus mit den neuen Bereichsgrenzen ausgeführt wird.
Aufwand
Durchschnittlicher Aufwand
Auch für dieses Verfahren beurteilen wir den Aufwand wieder anhand der Schleifendurchläufe, da in jedem Durchlauf eine konstante Anzahl von Operationen ausgeführt wird. Im günstigsten Fall befindet sich das gesuchte Element in der Mitte der Folge und wird daher nach einem Schritt gefunden. Im schlechtesten Fall müssen wir jedoch nicht die gesamte Folge durchsuchen. Nach dem ersten Teilen der Folge bleiben nur noch n/2 Elemente, nach dem zweiten Schritt n/4, nach dem dritten n/8 usw. Allgemein bedeutet dies, dass im i-ten Durchlauf maximal n/2i Elemente zu durchsuchen sind. Entsprechend werden log2n Schritte benötigt. Diesen Wert können wir auch als Durchschnittswert sowohl bei erfolgreicher als auch erfolgloser Suche angeben (Tabelle 5–2).
Tab. 5–2 Aufwand der binären Suche bei einer Folge der Länge n
|
Anzahl der Schritte |
bester Fall |
1 |
schlechtester Fall |
≈ log2n |
Durchschnitt (erfolgreiche Suche) |
≈ log2 n |
Durchschnitt (erfolglose Suche) |
≈ log2n |
Auch für dieses Verfahren wollen wir abschließend wieder die Java-Implementierung betrachten (Programm 5.2).
public class BinSearch {
public final static int NO_KEY = − 1;
static int search(int[ ] array, int key) {
int u = 0, o = array.length − 1;
while (u <= o) {
int m = (u + o) / 2;
if (array[m] == key)
return m;
else if (array[m] > key)
o = m − 1;
else
u = m + 1;
}
return NO_KEY;
}
public static void main(String[ ] args) {
if (args.length != 1) {
System.out.println("usage: BinSearch <key>");
return;
}
int[ ] f = { 2, 4, 5, 6, 7, 8, 9, 11 };
int k = Integer.parseInt(args[0]);
System.out.println("Binär: " + search(f, k));
}
}
Die Klasse BinSearch ist eine direkte Umsetzung des Algorithmus. Wie schon bei der sequenziellen Suche ist die eigentliche Suche als Klassenmethode implementiert, die von der main-Methode aufgerufen wird.
Tab. 5–3 Vergleich des Aufwandes der Suchverfahren
Interpolationssuche
Eine Variante der binären Suche ist die Interpolationssuche, mit der versucht wird, Wissen über die potenzielle Lage des Suchschlüssels im Suchbereich auszunutzen. Dazu wird nicht jeweils einfach die mittlere Position für den Vergleich gewählt wird, sondern es wird die Position anhand des Suchschlüssels und der unteren und oberen Werte interpoliert. Für einen Suchwert v kann die Position m in der Folge F danach wie folgt berechnet werden:
Offensichtlich funktioniert dies am besten bei einer Gleichverteilung der Werte in der Folge.
Die obige Berechnungsvorschrift kann direkt in den Algorithmus der binären Suche eingesetzt werden. Betrachten wir dazu ein Beispiel: Gegeben sei wieder die in Abbildung 5–1 dargestellte Folge. Für den Suchschlüssel 5 wird im ersten Schritt m wie folgt bestimmt:
Da der Wert von F[4] kleiner als der gesuchte Wert ist, ergeben sich u := 4 und o := 10. Im nächsten Schritt bestimmen wir
und der gesuchte Wert wird auf der Position F[5] gefunden. Bei einer Suche nach dem Schlüssel 4 berechnet sich die Position nach
und wir finden den gesuchten Wert sogar sofort.
Das Beispiel der binären Suche sollte auch verdeutlichen, dass bereits eine einfache Verbesserung eines Algorithmus zu einem drastischen Effizienzgewinn führen kann. So sind in Tabelle 5–3 die Anzahl der Vergleiche für unterschiedliche Eingabegrößen sowohl für die sequenzielle als auch die binäre Suche dargestellt. Es lohnt sich daher durchaus, auch bei vermeintlich einfachen Problemen nach einer besseren Lösung zu suchen.
Datensätze
Ordnung der Schlüssel
Duplikate
Ein weiteres grundlegendes Problem in der Informatik neben dem Suchen ist das Sortieren. So entfällt nach [OW17] ca. 1/4 der kommerziell verbrauchten Rechenzeit auf Sortiervorgänge. Die Aufgabe besteht hierbei im Ordnen von Dateien mit Datensätzen, die Schlüssel enthalten. Die Datensätze sind derart umzuordnen, dass eine klar definierte Ordnung der Schlüssel – entweder numerisch oder auch lexikographisch – entsteht. Das Problem der Sortierung stellt sich in vielen Anwendungen. So haben wir im vorigen Abschnitt gesehen, dass die Suche viel effizienter realisiert werden kann, wenn die zu durchsuchende Folge sortiert vorliegt. Es kann daher durchaus sinnvoll sein, die Datensätze zuvor zu sortieren und danach binär zu durchsuchen. Auch das Erkennen von mehrfach auftretenden Elementen (sogenannte Duplikate) ist in sortierten Folgen viel einfacher.
Bei den folgenden Betrachtungen der verschiedenen Verfahren bleiben wir bei unserer Vereinfachung, nur die Schlüssel zu berücksichtigen sowie als Schlüssel int-Werte anzunehmen.
Interne Verfahren
Externe Verfahren
Bevor wir auf konkrete Verfahren zum Sortieren eingehen, wollen wir zunächst einige Grundbegriffe klären. Grundsätzlich muss beim Sortieren zwischen zwei Klassen von Verfahren unterschieden werden. Interne Verfahren kommen beim Sortieren von Hauptspeicherstrukturen wie Felder oder Listen zum Einsatz. Voraussetzung für den Einsatz dieser Verfahren ist demnach, dass die zu sortierende Folge in den Hauptspeicher passt. Ist dies nicht gewährleistet, so werden externe Verfahren angewendet, die Datensätze auf externen Speichermedien wie Festplatte oder Magnetband sortieren. Speziell in Datenbanksystemen, die Datenmengen im Bereich von Giga- oder Terabytes verwalten können, werden solche Verfahren eingesetzt.
Stabilität
Ein weiteres Merkmal von Sortierverfahren ist die Stabilität. Ein Verfahren heißt stabil, wenn es die relative Reihenfolge gleicher Schlüssel in der Datei beibehält.
Nehmen wir eine Liste mit Daten zu Personen an, die alphabetisch nach den Namen sortiert ist. Wird diese Liste nun nach dem Alter der Personen sortiert, so werden bei Anwendung eines stabilen Verfahrens Personeneinträge mit dem gleichen Alter auch weiterhin alphabetisch geordnet sein.
Eine erste Variante – auch bekannt als InsertionSort – ergibt sich aus der direkten Umsetzung der typischen menschlichen Vorgehensweise, etwa beim Sortieren eines Stapels von Karten:
Sortieren im Stapel
Dieses Prinzip kann natürlich auch an das Sortieren im Stapel angepasst werden, indem beginnend bei der zweiten Position die jeweilige Karte aus dem Stapel entnommen und die neue Einfügeposition gesucht wird.
Angewendet auf die Aufgabe, eine Folge von Zahlen der Länge n zu sortieren, bedeutet dies, dass ein Element zu »merken« ist. Dadurch wird eine Position in der Folge frei, die genutzt werden kann, um alle Elemente, die größer als das gemerkte Element sind, eine Position nach rechts zu verschieben. In Algorithmus 5.3 wird eine Variable m zum »Merken« verwendet. Das Verschieben erfolgt ausgehend von der aktuellen Position j rückwärts bis zum ersten Element. Ist das Element F[j−1] kleiner oder gleich dem gemerkten Element, wird die innere Schleife verlassen. Durch das Verschieben »nach rechts« wird die Position j in der Folge frei, an der das gemerkte Element eingefügt werden muss.
algorithm InsertionSort (F)
Eingabe: zu sortierende Folge F der Länge n
for i := 2 to n do
m :=F[i];/* zu merkendes Element */
j := i;
while j > 1 do
if F[j − 1] ≥ m then
/* Verschiebe F[j − 1] eine Position nach rechts */
F[j] := F[j − 1];
j := j − 1
else
Verlasse innere Schleife
fi
od;
F[j] := m /* j zeigt auf Einfügeposition */
od
In Abbildung 5–2 ist das Prinzip dieses Sortierverfahrens anhand der Folge 5, 1, 8, 3, 9, 2 dargestellt. Beginnend mit dem zweiten Element (hier 1) wird jeweils ein Element in der Variablen m zwischengespeichert. Alle Elemente links dieses Elementes, die größer sind (im ersten Schritt 5), werden um eine Position verschoben. Nach dem ersten Schritt ist demnach die erste Position frei, so dass dort das Element 1 abgelegt werden kann. Im zweiten Schritt wird das Element 8 zwischengespeichert. Da jedoch alle Elemente links davon kleiner sind, findet keine Verschiebung statt.
Abb. 5–2 InsertionSort am Beispiel
Anhand des Algorithmus 5.3 kann das Verfahren direkt in eine Java-Implementierung überführt werden (Programm 5.3). Wir bleiben dabei zunächst bei der Beschränkung auf das Sortieren von int-Feldern.
static void insertionSort(int[ ] array) {
for (int i = 1; i < array.length; i++) {
int j = i;
int m = array[i];
// für alle Elemente links vom Marker-Feld
while (j > 0 && array[j − 1] > m) {
// verschiebe alle größeren Element nach hinten
array[j] = array[j − 1];
j −− ;
}
// setze m auf das freie Feld
array[j] = m;
}
}
Auswählen
Auch das zweite hier zu betrachtende Verfahren kann dem Sortieren beim Kartenspielen entlehnt werden. Die Idee ist hierbei, jeweils das größte Element auszuwählen und an das Ende der Folge zu setzen. Dies wird in jedem Schritt mit einem jeweils um eins verkleinerten Bereich der Folge ausgeführt, so dass sich am Ende der Folge die bereits sortierten Elemente sammeln (Algorithmus 5.4). Das Prinzip des Auswählens oder Selektierens des größten Elementes hat diesem Verfahren auch den Namen SelectionSort gegeben.
algorithm SelectionSort (F)
Eingabe: zu sortierende Folge F der Länge n
p := n;
while p > 0 do
g := Index des größten Elementes aus F im Bereich 1… p;
Vertausche Werte von F[p] und F[g];
p := p − 1
od
Das Prinzip des SelectionSort soll wieder anhand einer Beispielfolge illustriert werden (Abbildung 5–3). Der betrachtete Bereich der Folge ist dabei jeweils gerahmt dargestellt. So wird im ersten Schritt die gesamte Folge untersucht. Das größte Element (hier: 9) wird so mit dem Element 2 getauscht. Im nächsten Schritt wird die um eins verkürzte Folge betrachtet und das Element 8 ausgewählt. Dies erfolgt so lange, bis nur noch ein einzelnes Element übrig bleibt.
Abb. 5–3 SelectionSort am Beispiel
Für die Implementierung des SelectionSort ist es zunächst sinnvoll, eine Hilfsmethode swap zum Vertauschen zweier Feldelemente zu implementieren (Programm 5.4).
static void swap(int[ ] array, int idx1, int idx2) {
int tmp = array[idx1];
array[idx1] = array[idx2];
array[idx2] = tmp;
}
static void selectionSort(int[ ] array) {
int marker = array.length − 1;
while (marker > = 0) {
// bestimme größtes Element
int max = 0;
for (int i = 1; i < = marker; i++)
if (array[i] > array[max])
max = i;
// tausche array[marker] mit diesem Element
swap(array, marker, max);
marker −− ;
}
}
Mithilfe dieser Methode kann das eigentliche Suchverfahren einfach implementiert werden. Die Variable marker wird dabei wie die Variable p in Algorithmus 5.4 als Marker für die Obergrenze des zu betrachtenden Bereiches verwendet und in jedem Schleifendurchlauf dekrementiert.
Eines der bekanntesten, wenn auch kein besonders effizientes Sortierverfahren ist BubbleSort. Der Name ist aus der Vorstellung abgeleitet, dass sich bei einer vertikalen Anordnung der Elemente der Folge verschieden große, aufsteigende Blasen (»Bubbles«) wie in einer Flüssigkeit von allein sortieren, da die größeren Blasen die kleineren »überholen«.
Vertauschen benachbarter Elemente
Das Grundprinzip besteht demzufolge darin, die Folge immer wieder zu durchlaufen und dabei benachbarte Elemente, die nicht der gewünschten Sortierreihenfolge entsprechen, zu vertauschen. Elemente, die größer als ihre Nachfolger sind, überholen diese daher und steigen zum Ende der Folge hin auf.
algorithm BubbleSort (F)
Eingabe: zu sortierende Folge F der Länge n
do
for i := 1 to n − 1 do
if F[i]> F[i + 1] then
Vertausche Werte von F[i] und F[i + 1]
fi
od
until keine Vertauschung mehr aufgetreten
Optimierung
Der Algorithmus 5.5 weist schon eine Verbesserung gegenüber der ursprünglichen Idee auf, indem die Folge nicht n · n-mal durchlaufen wird, sondern der Abbruch bereits dann erfolgt, wenn keine Vertauschung mehr stattgefunden hat. Eine weitere Optimierung basiert auf der Beobachtung, dass in jedem Durchlauf das jeweils größte Element an das Ende bewegt wird. Daher genügt es, im zweiten Durchlauf nur den Bereich 1 … n − 2, im dritten Durchlauf den Bereich 1 … n − 3 usw. zu betrachten. Schließlich kann auch noch »Lokalität« von Feldzugriffen speziell bei großen Folgen ausgenutzt werden, indem der Durchlauf abwechselnd auf- bzw. abwärts erfolgt. So kann die Effizienz der Sortierung dadurch verbessert werden, dass Teile der Folge noch im CPU-Cache – einem schnellen Zwischenspeicher des Prozessors – vorhanden sind, wenn ein neuer Durchlauf gestartet wird.
Auch hier wollen wir zunächst ein Beispiel betrachten, bevor wir auf die Umsetzung in Java eingehen. Im ersten Durchlauf müssen die jeweils benachbarten Elemente 5, 1 sowie 8, 3 und 9, 2 vertauscht werden (Abbildung 5–4). Danach ist die Folge jedoch noch nicht vollständig sortiert, so dass im zweiten Durchlauf die Paare 5, 3 und 8, 2 vertauscht werden. Im dritten Schritt wird dann 5, 2 und im letzten Schritt schließlich noch 3, 2 getauscht. An diesem Beispiel wird noch einmal das »Bubble«-Prinzip deutlich: Das Element 2 als eine kleine »Blase« wird von den größeren Elementen allmählich überholt.
Auftreten von Vertauschungen
Bei der Umsetzung des Algorithmus in ein Java-Programm ist als Besonderheit nur zu beachten, dass es in Java keine do… until-Anweisung gibt. Stattdessen kann hier die do… while-Anweisung verwendet werden. Allerdings ist dabei die Bedingung zu negieren, da dies ja ein »Wiederhole-solange« bedeutet. Zur Verfolgung des Auftretens von Vertauschungen wird in Programm 5.5 weiterhin eine boolesche Variable swapped genutzt, die bei jedem Schleifendurchlauf zunächst mit false initialisiert wird und erst bei einer Vertauschung auf true gesetzt wird. Das eigentliche Vertauschen erfolgt wieder mithilfe der bereits eingeführten Methode swap.
Abb. 5–4 BubbleSort am Beispiel
static void bubbleSort(int[ ] array) {
boolean swapped;
do {
swapped = false;
for (int i = 0; i < array.length − 1; i++) {
if (array[i] > array[i + 1]) {
// Elemente vertauschen
swap(array, i, i + 1);
swapped = true;
}
}
// solange Vertauschung auftritt
} while (swapped);
}
Die bisher vorgestellten Verfahren erfordern einen direkten Zugriff auf einzelne Elemente der Folge und sind daher nur für internes Sortieren geeignet. Sollen dagegen Dateien sortiert werden, die nicht in den Hauptspeicher passen, müssen andere Verfahren zum Einsatz kommen. Eine Möglichkeit ist hier, das Sortieren in zwei Schritten oder Phasen auszuführen:
Sortieren in zwei Schritten
Rekursive Anwendung
Mischen
Dieses MergeSort-Verfahren lässt sich aber auch für das interne Sortieren anwenden. Hierbei wird zunächst die zu sortierende Folge in zwei Teilfolgen zerlegt, diese werden durch rekursive Anwendung von MergeSort sortiert und anschließend gemischt. Es stellt sich jedoch die Frage, wie man dabei zu sortierten Teilfolgen kommt. Dies wird dadurch erreicht, dass MergeSort so lange rekursiv angewendet wird, bis die zu sortierenden Teilfolgen nur noch aus einem Element bestehen. In diesem Fall liefert das Mischen ja eine neue, sortierte Folge.
Betrachten wir zunächst den Schritt des Mischens (Algorithmus 5.6). Wir nehmen dabei zur Vereinfachung an, dass Folgen ein einfaches Anhängen bzw. Entfernen von Elementen erlauben. Später bei der Implementierung werden wir auch auf die Umsetzung mithilfe von Feldern eingehen.
procedure Merge (F1, F2) → F
Eingabe: zwei zu sortierende Folgen F1, F2
Ausgabe: eine sortierte Folge F
F := leere Folge;
while F1 und F2 nicht leer do
Entferne das kleinere der Anfangselemente aus F1 bzw. F2;
Füge dieses Element an F an
od;
Füge die verbliebene nichtleere Folge F1 oder F2 an F an;
return F
Abbruchkriterium
Mithilfe des Algorithmus 5.6 kann nun das eigentliche Sortieren rekursiv realisiert werden. Das Abbruchkriterium in Algorithmus 5.7 ist eine einelementige Folge, die nicht mehr sortiert werden muss und daher unverändert zurückgegeben wird. Andernfalls wird die Folge zunächst in zwei Teile F1 und F2 aufgeteilt, die sortiert werden. Die Ergebnisse werden schließlich mittels Merge gemischt.
algorithm MergeSort (F) → FS
Eingabe: eine zu sortierende Folge F
Ausgabe: eine sortierte Folge FS
if F einelementig then
return F
else
Teile F in F1 und F2;
F1 := MergeSort (F1);
F2 := MergeSort (F2);
return Merge (F1, F2)
fi
Der Vorgang des Mischens erfordert in der Regel doppelten Speicherplatz, da ja eine neue Folge aus den beiden sortierten Folgen erzeugt wird. Eine Alternative ist das Mischen in einem Feld, allerdings ist hier ein aufwendigeres Verschieben notwendig.
Split
Merge
Abbildung 5–5 demonstriert das Vorgehen beim MergeSort. Zunächst wird die zu sortierende Folge in zwei Teile (5, 1, 8) und (3, 9, 2) zerlegt. Durch die rekursiven Aufrufe werden diese Folgen weiter geteilt, bis nur noch einelementige Folgen vorliegen (Abschnitt »Split«).
Im zweiten Abschnitt »Merge« werden die sortierten Teilfolgen gemischt: Zunächst also 5 und 1 sowie 3 und 9. Diese Folgen werden dann weiter mit 8 bzw. 2 und schließlich miteinander gemischt.
Es sei noch einmal betont, dass die Aufteilung in die zwei Abschnitte »Split« und »Merge« nur durch die Rekursion im Algorithmus entsteht, indem zu Beginn jeweils das Zerlegen erfolgt und erst als letzter Schritt das eigentliche Mischen.
Mischen mit Hilfsfeld
Für eine Implementierung des Verfahrens zum Sortieren von Feldern sind die in Algorithmus 5.6 skizzierten Operationen »Entfernen« und »Anfügen« nicht sonderlich gut geeignet. Während das Zerlegen noch auf einfache Weise durch Zeiger auf Anfang und Ende des jeweiligen Teilfeldes realisiert werden kann, erfordert das Mischen ein Hilfsfeld, in das die neu sortierte Folge eingetragen wird.
Abb. 5–5 MergeSort am Beispiel
Die Implementierung aus Programm 5.6 nutzt dieses Prinzip. Da bei jedem Aufruf die Unter- bzw. Obergrenze des aktuellen Feldes übergeben werden müssen, ist die eigentliche Sortierroutine in der Methode msort implementiert, die von der Methode mergeSort aufgerufen wird. In msort werden zunächst die Mitte (mid) des Feldes anhand der aktuellen Grenzen le und ri bestimmt und anschließend die beiden Teilfelder durch den rekursiven Aufruf von msort sortiert.
// Hilfsmethode für rekursives Sortieren durch Mischen
static void msort(int[ ] array, int le, int ri,
int[ ] helper) {
int i, j, k;
if (ri > le) {
// zu sortierendes Feld teilen
int mid = (ri + le) / 2;
// Teilfelder sortieren
msort(array, le, mid, helper);
msort(array, mid + 1, ri, helper);
// Hilfsfeld aufbauen
for (k = le; k <= mid; k++)
for (k = mid; k < ri; k++)
helper[ri + mid − k] = array[k + 1];
// Ergebnisse mischen über Hilfsfeld
i = le; j = ri;
for (k = le; k < = ri; k++)
if (helper[i] < helper[j])
array[k] = helper[i++];
else
array[k] = helper[j −− ];
}
}
static void mergeSort(int[ ] array) {
int helper[ ] = new int[array.length];
msort(array, 0, array.length − 1, helper);
}
Im nächsten Schritt werden die beiden Teilfelder über das Hilfsfeld helper gemischt. Dieses Feld ist exakt so groß wie das zu sortierende Feld. Es wird nur einmal in der mergeSort-Methode angelegt und als Parameter der Hilfsmethode msort übergeben. Die Elemente aus dem linken Teilfeld werden dabei auch in die linke Hälfte des Hilfsfeldes kopiert, entsprechend die Elemente aus dem rechten Teilfeld in die rechte Hälfte – hier jedoch abwärts sortiert. Anschließend werden die beiden Teilfelder aus dem Hilfsfeld gemischt und das Ergebnis in das eigentliche Feld eingetragen. Zum Vergleich der jeweils kleinsten Elemente werden zwei Zeiger i und j verwendet, wobei i beim ersten Element beginnt und aufwärts zählt bzw. j vom letzten Element abwärts läuft. Durch diese Vorgehensweise sind die beiden Zeiger nach dem Kopieren in das Hilfsfeld bereits richtig positioniert und wandern so nach innen zur Mitte.
Das wohl am häufigsten angewandte Sortierverfahren ist QuickSort, das wie MergeSort auf dem Prinzip »Teile und herrsche« basiert: Eine Folge wird in zwei Teile zerlegt, die unabhängig voneinander sortiert werden. Im Gegensatz zu MergeSort wird jedoch bei QuickSort der Mischvorgang vermieden. Dadurch benötigt dieses Verfahren weniger Ressourcen.
Pivot-Element
Die Grundidee von QuickSort ist die Zerlegung der Folge in zwei Teile, wobei alle Elemente der einen Teilfolge kleiner als ein Referenzelement (das sogenannte Pivot-Element) und alle Elemente der anderen Teilfolge größer als das Referenzelement sind. Das Pivot-Element kann beliebig gewählt werden. Typischerweise wird das mittlere Element der Folge verwendet, es kann aber auch das erste oder das letzte Element genutzt werden. Abbildung 5–6 illustriert die Rolle des Pivot-Elementes: Alle Elemente links von 6 sind kleiner oder gleich 6, alle Elemente rechts davon größer.
Abb. 5–6 Pivot-Element beim QuickSort
Die beiden Teilfolgen werden durch den rekursiven Aufruf sortiert. Das Verfahren bricht für eine Teilfolge ab, wenn diese die Länge 0 hat. Da das Pivot-Element gegebenenfalls verschoben werden muss – beispielsweise wenn es das kleinste oder größte Element der Folge darstellt – ist die beim Zerlegen bestimmte und eventuell neue Position pn des Pivot-Elementes zu berücksichtigen (Algorithmus 5.8).
algorithm QuickSort (F, u, o)
Eingabe: eine zu sortierende Folge F,
die untere und obere Grenze u, o
if o > u then
Bestimme Position p des Pivot-Elementes;
pn := Zerlege(F, u, o, p);
QuickSort (F, u, pn − 1);
QuickSort (F, pn + 1, o)
fi
Zerlegen der Folge
Der entscheidende Schritt ist demnach das Zerlegen der Folge. Hierfür wird die folgende Strategie verwendet: Nachdem wie bereits angedeutet die Position p des Pivot-Elementes festgelegt wurde, werden die Elemente so umgeordnet, dass alle Elemente, die kleiner oder gleich dem Pivot-Element sind, links davon stehen. Dazu wird zunächst das Pivot-Element mit dem am rechten Ende der Folge stehenden Element getauscht, um Platz beim Verschieben zu schaffen (Algorithmus 5.9). Anschließend wird die Folge von links durchlaufen. Ist ein Element kleiner oder gleich dem Pivot-Element wird es nach vorn getauscht, wobei die Position durch die Variable pn bestimmt wird, die nach jedem Tausch inkrementiert wird. Am Ende des Durchlaufs zeigt pn damit auch genau auf die neue Position des Pivot-Elementes, das nun an diese Stelle zurückgetauscht werden kann.
algorithm Zerlege (F, u, o, p) → pn
Eingabe: zu zerlegende Folge F, untere und obere Grenze u, o,
Position p des Pivot-Elementes
Ausgabe: neue Position pn des Pivot-Elementes
pn := u;
pv := F[p];
Tausche F[p] und F[o]; // Pivot-Element nach rechts
for i := u to o − 1 do
if F[i] ≤ pv then
Tausche F[pn] und F[i];
pn := pn + 1;
fi
od
Tausche F[o] und F[pn]; // Pivot-Element zurück
return pn
In Abbildung 5–7 ist das Prinzip noch einmal verdeutlicht. Für die gegebene Folge wird zunächst das mittlere Element (hier 5) als Pivot-Element gewählt und mit dem am Ende stehenden Element getauscht. Danach wird die Folge so umgeordnet, dass sich »links« vom Pivot-Element die Elemente 2, 1, 3 befinden, wobei die neue (und in diesem Fall gleichzeitig auch die alte) Position des Pivot-Elementes 4 ist. Nach dieser Zerlegung wird das Pivot-Element an diese Stelle zurückgetauscht und es ergibt sich der in Ebene 0 dargestellte Aufbau der Folge (2, 1, 3, 5, 9, 7, 8).
Im nächsten Schritt werden die beiden entstandenen Partitionen weiter sortiert. Im linken Teil wird das Element 1 als Pivot-Element bestimmt, im rechten Teil das Element 7. Daraus resultiert die für Ebene 1 angegebene Zerlegung, wobei die Pivot-Elemente in beiden Fällen verschoben werden.
Anschließend ergibt die Zerlegung der linken Partition, dass nur noch die Folge (3, 2) sortiert werden muss: Hier wird 3 als Pivot-Element bestimmt und nach den Vertauschungen liegt die Reihenfolge (2, 3) vor. Nachdem die letzte Partition (2) nur noch aus einem Element besteht, ist die Sortierung für diesen Zweig beendet. Im rechten Teil wird noch einmal für die Folge (8, 9) das Pivot-Element bestimmt und nach der Zerlegung ist auch dieser Zweig fertig sortiert.
Die tatsächliche Sortierung erfolgt jedoch nicht so symmetrisch, wie die Darstellung in Abbildung 5–7 vermuten lässt. Vielmehr wird aufgrund der Rekursion zuerst der linke Zweig des Baumes bis zur Folge (2, 3) verfolgt und erst danach wird die rechte Partition nach dem gleichen Prinzip verarbeitet.
Abb. 5–7 QuickSort am Beispiel
Für die Implementierung verfahren wir wie beim MergeSort: Die eigentliche Sortierung erfolgt über eine Hilfsmethode (hier qsort), die zwei Zeiger u und o als Parameter für die Unter- bzw. Obergrenze des zu verarbeitenden Bereiches nutzt. In dieser Methode wird zunächst die Position p des Pivot-Elementes bestimmt. Anschließend wird die Methode partition aufgerufen, die den Algorithmus 5.9 implementiert und die neue Pivot-Position pn liefert. Der Tausch der Elemente erfolgt durch Nutzung der bereits bekannten swap-Methode. Sind beide Partitionen entsprechend aufgeteilt, werden sie durch erneuten Aufruf von qsort sortiert. Die Grenzen der Partitionen werden dabei durch u bzw. o und die neue Pivot-Position bestimmt.
// Hilfsmethode zum Zerlegen der Folge
static int partition(int[ ] array, int u, int o, int p) {
int pn = u;
int pv = array[p];
// Pivot-Element an das Ende verschieben
swap(array, p, o);
for (int i = u; i < o; i++)
if (array[i] <= pv)
swap(array, pn++, i);
// Pivot-Element an die richtige Position kopieren
swap(array, o, pn);
// neue Pivot-Position zurückgeben
return pn;
}
// Hilfsmethode zum rekursiven Sortieren
static void qsort(int[ ] array, int u, int o) {
// Pivot-Element bestimmen
int p = (u + o) / 2;
if (o > u) {
// Feld zerlegen
int pn = partition(array, u, o, p);
// und Partitionen sortieren
qsort(array, u, pn−1);
qsort(array, pn+1, o);
}
}
static void quickSort(int[ ] array) {
qsort(array, 0, array.length − 1);
}
Die vorgestellte Implementierung ist nur eine der möglichen Umsetzungen. In der einschlägigen Literatur sind eine Vielzahl von weiteren Varianten beschrieben, so auch andere Strategien zur Bestimmung des Pivot-Elementes, das Verhalten beim Auffinden eines Elementes, das gleich dem Pivot-Element ist, sowie iterative Varianten.
RadixSort
Alphabet
Radix
Alle bisher betrachteten Verfahren basieren auf dem Vergleich von Elementen. Ein alternativer Ansatz wird mit dem RadixSort-Verfahren verfolgt, das auch als DistributionSort bekannt ist. Die Grundidee ist dabei das Verteilen der Elemente. Dazu müssen die zu sortierenden Elemente aus Zeichen eines endlichen Alphabets bestehen, für die eine totale Ordnung definiert ist. Ein einfaches Beispiel hierfür sind natürliche Zahlen als Elemente (Schlüssel): Die Zeichen des Alphabets sind dann die Ziffern 0 bis 9. Der Name »Radix« (lateinisch für Wurzel) bezeichnet die Basis eines Stellenwertsystems – in unserem Beispiel der natürlichen Zahlen als Schlüssel ist die Basis bekanntermaßen 10.
Histogramm
Das RadixSort-Verfahren läuft schrittweise ab, wobei in jedem Schritt eine Stelle (in unserem Fall Ziffer) der Elemente behandelt wird. Pro Schritt wird zunächst ermittelt, wie viele Elemente pro Zeichen vorhanden sind. Dies kann entweder erfolgen, indem die Elemente entsprechend ihrem jeweiligen Stellenwert partitioniert, d.h. in Fächer oder Listen eingeordnet werden. Alternativ kann auch ein Histogramm (die Darstellung einer Häufigkeitsverteilung) über den Zeichen des Alphabets konstruiert werden. Anhand dieses Histogramms kann dann für jedes Element ermittelt werden, an welche Stelle es hinsichtlich der aktuellen Sortierung bewegt werden muss. Die Histogramm-Variante vermeidet die Verwaltung zusätzlicher Listen, daher betrachten wir im Weiteren diese Idee. Abbildung 5–8 illustriert das Vorgehen anhand einer Beispielfolge.
Im ersten Schritt (obere Zeile) wird die letzte Ziffer jedes Elementes betrachtet und es ergeben sich für die vier vorkommenden Ziffern folgende Häufigkeiten: 1 mit 2 Elementen (891 und 251), 2 mit 1 Element (692), 3 mit 3 Elementen (543, 123, 243), 8 mit 1 Element (138). Mit dieser Information können nun die Elemente an die richtige Position bewegt werden: 543 gehört zur 3 und muss damit an die Position 4 (Anzahl der Elemente von 1 + Anzahl der Elemente von 2 + 1), 123 gehört ebenfalls zur 3 und damit an die Nachfolgeposition 5. 891 gehört zur 1 und muss damit auf die Position 1. In der Abbildung sind die Zielpositionen bereits mit angegeben.
Im zweiten Schritt (zweite Zeile) wird nun die vorletzte Ziffer betrachtet. Auch hier wird wieder ein Histogramm für die Ziffern 2, 3, 4, 5 und 9 konstruiert. Darauf aufbauend muss die 891 an die Position 1 + 1 + 2 + 1 + 1 = 6 (Anzahl der Elemente von 2, 3, 4, 5 und 9 +1) bewegt werden, die 251 an die Position 1 + 1 + 2 + 1 = 5 usw.
Im dritten und – in diesem Fall – letzten Schritt wird dann die erste Ziffer behandelt und das in der Abbildung dargestellte Histogramm erstellt. Danach bleiben die 123 und 138 an ihren Positionen, die 543 wird dagegen an die Position 2 + 2 + 1 = 5 verschoben. Nachdem alle Elemente in dieser Form behandelt sind, liegt die Folge komplett sortiert vor.
Abb. 5–8 RadixSort am Beispiel
Dieses Verfahren entspricht interessanterweise dem Vorgehen beim Sortieren von nummerierten Lochkarten, das bereits 1887 von Hollerith entwickelt wurde. Dort wurden allerdings keine Histogramme genutzt, stattdessen wurden die Karten entsprechend dem jeweiligen Stellenwert in Fächer eingeordnet.
Programm 5.8 zeigt eine einfache Implementierung von RadixSort. Die Methode radixSort sortiert das Feld in mehreren Schritten, wobei der eigentliche Schritt in der Methode radixSortStep realisiert ist. In der dargestellten Implementierung gehen wir zeichenweise vor und betrachten Zahlen mit maximal 3 Stellen – dies kann jedoch leicht angepasst werden.
In jedem Schritt wird zunächst das Feld in ein temporäres Feld kopiert, so dass das Ergebnis des Sortierschrittes direkt in das originale Feld geschrieben werden kann. Danach wird das Histogramm konstruiert, indem die betrachtete Ziffer über die Methode getDigit extrahiert und der passende Zähler im Histogramm inkrementiert wird.
Anschließend werden mithilfe der Variablen sum die kumulierten Häufigkeiten berechnet und direkt im Histogrammfeld abgelegt. Wie in Abbildung 5–8 entsprechen diese Häufigkeiten den Positionen der jeweiligen Partition nach der Sortierung.
Mit dieser Information können im letzten Schritt die Elemente aus dem temporären Feld an die richtige Position im Originalfeld array kopiert werden. Die Position ergibt sich aus dem Histogramm mit den kumulierten Häufigkeiten. Allerdings ist zu beachten, dass pro Partition mehrere Elemente (mit der gleichen Ziffer) existieren können. Um zu verhindern, dass diese auf die gleiche Position kopiert werden, nutzen wir das Feld offset, das die Zielposition relativ zum Beginn der Partition enthält und daher bei jeder Kopieroperation angepasst werden muss.
static void radixSort(int[ ] array) {
for (int i = 0; i < 3; i++)
radixSortStep(array, i, 10);
}
static int getDigit(int val, int dpos, int base) {
int[ ] div = { 1, 10, 100, 1000, 10000 };
return (val / div[dpos]) % base;
}
static void radixSortStep(int[ ] array, int d, int base) {
int[ ] histo = new int[base]; // Histogramm
int[ ] offset = new int[base]; // aktuelle Position pro Partition
// temporäres Feld
int[ ] tmp = new int[array.length];
System.arraycopy(array, 0, tmp, 0, array.length);
// Histogramm konstruieren
for (int i = 0; i < array.length; i++) {
int digit = getDigit(array[i], d, base);
histo[digit]++;
}
// kumulierte Häufigkeiten berechnen
int sum = 0;
for (int i = 0; i < histo.length; i++) {
sum += histo[i];
if (histo[i] > 0) histo[i] = sum − histo[i];
}
// Elemente an Position kopieren
for (int i = 0; i < tmp.length; i++) {
int digit = getDigit(tmp[i], d, base);
int pos = histo[digit] + offset[digit]++;
array[pos] = tmp[i];
}
}
Die Implementierung folgt dem Beispiel aus Abbildung 5–8, indem als Alphabet die Ziffern des Zahlensystems genutzt werden. Dies ist in der Methode getDigit(val, dpos, base) umgesetzt: Für den Wert val wird die Ziffer an der Position dpos (beginnend von hinten) extrahiert, wobei die Basis hier 10 ist. Die Basis definiert dabei auch die Größe des Histogramms (10 verschiedene Werte). Grundsätzlich ist aber das Alphabet frei wählbar. So können anstelle der Ziffern auch eine beliebige Anzahl von Bits der Elemente genutzt werden. Programm 5.8 kann dahingehend leicht abgewandelt werden, indem nur die getDigit()-Methode angepasst wird. Soll als Alphabet die Menge der 4-Bit-Werte (0x00 bis 0xff) eingesetzt werden, kann dies über folgende Implementierung erreicht werden:
static int getDigit(int val, int dpos, int base) {
return (val » (dpos « 2)) & (base - 1);
}
static void radixSort(int[] array) {
for (int i = 0; i < 16; i++)
radixSortStep(array, i, 16);
}
Gehen wir von 64-Bit-Integerwerten aus, dann sind bei 4 Bit pro Schritt 64/4 = 16 Schritte notwendig. Demzufolge muss auch die Schleife in der Methode radixSort angepasst werden.
Unser Beispielprogramm zeigt nur eine der möglichen Implementierungsvarianten. So exisitieren neben den hier betrachteten Verfahren, die an der niedrigswertigen Stelle (LSD – least significant digit) beginnen, auch Verfahren, die am anderen Ende (MSD – most significant digit) starten. Weiterhin kann zwischen In-Place-Verfahren (es wird direkt das Feld sortiert) und Out-of-Place-Verfahren (wie unsere Beispielimplementierung: Sortieren über ein zusätzliches Feld) unterschieden werden. Schließlich gibt es noch diverse Optimierungen für spezielle Datentypen wie z.B. Gleitkommawerte und Zeichenketten.
Laufzeitaufwand
Zum Abschluss dieses Kapitels wollen wir die vorgestellten Sortierverfahren bezüglich des Laufzeitaufwandes vergleichen. Dies liefert nicht nur eine wichtige Aussage über die Leistungsfähigkeit der Verfahren, sondern ist gleichzeitig eine gute Übung für die späteren Komplexitätsbetrachtungen.
Der Laufzeitaufwand eines Sortierverfahrens wird im Wesentlichen durch die Anzahl der Vergleiche und die Anzahl der Vertauschungen bestimmt. In Tabelle 5–4 sind die wichtigsten Eigenschaften der bisher eingeführten Verfahren angegeben, in den folgenden Abschnitten werden wir diese näher begründen.
Tab. 5–4 Eigenschaften von Sortierverfahren
Verfahren |
Stabilität |
Vergleiche (im Mittel) |
SelectionSort |
instabil |
≈ n2/2 |
InsertionSort |
stabil |
≈ n2/4 |
BubbleSort |
stabil |
≈ n2/2 |
MergeSort |
stabil |
≈ n log2 n |
QuickSort |
instabil |
≈ 2n ln n ≈ 1.38n log2 n |
RadixSort |
stabil/instabil |
≈ l · n |
Betrachten wir Algorithmus 5.4, so können wir feststellen, dass in jedem Durchlauf das Element von F[p] mit dem größten Element vertauscht wird. Da die Variable p von n bis 1 läuft, ergeben sich daraus n Vertauschungen. Gleichzeitig muss in jedem Durchlauf das größte Element aus dem Bereich 1 … p ermittelt werden. Dies erfordert wiederum jeweils p − 1 Vergleiche. Für n Elemente sind das insgesamt:
Die Anzahl der Vergleiche ist dabei unabhängig von der Art der Eingabefolge: Sowohl im günstigsten Fall (die Folge ist bereits sortiert) als auch im ungünstigsten Fall (die Folge ist absteigend sortiert) bleibt die Anzahl der notwendigen Vergleiche gleich. Einzig die Anzahl der Vertauschungen wird davon beeinflusst. Im ungünstigsten Fall könnten diese ebenfalls mit quadratischem Aufwand verbunden sein, im Durchschnitt sind es aber weniger als n.
Weiterhin ist zu beachten, dass SelectionSort instabil ist und damit die relative Reihenfolge der Elemente nicht beibehält.
Beim InsertionSort wird zunächst wiederum die gesamte Folge durchlaufen. In jedem Durchlauf wandert das gemerkte Element nach vorn, sofern es kleiner als seine bisheringen Vorgänger ist. Im ungünstigsten Fall sind dies im i-ten Durchgang i − 1 Positionen, im günstigsten Fall ist dagegen keine Verschiebung notwendig. Jeder Schritt umfasst dabei eine Vergleichsoperation und eine »halbe« Austauschoperation, da das betroffene Element jeweils auf ein freies Feld bewegt wird und kein echter Austausch durchgeführt wird. Für den durchschnittlichen Fall können wir also davon ausgehen, dass jedes Element nur den halben Weg zurückwandert und damit nur (i − 1)/2 Operationen benötigt werden. Dies ist die Hälfte der Anzahl der Vergleiche vom SelectionSort und kann daher mit − n2/4 angegeben werden. Aufgrund der »halben« Austauschoperationen beträgt die Anzahl der Vertauschungen für den durchschnittlichen Fall entsprechend ≈ n2/8.
InsertionSort erhält die relative Ordnung der Elemente und ist somit stabil.
Zur Analyse von BubbleSort ist es notwendig, sich das Grundprinzip noch einmal zu verdeutlichen. Bei jedem Durchlauf wird das größte Element gefunden und durch Vertauschen mit seinem rechten Nachbarn an das Ende der Folge bewegt. Im ungünstigsten Fall sind daher n Durchläufe notwendig, wobei im i-ten Durchlauf n − i Vergleiche (unter Ausnutzung der skizzierten Optimierungen) und Austauschoperationen erforderlich sind. Damit kann der Aufwand bezüglich Vergleichen und Vertauschungen wie beim SelectionSort mit ≈ n2/2 bestimmt werden. Dies gilt auch für den durchschnittlichen Fall. Im günstigsten Fall – wenn die Folge bereits sortiert vorliegt – ist jedoch nur ein Durchlauf notwendig.
Im Gegensatz zu SelectionSort ist BubbleSort jedoch stabil, da zwei benachbarte Elemente nur dann getauscht werden, wenn das erste Element größer ist.
Die Bestimmung der Anzahl der Vergleiche bei MergeSort ist aufgrund der Rekursion nicht ganz so einfach wie bei den nichtrekursiven Verfahren. Zunächst können wir feststellen, dass für die Anzahl der Vergleiche Vn für eine Folge der Länge n folgender Zusammenhang gilt:
Vn = 2Vn/2 + n für n ≥ 2 mit V1 = 0
Dies ist offensichtlich, da ja beide Teilfolgen zu sortieren sind und dies jeweils n/2 Vergleiche erfordert sowie für das abschließende Mischen wiederum n Vergleiche notwendig sind. Bei der weiteren Auflösung der obigen Gleichung hilft uns ein kleiner Trick [Sed02a]: Wir nehmen einfach an, dass n = 2N gilt, d.h., dass n eine Zweierpotenz ist. Nun kann 2N in die obige Gleichung eingesetzt werden:
Nun wird sukzessive der Term 
ersetzt, bis i = N ist:
Da aus n = 2N folgt N = log2 n, ergibt sich schließlich für Vn:
Eine Besonderheit von MergeSort ist der zusätzlich benötigte Speicherplatz (Out-of-Place). Bei der hier betrachteten Implementierung wurde ein Feld benutzt, dessen Größe proportional zu n ist.
Da das Bewegen von Elementen nur während des eigentlichen Mischens erfolgt, bleibt die relative Ordnung der Elemente erhalten. MergeSort ist somit stabil.
Da es sich bei QuickSort ebenfalls um ein Sortierverfahren nach dem »Teile und herrsche«-Prinzip handelt, gelten bezüglich der Anzahl der Vergleiche prinzipiell ähnliche Aussagen wie für MergeSort. Allerdings ist die Analyse komplexer, so dass wir an dieser Stelle darauf verzichten. Im Vergleich zu MergeSort entfällt jedoch der zusätzliche Speicherplatzbedarf für das Hilfsfeld. Aufgrund der Vertauschungen beim Partitionieren der Folge ist QuickSort instabil.
Der in Programm 5.8 implementierte Algorithmus durchläuft das Feld mehrfach: Für jede Stelle des Schlüssels genau einmal, d.h. bei einer maximalen Schlüssellänge l entsprechend l-mal. Jeder Durchlauf besteht wiederum aus der Konstruktion des Histogramms und dem Kopieren der Elemente an die richtige Position. Bei n Schlüsseln sind dies demzufolge 2n Schritte. Insgesamt ergibt sich somit ein Aufwand von l · 2n, d.h. ≈ l · n.
Ein weiteres Kriterium für die Eignung von Sortierverfahren, das wir bisher nicht betrachtet haben, ist das Verhalten bei bereits sortierten bzw. fast sortierten Folgen. Dies kann in der Praxis durchaus häufig auftreten, wenn beispielsweise einige wenige Elemente an eine bereits sortierte Folge angefügt werden sollen oder einfach nicht bekannt ist, dass die Folge bereits geordnet ist. Für diese Fälle sind beispielsweise InsertionSort und BubbleSort sehr gut geeignet, da ihre Gesamtlaufzeit hier linear ist.
Die getroffenen Aussagen sind natürlich nur Abschätzungen für den durchschnittlichen Fall. Darüber hinaus haben wir nur abstrakte Operationen gezählt und keine Angaben über deren konkreten Aufwand gemacht. Wir werden aber später in Kapitel 7.3 anhand des Begriffs der Komplexität zeigen, dass solche Aussagen für die Bewertung und den Vergleich von Algorithmen durchaus geeignet sind.
