Vermutlich jeder Programmierer wird früher oder später beim Programmieren einer zumeist eher umfangreicheren Software einmal vor dem Problem stehen, eine Menge von Daten nach einem bestimmten Kriterium (beispielsweise der lexikografischen Reihenfolge) zu sortieren – sei es, um die Daten sortiert dem Anwender präsentieren zu können oder nur um schnell und effektiv zu suchen. In folgendem Artikel möchten wir kurz einige Algorithmen vorstellen, mit denen das Sortieren nicht nur leicht fällt, sondern möglichst auch effektiv vonstatten geht.
Ziel soll dabei jedoch nicht sein – genauso wie in künftigen Artikeln in der Kategorie “Algorithmik” -, die Algorithmen komplett zu analysieren und ihre Korrektheit ausführlichst zu beweisen, wie es der eine oder andere theoretische Informatiker gerne einmal macht. Stattdessen sollen die Prinzipien der Algorithmen, ein kurzer Programmcode sowie die Vor- und Nachteile im Mittelpunkt stehen.
InsertionSort – Sortieren durch Einfügen
Aller Anfang ist schwer, heißt es zumeist. Hier wollen wir jedoch eher einfach anfangen mit einem Algorithmus, der sortiert, wie es der Otto-Normal-Kartenspieler sicherlich auch macht. Hierbei nimmt man an, ein Stapel mit einer Karte ist sortiert. Dann wird nach und nach jede einzelne Karte des Reststapels in den sortierten Stapel eingefügt, indem die Karte einfach an der korrekten Stelle in den Stapel eingefügt wird (d.h., wenn im sortierten Stapel die Karten 2,3,4 und 6 stehen, dann wird die 5 zwischen die 4 und die 6 gesetzt). Gleiches Prinzip kann natürlich auch für andere Datentypen wie “Karten” analog verwendet werden. In Pseudocode sieht das dann in etwa wie folgt aus:
InsertionSort(A[1..n]):
for i := 2 to n do
x := A[i]
for j := i downto 1 do
if A[j-1] > x then
A[j] := A[j-1]
else
A[j] := x
break
end
end
end
return A
Zugegebenermaßen ist InsertionSort zwar ein relativ simpler Algorithmus, dafür jedoch auch nicht sonderlich effektiv – das Verhältnis Eingabemenge zu den benötigten Vergleichen wäre im Durchschnitt n zu n² (soll heißen für n Elemente werden rund n² Vergleiche benötigt). Dafür wird aber neben dem zu sortierenden Array nur konstant viel zusätzlicher Speicher benötigt (man sagt, der Algorithmus arbeitet in-Place) und die relative Reihenfolge von Elementen mit gleichem Wert bleibt erhalten (d.h., im Array [A,A,A,A] bleiben die As in der gleichen Reihenfolge – dies mag hier eher unnötig wirken, wird aber deutlicher, wenn bspw. eine Menge von Tupeln nach einer speziellen Komponente sortiert wird), der Algorithmus arbeitet also stabil.
MergeSort – Sortieren nach dem Divide-and-Conquer-Prinzip
Eine weitere recht einfache und gleichzeitig auch ziemlich schnelle Sortiermethode lässt sich ebenfalls mit dem Karten-Sortieren sehr gut erklären: Man teile den Karten-Stapel in zwei gleich große Hälften, dieser wird erneut geteilt usw. bis es schließlich trivial ist, den Stapel zu sortieren (z.B. wenn der Stapel nur noch eine Karte ist). Nun werden jeweils die zwei eben getrennten und jetzt sortierten Stapel zu einem großen sortierten Stapel zusammengefügt. Auch dies lässt sich in Pseudocode wunderbar darstellen:
MergeSort(A[a..b]):
if n > 1 then
m := floor((a+b)/2) //berechnet das mittlere Element - floor() rundet ab
B := MergeSort(A[a..m]) //die erste Hälfte sortieren
C := MergeSort(A[m+1..b]) //die zweite Hälfte sortieren
i,k := a, j := m+1
while (i <= m and j <= b) do //füge die beiden Hälften zusammen
if B[i] <= C[j] then A[k] := B[i], i := i+1
else A[k] := C[j], j := j+1
end
k := k+1
end
while i <= m do //füge noch die Rest-Stapel an
A[k] := B[i]
i := i+1, k := k+1
end
while j <= m do
A[k] := C[j]
j := j+1, k := k+1
end
end
return A
Im Vergleich zu InsertionSort sieht der MergeSort-Algorithmus doch viel komplexer aus, ist dafür aber deutlich schneller - für n Elemente, die sortiert werden sollen sind in etwa n*log(n) Vergleiche notwendig. Jedoch arbeitet der Algorithmus nicht in-Place (d.h., der zusätzlich verwendete Speicherplatz ist abhängig von der Anzahl an Elementen), sortiert aber immerhin stabil.
QuickSort
Um Einiges komplizierter wird es mit einem weiteren Algorithmus, der ebenfalls auf dem Divide-and-Conquer-Prinzip ("Teile und Herrsche") beruht. Da es sich aber um den am Meisten eingesetzten Sortier-Algorithmus handelt (in Durchschnittlichen Fall ist dies einer der schnellsten vergleichsbasierten Sortier-Algorithmen). Vielleicht aber zunächst einmal eine Erklärung, was dieser Algorithmus tut: Man nehme sich zufällig eine Karte aus dem Karten-Stapel und bilde nun zwei neue Stapel - einer mit den Karten mit kleinerem Wert und einer mit den Karten mit größerem Wert. Daraus ergibt sich schon einmal die End-Position des Vergleichs-Elements (das sogenannte Pivot-Element). Rekursiv wird nun der Algorithmus auf die beiden kleineren Stapel angewendet, bis die Stapelgröße klein genug ist, dass das Sortieren eine Trivialität darstellt. In Pseudocode sieht das dann in etwa wie folgt aus:
QuickSort(A[1..n], a, b):
if a - b > 0 then
p := a //das Pivot-Element ist das erste Element
i := a+1, j := b
while i <= j do
while (i <= j and A[i] <= A[p]) do i := i+1 //suche von links nach rechts nach größeren Elementen
while (j > i and A[j] > A[p]) do j := j-1 //suche von rechts nach links nach kleineren Elementen
if i == j then j := j-1
if i < j then Vertausche A[i] mit A[j]
end
if j > p then //verschiebe das Pivot-Element an seine End-Position
Vertausche A[j] mit A[p]
p := j
end
A := QuickSort(A, a, p-1)
A := QuickSort(A, p+1, b)
end
return A
Im Durchschnittlichen Fall benötigt Quicksort für n Elemente rund n*log(n) Vergleiche, in der Regel aber etwas weniger, als MergeSort (im Schlechtesten Fall ist aber QuickSort leider nicht wesentlich schneller wie InsertionSort). In der Regel ist QuickSort nicht in-Place und auch nicht stabil. Durch geschicktes Implementieren lässt sich aber sicherlich noch eine Menge Speicherplatz sparen, sodass QuickSort auch in-Place funktioniert.
CountingSort - Sortieren durch Abzählen
Ein deutlich einfacherer und auch noch bedeutend schnellerer Algorithmus als QuickSort ist CountingSort. Bevor man sich aber zu früh über einen ultra-schnellen Algorithmus zum Sortieren freut, gibt es bereits eine schlechte Nachricht: CountingSort kann nur auf bestimmte Eingabemengen angewendet werden. So muss die Eingabe-Menge abzählbar und auch endlich sein (z.B. die Menge der Buchstaben des lateinischen Alphabets oder die ersten m natürlichen Zahlen).
Das Prinzip des Algorithmus' ist das Zählen der Vorkommen jedes einzelnen Elements in der zu sortierenden Menge, dann das Berechnen der jeweiligen Position der Elemente in der Ausgabe-Reihenfolge und letztendlich das nacheinander Einsortieren in die Ausgabe. Klingt zunächst vielleicht etwas komisch, vielleicht bringt aber auch der folgende Pseudo-Code noch etwas Licht ins Dunkel:
CountingSort(A[1..n]):
Erzeuge Arrays C[1..m], B[1..n] //C ist die Menge der Zähler für m verschiedene Elemente, B ist Ausgabe-Array
for i := 1 to m do
C[i] := 0 //Zähler zunächst auf 0 setzen
end
for j := 1 to n do
C[A[j]] := C[A[j]] + 1
end
for i := 1 to m-1 do
C[i+1] := C[i+1] + C[i] //berechne die Postionen des jeweils letzten Elements
end
for j := n downto 1 do
x := A[j]
B[C[x]] := x //füge Element A[j] an die Stelle, die im entsprechenden Zähler steht, ein
C[x] := C[x] - 1
end
return B
Für n Elemente werden hier letztlich 2n+2m Schritte benötigt - für größere Mengen mit wenigen verschiedenen Elementen (d.h., m <= n) ist dies bedeutend schneller als die zuvor genannten Algorithmen. Zudem sortiert CountingSort stabil, jedoch aber nicht in-Place.
Damit sind wir auch schon am Ende dieser kleinen Einführung in die Algorithmik und im speziellen des Sortierens angelangt. Es gibt natürlich noch Unmengen weiterer Algorithmen, die das Sortieren realisieren - von Bedeutung wären hier noch BubbleSort, SelectionSort, HeapSort, BucketSort und RadixSort. Vor allem die beiden letztgenannten sortieren wie CountingSort in linearer Zeit - BucketSort sortiert jedoch verkettete Listen (d.h., keine Arrays) und RadixSort baut auf CountingSort und/oder RadixSort auf.
Welcher Algorithmus nun am besten für eine Implementierung geeignet ist, muss man situationsabhängig entscheiden. Für kleine Arrays reicht beispielsweise InsertionSort schon aus, für größere Arrays ist dagegen QuickSort zu empfehlen und, wenn bereits im Voraus bekannt ist, dass nur wenige verschiedene Elemente auftreten (und diese auch bekannt sind), kann CountinSort auf jeden Fall empfohlen werden.
Wir hoffen, dass wir durchaus Licht ins Dunkel dieses Kapitels bringen konnten. Sollten aber noch weiterhin Fragen bestehen, können diese natürlich gerne in die Kommentare geschrieben werden.