Countingsort und Radixsort. Sortieren in linearer Zeit

Zusammenfassung

Wir stellen zwei Sortierverfahren vor, die im Gegensatz zu ”her- kömmlichen Verfahren“ in linearer Zeit sortieren können, indem sie Annahmen über die Eingabemenge treffen. Diese sind Countingsort und Radixsort. Countingsort nimmt an, dass es sich ausschließlich um ganze Zahlen handelt, Radixsort nimmt an, dass die größte Ziffer kleiner als die Anzahl der zu sortierenden Zahlen ist.¹

1 Einleitung

Je mehr Werte sortiert werden sollen, desto wichtiger ist es, dass die Sortierung schnell und effizient geschieht. Dies ist u.a. mit Countingsort, Radixsort und Bucketsort möglich, deren Laufzeit linear ist. Allerdings ist die Eingabemenge stark beschränkt, bei Countingsort etwa auf die ganzen Zahlen, und je größer die höchste Zahl ist, desto mehr Zahlen sollten insgesamt sortiert werden, damit Countingsort effizient bleibt.

Sortierverfahren spielen zum Beispiel beim Sortieren von Telefonbüchern, Adresslisten oder in Datenbanken eine große Rolle. Gerade bei Datenbanken ist eine effiziente Sortierung entscheidend, da diese die Zugriffe deutlich beschleunigen kann und somit viel Zeit spart.

Radixsort hatte vor allem früher eine große Bedeutung. Es wurde ur- sprünglich dazu genutzt um Lochkarten zu sortieren. Die Lochkarten be- standen zum Beispiel aus 80 Spalten und in jeder Zeile gab es an einer von 12 Stellen ein Loch. Die Maschine sortiert die Lochkarten, je nachdem, an welcher der 12 Stellen sich ein Loch befindet, in eines von 12 Kästchen [CLRS01, 168].

Wenn jetzt nach der nächsten Spalte sortiert werden soll, sammelt man die Karten ein und legt die Stapel gesammelt wieder in die Maschine. Anschließend stellt man die Maschine auf die Spalte mit der nächsthöheren Priorität ein. Diese Sortiermethode wird heute manchmal in Rechnern verwendet, wenn Daten nach mehreren Schlüsseln (wie etwa Tag, Monat und Jahr) sortiert werden sollen [CLRS01, 170].

2 Grundlagen

2.1 Definitionen

Wenn von N gesprochen wird, sind hier (sofern nicht anders angegeben) die natürlichen Zahlen inklusive 0 gemeint.

Eine Teilliste A[m..n] einer Liste A, n > m besitzt n − m + 1 Elemente, Indizes von m bis n. Ist keine Basis angegeben, so betrachten wir den Logarithmus zur Basis 2.

2.2 O-Notation

Meistens ist die tatsächliche Laufzeit von Algorithmen uninteressant. Viel eher möchte man wissen, in welcher ”Effizienzklasse“dasProgrammläuft, um somit die Laufzeit mehrerer Programme einfach vergleichen zu können. Seien f, T zwei Funktionen mit f, T : N → N . Dann ist T von der Größenordnung f (kurz: T (n) = O(f (n))) ⇔ ∃ n0 ∈ N und c ∈ R, c > 0 mit: ∀n ≥ n0 : T (n) ≤ c · f (n).

Mit c und n0 fest gewählt [ODR16a, 28 f]. Das Gleichheitszeichen sollte eher als ”IstElementvon“verstandenwerden,daessichnichtumGleich- heit handelt, sondern um ein Element einer Menge [ODR[16]a,²⁸ ff] Prinzipiell ist die Ω-Notation genau gleich wie die O-Notation aufgebaut, mit dem Unterschied, dass hier die untere Schranke betrachtet wird [ODR[16]a,³⁰ ].

Nun gibt es noch die Möglichkeit, die Laufzeit eines Algorithmus’ ”einzuzwängen”, also eine Funktion anzugeben, dass gilt:

∃ n0 ∈ N sodass ∀n ≥ n0 : T(n) ≥ c · f(n) und T(n) ≤ c · f(n) mit c, c ∈ R, c, c > 0 [ODR16a, 30]. Diese Funktion Θ gibt also an, wie die un- gefähre Laufzeit des Algorithmus aussieht mit oberer und unterer Schranke.

3 Sortierverfahren

3.1 Stabile Sortieralgorithmen

Gehen wir davon aus, dass unsere zu sortierende Zahlenfolge in einer Liste gespeichert ist ( = Eingabesequenz). In der Regel muss für einen schnel- len Algorithmus entweder mehr Speicherplatz (als für die Liste, welche die Eingabesequenz enthält, benötigt wird) verwendet werden, oder der Algo- rithmus arbeitet nicht stabil. Stabil bedeutet, dass gleiche Elemente in der Reihenfolge ausgegeben werden, in welcher sie in der Eingabe gespeichert sind. Ein einfaches Beispiel:

Abbildung in dieser Leseprobe nicht enthalten

Nach einem stabilen Sortieralgorithmus:

Abbildung in dieser Leseprobe nicht enthalten

Nach einem nicht-stabilen Sortieralgorithmus ist auch folgendes Szenario denkbar:

Abbildung in dieser Leseprobe nicht enthalten

Kurz zusammengefasst:

Bei einem nicht-stabil operierenden Sortieralgorithmus können gleiche (bzw. genauer: unter dem Sortierkriterium ”gleiche”) Elemente in einer anderen Reihenfolge auftreten als in der Urspungsfolge. Dies kann zu falschen Ergeb- nissen führen, wenn ein nicht-stabiler Sortieralgorithmus als ”Unterprogramm“ für einen anderen Algorithmus verwendet wird. Dies werden wir später nochmals bei Radixsort sehen.

3.2 Speicherplatzverbrauch: In-Place und Out-of-Place

Algorithmen können mit oder ohne zusätzlichen Speicherplatzverbrauch ar- beiten. Wenn alle Operationen auf der Eingabeliste ausgeführt werden, und man keinen zusätzlichen Speicherplatz benötigt, nennt man dies In-Place. Meistens wird eine bessere Effizienzklasse durch mehr Speicherverbrauch

”erkauft“.DieserVerbrauchvonSpeicherkannebenfallsinderO-Notation angegeben werden. Liegt der Speicherplatzverbrauch etwa in O(n), so benötigt das Programm linear viel Speicherplatz mehr. Dies kommt zustande, wenn der Algorithmus beispielsweise nochmals ein Feld benötigt, um sortieren zu können. Darauf wird im Abschnitt 4.1 noch genauer eingegangen.

3.3 Effizientes sortieren

Ein Algorithmus heißt effizient, wenn er polynomial begrenzt ist. Dies be- deutet, er läuft in O(nk), für ein festes k ∈ N [ODR16a, 43]. Die meisten (bekannten) Sortieralgorithmen arbeiten vergleichend. Das heißt, der Algorithmus kann nur paarweise Elemente vergleichen. Vergleichende Sortierverfahren können abstrakt als Entscheidungsbäume betrachtet wer- den. Ein Entscheidungsbaum ist ein vollständiger binärer Baum, der die Vergleiche zwischen den Elementen repräsentiert, die von einem speziellen Sortieralgorithmus auf einem Eingabefeld vorgegebener Größe durchgeführt werden. In einem Entscheidungsbaum wird jeder innere Knoten mit i : j (1 ≤ i, j ≤ n) versehen, wobei n die Anzahl der Elemente in der Einga- besequenz ist. Jedes Blatt ist mit einer Permutation (π(1), π(2), . . . , π(n)) gekennzeichnet. Die Ausführung des Sortieralgorithmus entspricht der Ver- folgung eines Pfads von der Wuzel bis zu einem Blatt. An einem Knoten i : j wird der Vergleich ai ≤ aj durchgeführt. Der linke Teilbaum beschreibt die Vergleiche für den Fall ai ≤ aj, der rechte Teilbaum für ai > aj. Wenn wir ein Blatt erreichen, hat der Sortieralgorithmus die Reihenfolge aπ(1) ≤ aπ(2) ≤ ··· ≤ aπ(n) festgelegt. Da jeder korrekte Sortieralgorithmus jede Permutation der Eingabe erzeugen können muss, ist eine notwendige Bedin- gung, dass jede der n! Permutationen von n Elementen als eines der Blätter des Entscheidungsbaumes vorkommen muss, und dass jedes Blatt von der Wurzel aus erreichbar sein muss. Dieser Pfad entspricht der tatsächlichen Ausführung des vergleichenden Sortierverfahrens. Wir werden nur Entschei- dungsbäume betrachten, in denen alle Blätter erreichbar sind. Die Länge des längsten Pfades entspricht der Anzahl der Vergleichsoperationen im schlech- testen Fall und ist die Höhe des Entscheidungsbaumes. Eine untere Schranke für die Höhen aller Entscheidungsbäume ist daher eine untere Schranke für die Laufzeit jedes vergleichenden Sortierverfahrens [CLRS01, 164 f].

