Kurs:Algorithmen und Datenstrukturen/Kapitel 2

Sortieren in Arrays

Der Wunsch Ordnung zu erzeugen ist sehr alt und die Gründe hierfür sind so vielfältig wie die Dinge, die sortiert werden sollen. Einer der Hauptgründe für das Sortieren ist der Umstand, dass man etwas schneller findet, wenn man eine Ordnung voraussetzen kann. Sortieren ist also die Voraussetzung für effektives Suchen. Dies gilt für Lagerhallen genauso wie für Wörterbücher.

In diesem Kapitel erfolgt eine Beschränkung auf das Sortieren von Datensätzen. Da die Zeiten schon lange vorbei sind, als Daten noch auf Magnetbändern gespeichert wurden und man nur sequenziellen Zugriff auf diese Daten hatte, erfolgt noch eine weitere Einschränkung: es wird wahlfreier Zugriff auf die Daten voraus gesetzt. Hierbei ist es unerheblich, ob sich die Daten im schnellen Arbeitsspeicher befinden oder auf der Festplatte; dies ändert nichts an der grundlegenden Arbeitsweise der Algorithmen.

Des weiteren wird voraus gesetzt, dass alle Datensätze die gleiche Länge und Struktur haben, und sie in Form einer Liste gespeichert sind; deshalb hat dieses Kapitel auch den Titel "Sortieren in Arrays" bekommen. Wie die Struktur der Datensätze im Detail aussieht, ist für das Problem des Sortierens unerheblich; hier interessiert nur, wie der Schlüssel aufgebaut ist, also der Teil des Datensatzes, nach dem sortiert werden soll.

Zu den Zeiten, als Speicherplatz noch extrem teuer war, war der Speicherbedarf eines Sortieralgorithmus von wesentlicher Bedeutung, es wurden also Algorithmen bevorzugt, die „in place“ sortieren konnten; man übergab also dem Algorithmus einen Array mit den Datensätzen und wenn die Sortierung beendet war, standen die sortierten Daten in eben diesem Array. Dieses Kriterium spielt heutzutage praktisch keine Rolle mehr.

Bei der Beurteilung eines Sortieralgorithmus auf Verwendbarkeit müssen folgende Kriterien untersucht werden:

kann der Algorithmus den Sortierschlüssel handhaben
steht genügend Speicherplatz zur Verfügung
ist er schneller als die Alternativen
kann der Algorithmus in der gewünschten Programmiersprache implementiert werden.

In diesem Kapitel werden anhand ausgesuchte Algorithmen die grundlegenden Strategien von Sortieralgorithmen dargelegt und sollten einen in die Lage versetzen, für ein aktuelles Problem einen geeigneten Sortieralgorithmus zu wählen und auch die Arbeitsweise und die Charakteristiken von den Algorithmen zu verstehen, die hier nicht beschrieben werden.

Einleitung

Wie kann man sortieren?

Der Begriff "sortieren" kann vereinfacht durch folgende Elementaroperationen dargestellt werden.

Man kann sortieren durch...

Auswählen und Einfügen
Vertauschen
Mischen ("Reißverschlussverfahren")
Streuen und Sammeln
Fachverteilen

Sortieren in Anwendungen Sortierung ist eine wichtige Operation in zahllosen Anwendungen. Es benötigt einen großen Anteil in Programmlaufzeiten bei großen Datenmengen. In folgenden "Anwendungen" kommen verschiedene Sortierverfahren zum Einsatz.

Wörter in Lexikon (geordnet nach der Buchstabenreihenfolge)
Kontoauszug (geordnet nach Datum der Kontobewegung)
Sortierung von Studenten (nach Namen, Notendurchschnitt, Semester, ...)
Sortierung von Adressen / Briefen (nach Postleitzahlen, Ort, Straße ...)

Definition des Problems

Beim Wort "Sortieren" denkt man automatisch an Zahlen. Das Sortieren an sich ist aber nicht auf numerische Werte beschränkt.

Eine Reihe von Objekten $a_{i}$ , $i=1\dots n$ nennen wir sortiert wenn für eine binäre, transitive Relation $\circ$ (auch Ordnungsrelation genannt) gilt

