Alle Sortieralgorithmen wurden zu einem ViAApplet zusammengefaßt. Die verschiedenen Algorithmen werden über die Choice am unteren Bildrand ausgewählt. Durch Klick auf den "scramble" Button, wird ein neues zu sortierendes Feld mit zufälligen Werten initialisiert. Dieses kann dann über den "sort" Button mit dem aktuell ausgewählten Algorithmus sortiert werden. Falls man diesselben Werte noch einmal mit einem anderen Sortieralgorithmus sortieren möchte, so ist der Button "re-init" zu drücken.
Die Elementanzahl wurde aufgrund von darstellungstechnischen Gründen auf 32 Elemente begrenzt. Dies trifft bei CountingSort auch auf den maximalen Elementwert zu, da bekannterweise ein weiteres Array mit maximal 32 Elementen angelegt und angezeigt wird. Weiterhin verhält sich die Animation auf Java Vitual Machines ohne just-in-time Compiler und/oder langsamen Rechner sehr träge. Ich empfehle daher standesgemäßen Software/Rechner einzusetzen. Dieses Applet soll nur die prinzipielle Funktionsweise der verschiedenen Algorithmen zeigen, nicht aber deren Verhalten bei großen n. Weiterhin wurde kein besonderer Wert auf stabile (ich meine nicht im Sinne von absturzfreudig :-) Sortieralgorithmen gelegt.
| Name des Algorithmus | |
| Vertauschung zweier Elemente | |
| Zusammenfassung | |
| Fehlermeldung | |
| sonstige Meldungen |
Für diejenigen, denen die derzeitige Appletgröße von 640 x 480 Pixeln zu klein ist, wird hier eine 100% Version angeboten. Dazu wird es notwendig den Browser vorher zu maximieren.
Ein recht bekannter Algorithmus ist BubbleSort. Wichtigstes Merkmal ist seine 2-Schleifen-Struktur, die BubbleSort zwar einfach implementieren läßt, ihm dafür aber auch eine quadratische Ordnung beschert. Die äußere Schleife i läuft von 2 bis n, die innere Schleife j über alle Elemente von n bis i. Innerhalb der inneren Schleife werden jeweils die Elemente j-1 und j miteinander verglichen und gegebenenfalls ausgetauscht.
Viele Leute werden sich wohl fragen, warum hier CountingSort auftaucht obwohl es doch gar nicht in das Schema der anderen Sortieralgorithmen passt. Tatsächlich tanzt CountingSort ein bißchen aus der Reihe, weil dieser Algorithmus (a) eine Eingangsinformation über den Wertebereich 1...k der zu sortierenden Elemente benötigt und (b) auch noch zwei zusätzlichen Arrays alloziiert. Ich habe mich trotzdem entschieden, ihn zu visualisieren, da CountingSort in O(n) sortiert. Im großen und ganzen läuft CountingSort in 4 Phasen ab. Zuerst wird ein zusätzliches Array C der Größe k angelegt und mit 0 initialisiert. Danach wird die Anzahl eines jeden Elementwertes bestimmt und in C abgelegt. Diese Anzahlen werden dann in einer Weise von links beginnend aufsummiert, das für alle k gilt: Cneu[k]:=Calt[k]+Calt[k-1] (hier: aufsteigende Sortierung). Im der letzten Phase werden nun die unsortieren Elemente mit Hilfe der C Information in das neue, sortierte Feld B kopiert. Dabei ist B[C[A[i]]]:=A[i] für alle i=1,2,...,n. Damit gleichwertige Elemente sich nicht überschreiben wird bei jedem Iterationsschritt C[i] mit C[i]:=C[i]-1 angepaßt. Letzendlich speichert das C Array nichts anderes als die neuen Indizes der zu sortierenden Elemente.
DirectSelectionSort versucht die Anzahl der Vertauschungen zu reduzieren indem es zuerst immer das kleinste bzw. größte Element der rechteren Elemente sucht und dieses mit dem aktuellen Element vertauscht. Dieser Algorithmus besteht aus zwei Schleifen. Die äußere kennzeichnet das aktuelle Element und läuft über alle Elemente von 1 bis n-1. Die innere versucht ab dem aktuellen Element das kleinste bzw. größte Element zu bestimmen. Falls das gefundene Element nicht das aktuelle (Start-)Element ist, wird getauscht.
Wer die Datenstruktur Heap kennt, der kann sich wahrscheinlich schon denken, wie HeapSort funktioniert. Zuerst wird das unsortierte Feld in einen Heap konvertiert. Da wir schon ein Array besitzen, wählen wir natürlich die Felddarstellung des Heaps, d.h. das erste Element entspricht der Heapwurzel, der linke Sohn eines Nodes i ist 2*i und der rechte ist 2*i+1. Wenn wir nun ein zweites, gleichgroßes Feld zu Verfügung hätten, dann würden wir solange die Heapwurzel entnehmen und dem zweiten Feld anhängen bis der Heap leer ist. Da wir aber kein zweites Feld anlegen wollen, müssen wir etwas tricksen. Mit jedem Schritt wird der Heap um ein Element kleiner, d.h. am Ende des Heaparrays wird immer ein Platz frei, den wir für unser sortiertes Feld nutzen können. Wir starten also, indem wird die Heapwurzel mit dem letzten Element des Heaps vertauschen und jeweils die Heapgröße um 1 reduzieren. Dabei vergessen wir nicht, daß die Heapeigenschaft (größtes bzw. kleinstes Element ist die Wurzel) verletzt wurde und wir ausgleichen müssen. Das ganze läuft solange bis wir beim ersten Element angelangt sind, welches schon richtig liegt. Bei dieser Vorgehensweise muß die Heapwurzel bei aufsteigender Sortierung immer das größte Element und bei absteigender Sortierung das kleinste Element beinhalten.
InsertionSort ist wohl der einfachste Sortieralgorithmus überhaupt. Man sortiert von links nach rechts indem man das aktuelle Element solange nach links durchrutschen läßt, bis es passt. Dabei beginnt man logischerweise mit dem zweiten Element, da sich das Erste schon an der linken Grenze befindet. Es gibt noch eine Mutation von InsertionSort, welche mit weniger Vergleichen auskommt. Hierbei wird davon ausgegangen, daß die linkeren Elemente ja schon sortiert sind. Wir können somit die Grenze, zu welcher das aktuelle Element durchrutschen soll, schon vorher mit Hilfe einer binären Suche bestimmen. Im Gegensatz zu dem normalen InsertionSort, wo immer mit dem linken Nachbarn verglichen wird, ergibt sich ein besseres Vergleichsverhalten.
MergeSort arbeitet rekursiv in zwei Phasen. Zuerst wird das zu sortierende Intervall genau in der Mitte aufgeteilt. Das geschieht solange bis nichts mehr zu teilen ist, also bis die Intervallänge gleich 1 ist. Beim obligatorischen Wiederaufstieg wird dann gemischt. Dazu brauchen wir ein zweites Array, das beide Intervalle temporär aufnehmen kann. Wir vergleichen jeweils das linkeste Element beider Intervalle und kopieren das kleinere bzw. größere Element in das temporäre Feld. Am Ende ist das temporäre Array sortiert und wir können weiter aufsteigen.
ModifiedBubbleSort erweitert BubbleSort nur um eine Abbruchbedingung. Man kann nämlich davon ausgehen, daß die Folge schon sortiert ist, wenn in der inneren Schleife beim vorangegangen Durchlauf keine Elemente mehr vertauscht wurden. Dennoch ist dieser Algorithmus immer noch von quadratischer Ordnung.
QuickSort macht seinem Namen alle Ehre. Es ist in der Tat eines der schnelleren, internen Sortierverfahren. Es funktioniert nach dem Teile-und-Hersche-Prinzip, d.h. der Algorithmus zerlegt die zu sortierende Folge in zwei unabhängige Teile und sortiert diese dann rekursiv weiter. In jedem Rekursionsschritt wählt man ein beliebiges Element (Pivotelement) aus dem Intervall aus. Dieses dient dann sozusagen als Grenze. In unserem Falle wählen wir immer das linkeste Element des Intervalls. Von außen beginnend, versucht man dann alle kleineren Elemente auf die linke Seite und die größeren auf die rechte Seite zu bringen (hier: aufsteigende Sortierung). D.h. man partitioniert das Intervall nach dem Pivotelement. Die Rekursion endet, wenn die Intervallänge 1 beträgt, also dieses Intervall auf alle Fälle richtig sortiert ist.
Diese QuickSort Variante unterscheidet sich insofern vom Original, daß das Pivotelement zufällig gewählt wird. Diese Vorgehensweise bringt im täglichen Leben Vorteile gegenüber fest gewählten Pivotelementen. Nehmen wir einmal an, daß die Folge schon vorsortiert ist, aber genau in verkehrter Richtung. Schauen wir uns jetzt den Aufrufbaum von QuickSort an, so werden wir feststellen, daß er in ein listenähnliches Gebilde entartet ist. Der Aufrufbaum von RandomizedQuickSort wird trotzdem ausgeglichen sein. Naja, vielleicht auch nicht. Das hängt ganz alleine von der Verteilung der Zufallszahlen ab. Es kann natürlich auch passieren, daß etwas ähnlich Entartetes herauskommt, ist aber unwahrscheinlich bei großen n (oder wie war das mit der Gaußchen Glockenkurve?). Zusammenfassend kann man also sagen, daß RandomizedQuickSort durch sein nichtdeterministisches Verhalten unabhängig von der Eingabefolge sortiert. Sein absolutes worst-case Verhalten ändert er dennoch nicht.
ShakerSort modifiziert BubbleSort in der Weise, daß die Durchlaufrichtung bei jedem Durchlauf wechselt. Es werden auch hier immer die benachbarten Element j-1 und j verglichen und gegebenenfalls vertauscht. Die äußere Schleife terminiert sobald die linke Durchlaufgrenze größer als die rechte ist. Nichtsdestotrotz bringt ShakerSort keine wesentliche Verbesserung gegenüber BubbleSort.
Der Clou an ShellSort ist die Tatsache, daß die Elemente mit verschiedenen Schrittweiten (Distanzen) vorsortiert werden. Man beginnt mit einer relativ großen Distanz ( d<n/2 ) und vergleicht/vertauscht die Elemente d*k+x und d*(k+1)+x mit k=0,1,2,... und x=1,2,...,d solange bis ein berechneter Index außerhalb des gültigen Wertebereiches 1...n liegt bzw. alle x abgearbeitet sind. Danach wird die Distanz veringert und von neuem sortiert. Das geschieht solange bis d=1.