Theorem 1. Für jeden vergleichenden Sortieralgorithmus sind im schlech- testen Fall mindestens Ω(n · log(n)) Vergleichsoperationen erforderlich.

Beweis: Nach der vorangegangenen Diskussion genügt es, die Höhe ei- nes Entscheidunsgbaumes zu bestimmen, in dem jede Permutation als Blatt erscheint. Betrachten wir nun einen Entscheidungsbaum der Höhe h mit l erreichbaren Blättern, der einer vergleichenden Sortierung von n Elemen- ten entspricht. Da jede der n! Permutationen der Eingabesequenz als Blatt erscheint, gilt n! ≤ l. Da ein binärer Baum der Höhe h nicht mehr als 2h Blätter besitzt, gilt: n! ≤ l ≤ 2h woraus wir h ≥ log(n!) (und somit) h = Ω(n · log(n)) folgern. [CLRS01, 165].

3.3.1 Mergesort

Im Gegensatz zu linearen Sortieralgorithmen kann Mergesort, welches einen sog. Divide-and-Conquer-Ansatz verwendet [ODR16b, 53 ff], mit vielen Un- terschiedlichen Daten arbeiten (insbesondere nicht nur mit ganzen Zahlen). Bei Mergesort wird die zu sortierende Folge so lange in Teilfolgen unter- teilt, bis jede Teilfolge nur noch aus einem Element besteht. Ein-elementige Teilfolgen sind bereits sortiert. Nun werden die Teilfolgen stückweise wie- der zusammengefügt und währenddessen sortiert. Aus ein-elementigen Teil- folgen werden zwei-elementige Teilfolgen gemacht (und währenddessen die zwei Elemente in der richtigen Reihenfolge angeordnet). Nun werden aus den zwei-elementigen Teilmengen vier-elementige Teilmengen erstellt und wieder sortiert. Dies läuft so lange, bis man die komplette Folge sortiert hat.

Der Speicherplatzverbrauch liegt (zusätzlich zum Eingabefeld) in O(n). Mergesort läuft zeitlich in O(n · log(n)), im Gegensatz zu beispielsweise O(n² ) von Bubblesort [Sch01, 96 ff]. Der Beweis zur Laufzeit und Korrektheit steht unter [ODR16b, 63 ff].

4 Lineares Sortieren

Vorher haben wir gezeigt, dass für vergleichsbasierte Algorithmen die unte- re Schranke Ω(n · log(n)) gilt. Dies stimmt natürlich weiterhin. Allerdings arbeiten die folgenden Algorithmen nicht vergleichsbasiert, daher gilt für sie die untere Schranke von Ω(n · log(n)) nicht. Die linearen Sortieralgorithmen können nur in Θ(n) arbeiten, weil sie bestimmte Annahmen über die Einga- besequenz treffen. Sind diese Annahmen falsch, so kann entweder gar nicht sortiert werden, oder die Laufzeit liegt nicht mehr in Θ(n). Das bedeutet, dass die Eingabemenge stark begrenzt ist. Bei Countingsort etwa können nur ganze Zahlen sortiert werden.

[...]

¹ Studiengang: Ba Informatik, Universität Ulm