a_{i}\circ a_{j}\quad \forall \,i<j

Anders ausgedrückt: die Relation $\circ$ ist erfüllt für alle Paare $a_{i}$ , $a_{j}$ , wo $i<j$ .

Eine Menge von aufsteigenden Zahlen $a_{1},a_{2},\dots a_{n}$ ist somit nach der Relation " $\leq$ " sortiert, denn es gilt

a_{i}\leq a_{j}\quad \forall \,i<j

.

Diese etwas abstrakte Definition ist für Zahlen ziemlich kompliziert, erlaubt es uns aber, beliebige Objekte nach beliebigen Kriterien zu sortieren.

Wir betrachten zum Beispiel die Menge von Namen:

Andrea, Beatrice, Caroline, Daniela, Edith

Die Namen sind oben aufsteigend alphabetisch sortiert. Wir können sie aber auch

Beatrice, Caroline, Daniela, Andrea, Edith

absteigend nach der Laenge sortieren. Oder

Andrea, Daniela, Caroline, Beatrice, Edith

absteigend nach der Anzahl Vorkommen des Buchstaben "a" sortieren.

Um zu überprüfen, ob ein Array sortiert ist, können wir uns auch die Transitivität der Relation, die besagt

a\circ b\quad \wedge \quad b\circ c\quad \rightarrow \quad a\circ c

zu nutze machen und verlangen, dass

a_{i}\circ a_{i+1},\quad i=1\dots n-1

.

Der Rang eines Elementes ( ${\mathsf {rank}}(a_{i})$ ) bezeichnet die Position dieses Elementes im sortierten Array. Ist das Array sortiert, so gilt

{\mathsf {rank}}(a_{i})=i,\quad i=1\dots n

.

Wir suchen nun nach Algorithmen, welche eine Folge von Elementen sortieren.

Beliebige Elemente $a_{1},a_{2},\dots a_{n}$ sind nach einer gegebenen transitiven, binären Relation $\circ$ sortiert wenn gilt:

a_{i}\circ a_{i+1},\quad i=1\dots n-1

.

Indirektes Sortieren

Die benötigte Zeit für das Vertauschen von Daten kann unter Umständen drastisch reduziert werden, in dem nicht die Daten selbst sondern zwei Indexwerte in einem Array vertauscht werden.

Nach dem Sortiervorgang sind nicht die Daten selbst, sondern nur das Array sortiert. Möchte man nun die Daten in eine sortierte Reihenfolge bringen, müssen diese anhand des Arrays umgestellt werden. Dies erfolgt aber in linearer Zeit ${\mathcal {O}}(n)$ .

Indirektes Sortieren ist also immer dann angezeigt, wenn einerseits die Kosten für das Vertauschen von Daten hoch ist (die Datensätze also lang) und andererseits der zusätzlich benötigte Speicher (i.d.Regel 4 Bytes pro Element) keine Probleme bereitet (also eigentlich nie).

Stabilität

In der Praxis kommt es häufig vor, dass Daten nicht nur nach einem Kriterium sortiert werden müssen. Hat man etwa eine Tabelle mit Personendaten, dann möchte man sie etwa nach Vornamen sortieren und in einem weiteren Schritt nach Nachnamen.

Ein Sortieralgorithmus wird als stabil bezeichnet, wenn anschliessend die ganze Liste nach Nachnamen sortiert ist und zusätzlich bei gleichen Nachnamen die Vornamen immer noch sortiert vorliegen.

Bei den Algorithmen, die nicht stabil sind, kommt man nur mit erheblichem Mehraufwand zum gleichen Ergebnis. Und zwar muß man die Sortierung nach den Nachnamen vornehmen und anschliessend durch die Liste gehen, die Datensätze mit gleichem Nachnamen in einer Gruppe sammeln und anschliessend diese Gruppe noch einmal nach dem Vornamen sortieren.

Soll etwa eine Tabelle mit Personendaten zunächst nach Postleitzahl, innerhalb der Postleitzahl nach Straßennamen, innerhalb der Straßennamen nach Nachname und innerhalb der Nachnamen nach Vornamen sortiert werden, dann wird das Programm bei nicht stabilen Algorithmen schon recht unübersichtlich. Bei stabilen Sortieralgoritmen führt man die vier Sortierungen einfach in umgekehrter Reihenfolge durch und ist fertig.

Laufzeit-Analyse

Sortierverfahren spielen in der Informatik eine wichtige Rolle und im Laufe der Zeit wurde eine große Anzahl von Sortieralgorithmen entwickelt. Eine gängige Unterscheidung erfolgt danach, ob ein Algorithmus vergleichsbasiert ist, also ganze Schlüssel miteinander in Bezug auf eine Ordnungsrelation verglichen werden, oder ob der Algorithmus nicht-vergleichsbasiert arbeitet. Die meisten Algorithmen, die zu letzterem Typ gehören, waren in ihrer Verwendbarkeit eingeschränkt, weshalb diese Unterscheidung oft mit „brauchbar“ und „exotisch“ gleichgesetzt wurde.

Es wird aufgezeigt, dass eine Unterscheidung in teilende und nicht-teilende Algorithmen wesentlich besser geeignet ist, die Unterschiede zwischen verschiedenen Algorithmen in Bezug auf ihre Verarbeitungsgeschwindigkeit zu erfassen. Die Funktionsweise der Algorithmen wird hier nur stark verkürzt wiedergegeben; eine detaillierte Beschreibung der Algorithmen findet sich weiter hinten.

Betrachten wir zunächst einen Algorithmus, der die Sortierung nicht in Teilaufgaben zerlegt.

SelectionSort

	Bei SelectionSort werden die kompletten Schlüssel der Datensätze miteinander verglichen, um die Datensätze gegebenenfalls zu vertauschen. Hierbei beginnt man mit dem ersten Element und durchsucht alle anderen Datensätze, ob sich einer mit einem kleineren Schlüssel findet. Falls ja, werden die Datensätze ausgetauscht. Findet sich kein kleinerer Schlüssel mehr, wird das Verfahren mit dem zweiten Datensatz wiederholt, dann dem dritte und so weiter. Grob gesagt wird jeder Datensatz mit allen anderen verglichen wird, wodurch sich eine quadratische Charakteristik ergibt. Der Zeitbedarf kann mit *T = B n²** abgeschätzt werden, wobei B eine Konstante darstellt, die die Implementierung berücksichtigt.

Hat man nur zwei Datensätze, reduzieren sich die Verfahren dieses Typs auf die Abfrage, ob diese beiden Datensätze getauscht werden müssen oder nicht. In diesem Sonderfall sind alle Algorithmen dieses Typs unschlagbar schnell.

Nun werden einige Algorithmen betrachtet, bei denen nach dem Motto „teile und herrsche“ gearbeitet wird.

QuickSort

	Der am häufigsten verwendete Algorithmus dieses Typs ist Quicksort. Man beginnt zunächst mit der Gesamtheit der Datensätze als ein Bereich. Für diesen Bereich wird ein Pivot-Wert so ausgewählt, dass möglichst gleichviele Schlüssel einen kleineren oder größeren Wert haben, und anhand dieses Pivotwertes werden die Datensätze in einen unteren Bereich und einen oberen Bereich aufgeteilt. Die Methode wird dann rekursiv auf diese beiden Bereiche angewendet. Enthält ein Bereich nur noch ein oder kein Element, gilt er als sortiert. Man könnte die Zerlegung der Bereiche in einem binären Baum darstellen und die Anzahl der Schichten in diesem Baum ergibt sich daraus, wie oft die Bereiche durch zwei teilbar sind. Folglich kann der Zeitbedarf mit *T = C n * lg₂(n)** abgeschätzt werden, wobei C eine Konstante darstellt, die die Implementierung berücksichtigt.

BucketSort

	Ein Klassiker unter den Sortieralgorithmen ist Bucketsort. Man habe eine Anzahl m von Eimern und eine -wie auch immer definierte- Bewertungsfunktion, die entsprechend dem Wert des Schlüssels die Datensätze auf die Eimer verteilt. Hat man in den Eimern Datensätze mit unterschiedlichem Schlüsselwert, muss der jeweilige Inhalt der Eimer noch einmal intern sortiert werden. Erfolgt die Erzeugung der Bewertungsfunktionen automatisch und optimal, werden die Datensätze auf jeder Rekursionsebene wieder gleichmäßig über m Eimer verteilt. Der Zeitbedarf bei wiederholt angewendetem Bucketsort kann mit *T = D n * lg_m(n)** abgeschätzt werden, wobei D eine Konstante darstellt, die die Implementierung berücksichtigt.

RadixSort

	Der absolute Klassiker unter den Sortieralgorithmen ist RadixSort (Herman Hollerith, 1887), der meist zum Sortieren durchnummerierter Lochkarten verwendet wurde. Hierzu wurde eine Sortiermaschine mit zehn Schächten so eingestellt, dass sie von diesen Nummern zunächst die Einerstelle auswertete und die Lochkarten entsprechend der aktuellen Ziffer in den Schächten ablegte. Dann wurden die Lochkarten bei Schacht Null beginnend eingesammelt, die Sortiermaschine wurde auf die Zehnerstellen ausgerichtet, und der nächste Sortierdurchgang gestartet. Dieser Zyklus von ausrichten, verteilen und wieder einsammeln wurde solange wiederholt, bis die vorderste Ziffer erreicht wurde. Bei RadixSort kann der Zeitbedarf mit *T = E n * lg₁₀(N)** abgeschätzt werden, wobei E eine Konstante darstellt, die die Implementierung berücksichtigt; N steht für die Anzahl möglicher verschiedener Schlüssel. Klassischerweise wird diese Formel mit T ≈ n * d angegeben, wobei d die Anzahl der Ziffern ist. Da durch den Logarithmus angegeben wird, wie oft die Anzahl wiederholt durch 10 geteilt werden kann, sind die Aussagen zwar identisch, aber der direkte Vergleich mit anderen Algorithmen wird erschwert.

ExtraDix

	Bei ExtraDix handelt es sich um eine Erweiterung von Radixsort und es werden Sortiermaschinen simuliert, die fest mit 256 Schächten arbeiten. Diese Anzahl wurde gewählt, da der kleinste Schlüssel, nach dem in der Praxis sortiert wird, Zahlen mit 8 Bit oder Zeichen sind, die 256 unterschiedliche Werte annehmen können. Entsprechend kann der Zeitbedarf mit *T = F n * lg₂₅₆(N)** abgeschätzt werden, wobei F eine Konstante darstellt, die die Implementierung berücksichtigt; N steht wieder für die Anzahl möglicher verschiedener Schlüssel; der Ausdruck lg₂₅₆(N) gibt die Anzahl der Bytes an, die der Schlüsseltyp hat, bei einer 32-Bit-Ganzzahl also 4.

Es fällt auf, dass bei Quicksort mit einem Logarithmus von n gearbeitet wird und bei den anderen kurz vorgestellten Algorithmen mit einem Algorithmus aus N; dies soll näher beleuchtet werden.

Auf dem Zahlenstrahl der reellen Zahlen befinden sich unendlich viele reelle Zahlen; es läßt sich sogar beweisen, dass in jedem beliebigen Intervall unendlich viele reelle Zahlen zu finden sind. Quicksort und andere Algorithmen gehen implizit von der Annahme aus, dass nicht bekannt sein kann, wieviele Bereichsunterteilungen gemacht werden müssen; daher wird diese Anzahl dynamisch während der Sortierung bestimmt.

Die beiden zuletzt vorgestellten Algorithmen gehen davon aus, dass nur eine endliche Anzahl verschiedener Werte auf einem Rechner darstellbar ist. Auch wenn man mit doppelt genauen reellen Zahlen arbeitet, ist die Anzahl verschiedener Werte abzählbar und zwar ist die Anzahl 2⁶⁴. Bei konstantem Teilungsfaktor -gleiche Anzahl der Schächte oder Eimer- kann man also unabhängig von der Anzahl der Datensätze bestimmen, nach wievielen Sortierdurchläufen nur noch Datensätze mit identischen Schlüsseln in den verschiedenen Ablagen sein können.

Hat man beispielsweise vier Datensätze, dann hat Quicksort seine Aufgabe nach zwei Rekursionsstufen erledigt. Arbeitet man mit Radixsort und der Wertebereich der Schlüssel liege zwischen 00.000 und 99.999, dann werden auf jeden Fall fünf Sortierdurchläufe gemacht. Quicksort ist also eindeutig im Vorteil. Dies ändet sich sofort, wenn man 100.000 Datensätze hat, die eine gleichmäßige Werteverteilung haben könnten. Radixsort benötigt immer noch fünf Sortierdurchläufe, aber Quicksort muß 17 Rekursionsstufen abarbeiten (2¹⁷ = 131072).

Sucht man für eine Sortieraufgabe den schnellsten Algorithmus, kann man die Funktionen zur Abschätzung der Sortierzeit in Relation zueinander setzen. Will man etwa wissen, ab welcher Anzahl von Datensätzen ExtraDix dem QuickSort beim Sortieren von 64-bittigen Ganzzahlen überlegen ist, erhält man

*F n * lg₂₅₆(N)**	<	*C n * lg₂(n)**
*F n * 8**	<	*C n * lg₂(n)**
*F 8**	<	*C lg₂(n)**
n	>	*2 ^{F 8 / C}**

Unterstellt man für C und F gleiche Werte, kann man sie gegeneinander kürzen und Erhält als Ergebnis, dass ab 256 Datensätzen ExtraDix schneller ist als Quicksort. Da ExtraDix indirekt sortiert und zudem nur wenige Rechenschritte pro Schlüsselbyte erforderlich sind, dürfte die Grenze deutlich niedriger liegen.

nicht teilende Algorithmen

BubbleSort

Ausgehend von der Definition eines sortierten Arrays

a_{i}\leq a_{i+1},\quad i=1\dots n-1

(wir verwenden hier das " $\leq$ " für eine allgemeine Ordnungsrelation), können wir einen ersten, naiven Algorithmus zum Sortieren eines Arrays konstruieren:

Wir durchlaufen das Array und vergleichen dabei jedes Element $a_{i}$ mit dem darauffolgenden Element $a_{i+1}$ . Sind die zwei Elemente nicht sortiert, so werden sie vertauscht. Wir wiederholen diesen Vorgang bis das Array sortiert ist.

BubbleSort ist in für die Anzahl von Vergleichen und Vertauschungen sowohl im worst-case als auch im average-case in der Größenordnung ${\mathcal {O}}(n^{2})$ .

Link auf die ausführliche Beschreibung von BubbleSort!

SelectionSort

SelectionSort sucht das kleinste Element in einem Array und vertauscht es mit der ersten Stelle. Danach wird das zweitkleinste Element gesucht und mit der zweiten Stelle vertauscht usw...

Die dazu notwendige Anzahl Vergleiche und Vertauschungen sind, sowohl im Worst-Case als auch im Average-Case in der Größenordnung ${\mathcal {O}}(n^{2})$ bzw. ${\mathcal {O}}(n)$ .

Link auf die ausführliche Beschreibung von SelectionSort!

InsertionSort

Ein Array mit $n$ Elementen wird sortiert, indem für jedes $i$ -te Element dessen richtige Position im Teilarray von $1\dots (i-1)$ gesucht wird und das Element durch paarweise Vertauschungen dorthin verschoben wird. Im Schnitt werden dafür ${\mathcal {O}}(n^{2})$ Vergleiche und ${\mathcal {O}}(n^{2})$ Vertauschungen benötigt.

Die Varianten Binary InsertionSort und ShellSort kommen mit ${\mathcal {O}}(n\log n)$ Vergleichen bzw. ${\mathcal {O}}(n^{3/2})$ Vertauschungen aus.

Link auf die ausführliche Beschreibung von InsertionSort!

teilende Algorithmen

Diese Algorithmen arbeiten alle nach dem "Teile und Herrsche"-Prinzip.

Warum das Prinzip "Teile und Herrsche" einen Vorteil bei Sortieraufgaben bewirkt, erfahren Sie hier!

Wie schon in der Laufzeitanalyse aufgezeigt, kann bei dieser Art Algorithmen unterschieden werden, ob die Anzahl der Teilungsschritte dynamisch bestimmt wird oder ob mit einer festen Anzahl von Teilungsschritten gearbeitet wird.

dynamische Teilung

Bei den Algorithmen dieser Gruppe erfolgt die Aufteilung in Teillisten aufgrund der Anzahl der Datensätze. Die meisten Algorithmen dieser Gruppe arbeiten nicht stabil.

MergeSort

Bei MergeSort wird die Eingabeliste in zwei Hälften aufgeteilt, welche rekursiv sortiert werden. Enthält eine Liste nur ein oder kein Element, gilt sie als sortiert; die Rekursion wird abgebrochen und die sortierte Liste wird an den aufrufenden Level zurück gegeben. Dieser fügt die beiden sortierten Listen zu einer sortierten Liste zusammen, indem die ersten Elemente der Teillisten betrachtet werden und der jeweils kleinere Wert wird in die Ergebnisliste verschoben. Wird bei identischen Schlüsselwerten immer zuerst die Liste mit den kleineren Werten abgearbeitet, so ist der Algorithmus stabil. Da es immer eine Zielliste geben muss, ist MergeSort kein in-place Algorithmus. Die Anzahl der Vergleiche und Kopiervorgänge kann mit ${\mathcal {O}}(n\log _{2}n)$ charakterisiert werden.

Ausführliche Beschreibung von MergeSort!

QuickSort

Aus dem gegebenen Bereich wird ein sogenanntes Pivotelement bestimmt. Dieses teilt die bestehende unsortierte Liste in zwei Unterbereiche, nämlich die Elemente, die kleiner/gleich oder die größer/gleich dem Pivotelement sind. Auf die Unterbereiche wird der Algorithmus rekursiv angewendet.

Bei gleichmäßig verteilten Daten ergibt sich ein Zeitbedarf, dessen Verlauf über ${\mathcal {O}}(n\log _{2}n)$ abgeschätzt werden kann. Dieses Verhalten gilt sowohl für den Best Case als auch den Average Case.

Wird der Algorithmus in seiner Grundform benutzt (als Pivotelement wird immer der erste oder der letzte Wert aus dem Bereich gewählt), dann ist das zeitliche Verhalten von der sogenannten Vorsortierung abhängig und es kann sich im Worst Case ${\mathcal {O}}(n^{2})$ ergeben.

Dies wird entweder durch zufällige Auswahl des Pivotelementes sehr unwahrscheinlich gemacht oder es wird mit einigem Aufwand (Histogramme) ein optimaler Pivotwert bestimmt.

Ausführliche Beschreibung von QuickSort!

BucketSort

Bei BucketSort wird über den Wert des Schlüssels mit Hilfe einer Zuordnungsfunktion festgelegt, in welchen Eimer der Datensatz einsortiert wird. Die Anzahl der Eimer wird bei der Erstellung der Zuordnungsfunktion festgelegt. Nach einem Sortierdurchgang befinden sich normalerweise in einem Eimer Datensätze mit unterschiedlichen Schlüsseln. Diese Eimerinhalte müssen also wiederum sortiert werden. Das kann natürlich auch rekursiv mit BucketSort erfolgen, wobei jeweils andere Zuordnungsfunktionen benutzt werden müssen.

Ist die Anzahl m der Eimer auf jeder Rekursionsebene konstant, ergibt sich der zeitliche Verlauf über ${\mathcal {O}}(n\log _{m}n)$ .

Ausführliche Beschreibung von BucketSort!

	In diesem rekursiven Beispielprogramm, das nach einem Integer-Schlüssel sortiert, erfolgt die Bestimmung der zu verwendenden Verteilerfunktion automatisch für jeden Eimer, indem der minimale und der maximale Schlüssel-Wert bestimmt wird und dieser Bereich dann in m Intervalle unterteil wird. Die Sortierung erfolgt stabil und indirekt. Wieviele Eimer auf den Rekursionsebenen zur Anwendung kommen sollen, kann vorgegeben werden. Ist diese Anzahl gleich 2, dann wird ein Quicksort mit optimaler Pivotsuche realisiert. Und hier ist die absolute Besonderheit: Nach der Bestimmung des minimalen und maximalen Schlüsselwertes wird geprüft, ob diese -und somit alle Schlüssel im Eimer- identisch sind. Ist dies der Fall, wird die Rekursion abgebrochen. Sind bei einer Sortierung alle Schlüssel identisch, ergibt sich ${\mathcal {O}}(n)$ und sind sie alle verschieden, ergibt sich ${\mathcal {O}}(n\log _{m}n)$ , jedoch mit der Einschränkung, dass es bei einem 4-Byte-Integer-Schlüssel maximal 32 Rekursionsebenen geben kann, egal wieviele Datensätze sortiert werden sollen. Der Beweis, dass ${\mathcal {O}}(n\log _{m}n)$ die untere Grenze für vergleichsbasierte Sortieralgorithmen darstellt, ist also lediglich eine fehlerhafte Behauptung! Programmbeispiel in C

feste Teilung

Vor Beginn der Sortierung ist der mögliche Wertebereich der Schlüssel bekannt. Soll etwa nach einem ganzzahligen Schlüssel mit 4 Byte sortiert werden, dann entspricht das bei Interpretation als positive Zahl Werten zwischen 0 und etwas mehr als 4 Milliarden. Für Radixsort wäre also klar, dass die Zahlen maximal 10 Ziffern haben können, die Sortierung also nach 10 Iterationen sicher abgeschlossen ist. Und bei ExtraDix ist klar, dass für die Sortierung 4 Iterationen genügen.

RadixSort

RadixSort ist nicht-vergleichsbasiert und stabil. Es wird eine Lochkartensortiermaschine mit zehn Ablageschächten simuliert. Zunächst wird auf die Einerstelle justiert und endsprechend der Endziffer werden die Datensätze in die entsprechend nummerierten Schächte verteilt. Dann werden die Datensätze eingesammelt, die Sortiermaschine auf die Zehnerstellen ausgerichtet und die Karten wieder auf die Schächte verteilt. Dieser Zyklus von ausrichten, verteilen und wieder einsammeln wird solange wiederholt, bis nach der höchstwertigen Ziffer sortiert ist. Der Zeitbedarf für Sortierungen kann über ${\mathcal {O}}(n\log _{10}N)$ abgeschätzt werden. N ist hierbei die maximal mögliche Anzahl verschiedener Schlüssel. Eine Vorsortierung hat keinen Einfluss auf die Geschwindigkeit, weshalb es keinen Worst oder Best-Case gibt.

Ausführliche Beschreibung von RadixSort!

ExtraDix

Bei ExtraDix handelt es sich um eine Erweiterung von RadixSort; daher auch der Name Extended raDix. Von diesem Algorithmus wird eine Sortiermaschine mit 256 Schächten simuliert. Dieser Algorithmus besteht aus einigen Varianten, die es ermöglichen, nach jedem gängigen Datentyp zu sortieren. ExtraDix gehört zu den stabilen Algorithmen und arbeitet zudem indirekt. Der Zeitbedarf für Sortierungen kann über ${\mathcal {O}}(n\log _{256}N)$ abgeschätzt werden. N ist hierbei die maximal mögliche Anzahl verschiedener Schlüssel. Eine Vorsortierung hat keinen Einfluss auf die Geschwindigkeit, weshalb es keinen Worst oder Best-Case gibt.

Der Speicherbedarf ergibt sich zu 4kByte + 24 * n, was man als durchaus moderat bezeichnen kann.

Der komplette Sourcecode kann von SourceForge unter dem Stichwort ExtraDix bezogen werden.

Link auf die ausführliche Beschreibung von ExtraDix!

Quellen

Algorithmen und Datenstrukturen 1 - 4. Vorlesung - Peter F. Stadler Universität Leipzig (Ifi)
Sortieralgorithmen bei Wikipedia
Übersicht Sortieralgorithmen von Stefan Baur