Sortieren Animation Sortieralgorithmus Visualisierung Sortieranimation Sortierverfahren Sortiervisualisierung

Sortierkino - ein Sortieranimationsprogramm

Sortierkino

Ein Sortieranimationsprogramm


Sehr geehrter Besucher,

herzlich willkommen auf meiner Internetpräsenz „Sortierkino“!


Das Sortierkino ist ein in der Programmiersprache Pascal geschriebenes und mit der Entwicklungsumgebung Delphi erstelltes Windows-Programm für den Windows-Desktop (also keine „App“ für „Modern UI“, vormals „Metro“ ab Windows 8) zum Veranschaulichen etlicher Sortierverfahren. Sie können sich über dieses Programm und seine (nicht nur theoretischen) Grundlagen anhand der linken Menüpunkte informieren und es dort auch herunterladen.

Es beinhaltet über 125 Sortierverfahren mit den unterschiedlichsten Merkmalen (Sortiergeschwindigkeit, Adaptivität, (In-)Stabilität, Speicherbedarf, Parallelität / Simultaneität und ggf. weitere) und bietet eine Fülle an Einstellmöglichkeiten.

Mein persönlicher Favorit dabei ist die zu sortierende Startmenge, die mit „natürliche Zahlen (je einmal)“ (in der obersten Combobox „Werterzeugung für die Startmenge“) und „aufsteigend, größtes Element vorn“ (in der zweitobersten Combobox „Struktur der Startmenge“) gebildet wird, sortiert von Swirlsort. Probieren Sie es einfach aus, so etwas sahen Sie zuvor sicher noch nie!

Als besondere Zugabe sind in diesem Programm sogar 14 Mischungsalgorithmen enthalten („implementiert“).

Viel Spaß und Unterhaltung!




Sortieren


zurück zum Seiteanfang

Was heißt Sortieren?

Sortieren heißt der Worbedeutung nach Ordnen, Gruppieren oder Separieren von Objekten anhand ihrer Sorte. Sortieren kann man z.B. ein Gemenge aus Schrauben und Muttern oder Lebewesen nach dem Geschlecht oder der Artzugehörigkeit, also nach qualitativen Merkmalen, eben der allgemeinen Kategorie, die hier „Sorte“ genannt wird (und worunter sich alles mögliche subsumieren läßt). Ordnet man nur nach der Größe, der Wertigkeit oder anhand einer anderen quantitativen Größe, wie es meistens der Fall ist, handelt es sich eigentlich nur um ein „Ordnen“, und die Bezeichnung „Sortieren“ ist genaugenommen falsch, wird hier aber beibehalten, da sie sich allgemein durchgesetzt hat.

Wir sortieren im alltäglichen Leben manchmal und dann meistens intuitiv, jedenfalls nicht streng i.S. eines konkreten Verfahren bzw. konkreten Algorithmus', so die Bücher im Regal (z.B. alphabetisch), Briefe und Photographien anhand ihres Alters / Entstehungsdatums oder aufgenommene Spielkarten anhand ihres Wertes, wir bringen diese Elemente anhand eines Ordnungskritierums/-merkmales in die gewünschte, „richtige“ Reihenfolge.

Doch auch Computer sortieren. Sortiert werden einzelne Daten, wie z.B. Zahlen, aber auch komplexere Daten bzw. Datensätze, dann anhand eines ihrer Merkmale, so z.B. Personendatensätze alphabetisch gemäß ihres Nachnamens oder chronologisch entsprechend ihres Geburtstages. Dieses für das Sortieren benutzte Datenmerkmal heißt Sortierschlüssel und ist eben nur bei einfachen Elementen mit dem Element selbst identisch.

Zum Sortieren von Computerdaten gibt es verschiedene Sortierverfahren bzw. -algorithmen, die natürlich verschiedene Merkmale haben. Sortieren ist eine der häufigsten Beschäftigungen für Computer, dementsprechend wichtig ist die Wahl des geeignetsten Sortieralgorithmus'. Es kommt dabei keinesfalls immer nur auf die Sortierdauer bzw. -geschwindigkeit an, auch der Bedarf an zusätzlichem Speicher in Wechselwirkung mit dem verfügbaren, weiterhin die sog. (In-)Stabilität und auch die Parallelisierbarkeit / Simultaneität / Sequentialität können entscheidende Rollen spielen. Häufig ist auch der Fall gegeben, daß in eine schon sortierte Menge weitere Daten so eingefügt („eingepflegt“) werden müssen, daß diese auch danach sortiert ist. Auch das ist Sortieren, und dafür sind die Sortieralgorithmen ebenfalls unterschiedlich geeignet. Einige Sortieralgorithmen funktionieren sogar auf diese Weise, indem in die schon sortierte Teilmenge „häppchenweise“ unsortierte Teilmengen oder gar nur einzelne Elemente der noch unsortierten Teilmenge nach und nach eingefügt werden. Nicht zuletzt spielt auch die Kompliziertheit eine wesentliche Rolle. Einige Algorithmen sind so kompliziert, daß deren Implementation sehr langwierig und fehleranfällig ist, und deshalb sie bzw. ihr Wirkprinzip teilweise vom Programmierer sogar nicht einmal (vollständig) verstanden werden. Das ist nicht nur eine Kostenfrage, sondern auch eine der Zuverlässigkeit. Derlei Algorithmen sind demnach eher von akademischem Interesse, jedoch bestenfalls kaum praxisrelevant.

zurück zum Sortieren
zurück zum Seitenanfang

Wozu dient das Sortieren?

Computer verlieren zwar - im Gegensatz zu Menschen - auch im Chaos nie den Überblick, sie übersehen schlichtweg nichts, aber die Antwort auf diese Frage ist lapidar: Um das gesuchte tendenziell schneller zu finden, denn in der Ordnung kann man meistens rascher und mit weniger Aufwand als im Chaos finden - das gilt für die Menschen genauso wie für die Computer. Dafür gibt es eine eigene Algorithmengruppe, die Suchalgorithmen. Der Aufwand des Sortierens lohnt sich naturgemäß umso mehr, je häufiger in der sortierten Menge gesucht wird, bei einmaliger Suche ist eher das Suchen in der unsortierten Menge vorteilhaft.

Spätestens bei Computerausgaben (Bildschirm, Ausdruck) sollten die Daten menschengerecht, also sortiert vorliegen.

zurück zum Sortieren
zurück zum Seitenanfang

Was ist eine Sortieranimation?

Sortieren ist ein Prozeß, der - wie alle Prozesse - von, in und mit der Zeit lebt und in bzw. mit der Zeit fortschreitet. Animieren stammt von lat. „animatio“ für „Beförderung“, „Belebung“, aber auch „Lebewesen“, „Geschöpf“. Animieren heißt demnach, zum Leben zu erwecken, beweglich zu machen (s. auch angelsächs. „animal“ für „Tier“).

Man kann Sortieralgorithmen auch ohne bzw. nur mit graphisch veranschaulichter Zeitkomponente bzw. Zeitdimension statisch visualisieren, so z.B. diese Visualisierung des Heapsorts:

Hier noch mehr davon. Letztlich zeigt eine solche Visualisierung ähnlich viel oder eher wenig, wie eine Bewegung in einem Weg-Zeit-Diagramm nicht erkennbar ist, es bleibt demnach vieles von ihrem Wesen verborgen; deshalb die dynamische Visualisierung inkl. echter Zeitkomponente über die Animation.

Nichtdestoweniger, wie eine Weg-Zeit-Diagramm dennoch immerhin die Bewegungsform erkennen läßt, kann auch eine geschickte statische Visualisierung erstaunlich viel Struktur offenbaren und den Sortieralgorithmus preisgeben, so da und erst recht und sogar ästhetisch dort.

zurück zum Sortieren
zurück zum Seitenanfang

Sortierprinzipien


Beim Sortieren gibt es zwei grundlegende Vor- oder Herangehensweisen, die ich so noch nirgendwo beschrieben fand:

Viele Sortieralgorithmen lassen sich mehr oder weniger eindeutig einem dieser beiden Prinzipien zuordnen. Es gibt aber auch Sortieralgorithmen, die sich beider Heransgehensweisen bedienen, so Quicksort und - was nicht offensichtlich ist - Stupidsort.

Deutlich unterscheidbar sind beide Prinzipien auch in meinem Programm in der sog. RadioGroup „Vorsortierung/-mischung“ rechts oben im Bedienformular. Je nach Sortierprinzip kann bzw. muß das Maß der Vorsortierung unterschiedlich eingestellt werden.

Möglicherweise hängt die Klassifikation in stationäre und nichtstationäre Sortieralgorithmen damit zusammen.

zurück zum Sortieren
zurück zum Seitenanfang

Sortierrichtungen

Das Sortieren kann an- oder absteigend erfolgen, und das gilt sowohl für den Sortierverlauf als auch - unabhängig davon - für das Sortierergebnis. Bevorzugt wird im allgemeinen das ansteigende Sortierergebnis, das darin besteht, daß jedes nachfolgende Element (bzw. dessen Sortierschlüssel) nicht kleiner als sein Vorgänger sein darf.

Mir ist unbekannt, ob alle Sortieralgorithmen sowohl ansteigend als auch absteigend gestaltet werden können. Im Sinne des Sortierergebnisses können die Sortieralgorithmen evtl. generell durch „gespiegelte“ Indizierung und / oder inverse Vergleichsfunktionen der Elemente gewonnen werden. Notfalls können sortierte Mengen nach der ansteigenden Sortierung (i.S. des Sortierergebnisses) - die in diesem Programm ausschließlich angwandt werden - durch einfache Mengeninversion („Arrayrotation“, Tausch des ersten Elementes mit letztem, des zweiten mit dem vorletztem usw.) immer in absteigende verwandelt werden, allerdings geht dabei die Stabilität, sofern der vorherige Algorithmus sie aufwies, mit Sicherheit verloren.

Bei einigen Sortieralgorithmen (Bubble-, Insertion-, Merge-, Quick- und Selectionsort) sind sowohl an- als auch absteigende Varianten hinsichtlich des Sortierverlaufes implementiert, um den Unterschied zu demonstrieren.

zurück zum Sortieren
zurück zum Seitenanfang

Sortiergeschwindigkeit

Das wichtigste allgemein in der Literatur genannte Merkmal des Sortierens ist die Sortierdauer („Laufzeit“, „Zeitkomplexität“) bzw. die Sortiergeschwindigkeit. Tendenziell, das ist sicher nicht verwunderlich, sortieren alle Sortieralgorithmen umso langsamer, je mehr Elemente sie zu sortieren haben. Auch bei den schnellsten auf Vergleiche beruhenden Algorithmen, den asymtotisch optimalen Sortieralgorithmen, wächst die Sortierdauer stärker als die Elementeanzahl x („leicht überlineares“ Wachstum: „x*log(x)“), im schlimmsten Falle wächst diese Dauer sogar hyperexponentiell („ xx “) mit der Elementeanzahl. Schneller, nämlich linear mit der Elementeanzahl ansteigend, sortieren nur noch die nicht auf Vergleichen beruhenden speziellen Sortieralgorithmen, die jedoch Einschränkungen haben.

Etliche Sortieralgorithmen sind so langsam, daß sie für ihren praktischen Einsatz, und sei es auch nur für eine überschaubare Elementeanzahl, deshalb nicht infragekommen.

Das Sortieren kann spürbar beschleunigt werden, wenn nicht die zu sortierenden Elemente selbst (im Speicher), sondern nur die sog. Zeiger bzw. Pointer, die auf ihre Speicheradressen zeigen, in die richtige Reihenfolge gebracht werden, jedoch ist der Aufruf, die Adressierung der Sortierelemente dann etwas aufwendiger, außerdem ist diese Programmierung wegen dieses „Adressierumweges“ leider deutlich fehleranfälliger. Während die zu sortierende Elementemenge auch nach dem Sortieren wegen des nur lesenden Zugriffs dieselbe Reihenfolge wie am Sortieranfang hat, haben die Zeiger nach dem Sortieren ihre Reihenfolge geändert: Der erste Zeiger zeigt auf das kleinste Sortierelement, der zweite auf das zweitkleinste usw. Auch das läßt sich mit einer Analogie plausibilisieren: Die Objekte verbleiben in ihren Fächern, jedoch hat man eine geordnete Liste (oder einen Kärtchenstapel): Der erste Listeneintrag (oder das erste Kärtchen) beinhaltet die Nummer des Faches mit dem kleinsten Element usw.

Die im Programm vorgenommene - grobe - Einteilung der Sortiergeschwindigkeit hat nicht zwangsläufig etwas mit der Komplexität zu tun. So wird z.B. Select(ion)sort als schnell beschrieben - was es mit den Elementezahlen, die Monitore mit ihren Auflösungen bieten - auch ist, tatsächlich ist seine Komplexität jedoch quadratisch (begründet in dem überbordenden Suchen in der unsortierten Menge). Ab etlichen tausend Elementen wird es deshalb deutlich langsamer und fällt hinter andere zurück, mit denen es auf dem Bildschirm noch mithalten kann.

zurück zum Sortieren
zurück zum Seitenanfang

Adaptivität

Die Adaptivität steht in engem Zusammenhang mit der Sortiergeschwindigkeit, dennoch sei ihr ein eigener Abschnitt gewährt.

Einige Algorithmen reagieren auf ein erhöhtes Ordnungsniveau der zu sortierenden Menge (vorsortiert, komplett sortiert oder viele gleiche Elemente) dergestalt, daß ihre Geschwindigkeit spürbar zunimmt, dieses Verhalten nennt man Adaptivität (auch Ordnungsverträglichkeit). Andere, eben nichtadaptive Sortieralgorithmen sind diesbezüglich unempfindlich und sortieren unbeindruckt davon mit gleicher Geschwindigkeit bzw. gleichem Zeitaufwand. Ggf. kann diese Adaptivität durch eine Verbesserung eines vorher nichtadaptiven, aber grundsätzlich adpativierbaren Algorithmus' erreicht werden (das ist in diesem Programm beim Bubblesort geschehen). Alle Sortieralgorithmen, die Vergleiche zwischen den Sortierelementen und anschließendem optionalem Elementetausch ((nur) wenn die Elemente die falsche Reihenfolge zueinander haben) vollziehen, besitzen zumindest eine „gewisse Adaptivität“, weil (vor-)sortierte gegenüber völlig chaotischen Mengen weniger Vertauschungen erfordern.

Eine ganz simple und plausible Möglichkeit, den meisten (vergleichsbarsierten) Sortieralgorithmen eine „Grundadaptivität“ zuzuordnen, besteht darin, die zu sortierende Menge vor dem Start des Algorithmus' auf Sortiertheit zu prüfen und den Algorithmus daraufhin nur optional zu starten, die Vorabprüfung sozusagen zum Bestandteil des Algorithmus selbst zu machen. Das ist ggf. ohne zusätzlichen Aufwand möglich, da es Soriteralgorithmen gibt, die ohnenhin am Ende der Hauptschleife auf Sortiertheit prüfen.

Ein adaptiver Sortieralgorithmus kann zusätzlich beschleunigt werden, indem absteigende Elementefolgen bzw. Teilmengen der zu sortierenden Startmenge vor dem eigentlichen Sortieren invertiert bzw. gewendet werden.

zurück zum Sortieren
zurück zum Seitenanfang

Stabiles Sortieren

Ein weiteres, ganz wichtiges Merkmal des Sortierens ist die sog. Stabilität bzw. Instabilität, die sich zudem, im Gegensatz zu anderen Merkmalen, auch auf das Sortierergebnis auswirkt. Damit ist nicht gemeint, daß ein instabiler Algorithmus wegen einer Inkonsistenz, wegen eines Programmier- oder Logikfehlers fehlerhafte Sortierergebnisse zeigt oder dieser Algorithmus oder gar mit ihm das Programm abbricht und im gegensätzlichen Falle ihm dieses Schicksal erspart bleibt. Eine bekannte Internetenzyklopädie schreibt dazu:

„Stabile Sortierverfahren sind solche, die die relative Reihenfolge von Elementen, die bezüglich der Ordnung äquivalent sind, nicht verändern, während instabile Sortierverfahren dies nicht garantieren.“

und an anderer Stelle:

„Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der die Reihenfolge der Datensätze, deren Sortierschlüssel gleich sind, bewahrt.“

Etwas plausibler anhand eines Beispieles: Eine Menge Personendatensätze wird nach dem Geburtstag bzw. -datum oder nach dem Vornamen sortiert. Danach wird diese Menge anhand des Nachnamens sortiert, die ursprüngliche Geburtstags- oder Vornamensreihenfolge wird damit aber wieder zerstört. So kommen alle „Meiers“ vor den „Müllers“, und beide bilden einen jeweils zusammenhängenden Bereich oder Block. Doch „innerhalb“ des Bereiches, in dem „Meier“ oder „Müller“ steht, sind alle diese „Meiers“ und „Müllers“, der vorherigen Sortierung sei dank, garantiert nach dem jeweiligen Geburtstag bzw. Vornamen sortiert, wenn das zweite Sortierverfahren ein stabiles ist, ansonsten ist das eher unwahrscheinlich (wenn auch bei wenigen „Meiers“ oder „Müllers“ nicht ausgeschlossen). Beobachten kann man dieses Phänomen auch in Windows in den Explorerfenstern mit Detailansicht, wenn man Windows die Einträge (Dateien mit ihren Daten) anhand verschiedener Merkmale sortieren läßt. Nach meiner Beobachtung verwendet Windows ein stabiles Sortierverfahren. Weitere Beispiele, die stabiles Sortieren benötigen, wären Tabellenprogramme wie Excel oder Datenbankprogramme wie Access.

Dieses Stabiltitätsmerkmal kann sich über mehrere Sortierungen durchziehen, so daß z.B. alle „Peter Müllers“ einen zusammenhängenden Block bilden und innerhalb dessen die Sortierung nach den Geburtstagen erhalten geblieben ist.

Es gibt durchaus Sortieralgorithmen, die eine stabile und eine instabile Variante / Version besitzen. Da die Stabilität das höhere Sortierniveau darstellt und - außer für Erstsortierungen - das bevorzugte Sortiermerkmal darstellt, denn bereits erledigte (Sortier-)Arbeit möchte man nur selten zerstört sehen, wurden die Algorithmen in solchen Fällen möglichst „stabilisiert“.

zurück zum Sortieren
zurück zum Seitenanfang

In-Situ-Sortieren

Lateinisch „in situ“ (oder angelsächsisch „in place“) heißt am selben Platze, an Ort und Stelle, und bedeutet, daß die Menge dort, wo sie sich befindet, auch sortiert wird. Im Computer wäre das demnach derselbe Speicherbereich. Nur ein konstant großer Speicherbereich, in extremer und Reinform nur ein Speicherplatz mehr ist für die nötigen Tauschvorgänge vonnöten und zulässig. Es liegt auf der Hand, daß einem solchen Sortieren ein gewisser „Flaschenhals“ anhaftet und es ggf. auch langsamer vonstatten geht, als wenn mehr zusätzliche Speicherplätze bereitstünden, die das Sortieren flexibler gestalten könnten. Dafür ist der Bedarf an zusätzlichem Speicher jedoch minimal.

Der Gegensatz dazu ist „ex situ“ bzw. „out of place“. Bei ausreichend zusätzlichem Speicher kann die Sortiermenge während des Sortierens sogar komplett im Speicher verschoben werden, so bei AVL-, B-, Merge-, Skip- und Splaysort.

zurück zum Sortieren
zurück zum Seitenanfang

Simultanes Sortieren

Sortieren ist ein Prozeß, bei dem - abhängig vom gewählten Sortieralgorithmus - ggf. durchaus „an mehreren Stellen“ gleichzeitig bzw. simultan das Ordnungsniveau der zu sortierenden Menge erhöht werden kann. Am offensichtlichsten ist das beim Quicksort, bei dem die Startmenge in zwei Teilmengen aufgespaltet wird (eine mit den kleineren und eine mit den größeren Elementen), die dann nichts mehr miteinander zu tun haben, es finden demnach keinerlei Vergleiche oder gar Vertauschungen zwischen diesen mehr statt. Deshalb können sie auch gleichzeitig, simultan oder auch (zeit-)parallel auf gleiche Weise wie die Gesamtmenge sortiert werden usw. (es handelt sich hierbei um einen sog. selbstähnlichen Prozeß).

Einen Algorithmus, sofern er dafür überhaupt infragekommt, auf eine solche Weise umzugestalten, daß er - mehr oder weniger - gleichzeitig abläuft, heißt, ihn zu parallelisieren, er ist als nötige Voraussetzung dann parallelisierbar. Es gibt demnach die Eigenschaft der Parallelisierbarkeit, der „potentiellen Parallelität / Simultaneität“ als notwendige Voraussetzung der Eigenschaft der (tatsächlichen) Parallelität / Simultaneität. Beides sind verschiedene Eigenschaften, die streng voneinander unterschieden werden sollten. Gibt es jedoch keinerlei parallele Anteile an einem Algorithmus (egal, ob ein Algorithmus nicht parallelisiert wurde oder gar nicht erst parallelisierbar ist), dann läuft er hingegen rein sequentiell ab.

Um einen solchen parallelisierbaren Algorithmus auch parallel zu realisieren, also zu parallelisieren, kommt man nicht umhin, sich mit der sog. Threadprogrammierung zu beschäftigen, wobei es sich hierbei vor allem um Multithread(ing)programmierung handelt, bei der die Anzahl der (Sortier-)Threads variabel ist. Jede Teilsortieraufgabe wird in einem eigenen Thread abgearbeitet. Diese Threads, die gar nicht gleichzeitig starten (können), arbeiten asynchron, aber auch nicht sequentiell, sondern „versetzt gleichzeitig“. Da sie in aller Regel unterschiedlich schnell ablaufen, weil sie verschieden oft und verschieden lang unterbrochen werden, werden sie kaum in der (bzw. der gleichen) Reihenfolge fertigwerden, in der sie begannen.

Bei der Parallelisierbarkeit gibt es deutliche Unterschiede: von hervorragend (Quicksort) und sehr gut (Mergesort) über mäßig (Naturalmerge-, Shear- und Shellsort), ziemlich gering (Oetsort) bis gar nicht parallelisierbar. Teilweise hängt das Maß der Parallelisierbarkeit bis hin zur Nichtparallelisierbarkeit von der konkreten Ausgestaltung des Sortieralgorithmus' ab. Bisher wurden nur Sortieralgorithmen parallelisiert (elf an der Anzahl), die diese Parallelisierung wenigstens halbwegs erkennen lassen. Es ließe sich auch auf in geringerem Maße parallelisierbare ausweiten, doch sind diese dann optisch von ihren rein sequentiell ablaufenden Pendants kaum bis gar nicht mehr zu unterscheiden. Der Aufwand lohnt sich deshalb kaum.

Einen Sortieralgorithmus zu parallelisieren ist das eine. Dieses parallele Wirken aber auch adäquat zu animieren ist das andere. Windows wehrt sich auf unterschiedliche Weise dagegen: Mal ist die Ausgabe auf dem Bildschirm synchroner, als der Prozeß, die Threadmenge intern eigentlich ablaufen sollte (und es vermutlich auch tut), anderenmal ist sie so sequentiell, daß eine Gleichzeitigkeit nicht mehr erkennbar ist. Je mehr Gleichzeitigkeit man der Ausgabe abzuringen sich bemüht, desto eher neigen die Algorithmen dazu, „hängenzubleiben“. Es ist viel Probieren erforderlich, um halbwegs konsistente Ausgaben unter verschiedenen Windows' zu erreichen. Hier stößt man mithin an eine Grenze dieser Programmierung.

Das parallele Sortieren läuft tendenziell umso schneller ab, je stärker der Computer zur Parallelverarbeitung imstande ist, und das hängt in erster Linie von der Anzahl der Prozessoren oder Prozessorkerne ab, sofern das Betriebsprogramm mehrere überhaupt unterstützt, was heutzutage aber selbstverständlich ist. Außerdem wird der Multithreadingalgorithmus nicht mehr beschleunigt, wenn es mehr Threads als Prozessoren oder Prozessorkerne gibt. Auf diese hardwarebedingte Anzahl reagiert das Programm nicht (so können Multithreadingalgorithmen mit mehreren gleichzeitigen Threads auch auf Computern mit nur einem Prozessor(kern) ablaufen, was sich recht zäh gestaltet), jedoch kann die Maximalanzahl gleichzeitiger Threads „manuell“ begrenzt werden.

Inzwischen ist dieses Gebiet mein Steckenpferd geworden. Hinzu kommt, daß ich keine einzige Sortieranimation als Programm fand, die das simultane Sortieren einschließt. Nur auf youtube findet man unter Mühen Animationen mit parallelem Sortieren, dort sind es aber nur Filmchen, bei denen man eben keine Parameter eingeben kann und die auch immer das gleiche zeigen.

zurück zum Sortieren
zurück zum Seitenanfang

Iterativ versus rekursiv

Die Grundstruktur jedes Sortieralgorithmus' besteht entweder aus Schleifen (iterativ) oder im Sich-Selbst-Aufrufen bestimmter Unterprogramme oder gar der eigentlichen Sortierroutine (rekursiv). Oft können diese Strukturen adäquat ineinander transformiert werden, sie sind dann äquivalent, was sich auch in (zumindest nahezu) gleicher Sortiergeschwindigkeit zeigt. Ein sehr einfaches und entsprechend bekanntes Beispiel liefert die Berechnung der Fakultät.

Während jeder iterative (nicht nur Sortier-)Algorithmus in sein rekursives Pendant umgewandelt werden kann, ist bei bestimmten rekursiven Algorithmen, so z.B. dem Quicksort, die Umwandlung in einen iterativen nur trickreich und unvollständig möglich, nämlich indem eine für die Rekursion wichtige Speicherstruktur (der sog. Stack) nachgebildet („emuliert“) und anstatt dieses Stacks entsprechend verwendet wird. Allerdings ist auch diese Umwandlung grundsätzlich als gelungen anzusehen, weil die Hauptstruktur dann eine Schleife ist.

zurück zum Sortieren
zurück zum Seitenanfang

Reine versus Hybridalgorithmen

Während die meisten Sortieralgorithmen „rein“ im Sinne der Umsetzung einer konkreten Idee sind, kamen in der letzen Zeit auch Sortieralgorithmen auf, die Kompositionen / Konglomerate bereits bestehender Ideen sind („umhüllende Sortieralgorithmen“). Selbstredend sind solche Algorithmen aufwendiger als ihre reinen (aber nicht notwendigerweise simplen) Pendants zu implementieren.

Grund für diese Hybriden ist (in erster Linie), daß die Sortiergeschwindigkeit für unterschiedliche Elementeanzahlen unterschiedlich ist, sodaß für Sortierungen großer Elementeanzahlen der eine, für kleinere Abschnitte aber der andere Algorithmus schneller ist.

zurück zum Sortieren
zurück zum Seitenanfang

Besondere Merkmale

Einige Sortieralgorithmen haben weitere, etwas „exotischere“ Eigenschaften: zurück zum Sortieren
zurück zum Seitenanfang

Zugriff auf die Daten(menge)

Alle in diesem Programm benutzten Sortieralgorithmen arbeiten in der komfortablen Situation, auf alle Elemente insofern mit gleichem Aufwand zugreifen zu können, als daß sich alle Elemente während des gesamten Sortierens im (Haupt-)Speicher des Computers befinden. Das ist sog. internes Sortieren. Je nach zu sortierender Datenmenge und Speichergröße kann aber auch jeweils nur ein Teil der Daten, also blockweise von einem externen Speichermedium in den Computerspeicher zum Sortieren geladen, sortiert und anschließend wieder geschrieben werden, das bezeichnet man dann als externes Sortieren und ist natürlich deutlich mühsamer und langwieriger. Denkbar ist sogar der Extremfall, daß dieses externe Sortieren ausschließlich auf diesem externen Speichermedium vollzogen wird, nur zum Vergleichen werden maximal je 2 Elemente in den Hauptspeicher geladen.

Komfortabel ist auch, die Daten(menge) in einem sog. Array, das den wahlfreien Zugriff auf alle Elemente mit gleichem Aufwand ermöglicht, zu speichern. So arbeitet auch dieses Programm. Die Sortiermenge kann jedoch auch z.B. in sog. verketteten Listen vorliegen, bei denen nur ein oder beide Randelement(e) direkt adressierbar ist / sind und man bzw. das Programm sich von diesem / diesen zu den Elementen im Inneren dieser Datenstruktur „hangeln“ muß. Letzteres ist für manche Sortieralgorithmen hinderlicher als für andere.

zurück zum Sortieren
zurück zum Seitenanfang

Relevante Nichtsortieralgorithmen

Sortieralgorithmen verwenden teilweise weitere für sie relevante Algorithmen, die für ihre Eigenschaften, vor allem die Sortiergeschwindigkeit, die (In-)Stabilität und den Speicherbedarf signifikant sind:

Sortierergebnis

Zuvörderst sei hier natürlich die Sortiertheit der Menge (jeder Nachfolger ist nicht kleiner als sein Vorgänger) zu nennen, das ist trivial. Doch die sortierte Menge birgt darüberhinaus noch eine Überraschung: Ihre „sichtbare Oberkante“ ist der (an der Diagonale links unt nach rechts oben gespiegelte) Graph der (kumulierten / kumulativen) Verteilungsfunktion der Wahrscheinlichkeitsverteilung ihrer Elemente.

zurück zum Sortieren
zurück zum Seitenanfang

Mischen - der Gegensatz des Sortierens

Mischen ist insofern der Gegensatz des Sortierens, als daß sein Ziel es ist, Ordnung zu zerstören bzw. Unordnung zu schaffen. Auch dafür gibt es verschiedene Algorithmen.

Auch Mischungsalgorithmen haben verschiedene Eigenschaften hinsichtlich ihrer Geschwindigkeit und ihres Speicherbedarfes. Außerdem haben die meisten von ihnen kein definiertes Ende (das haben in diesem Programm nur das Binär- und das Fisher-Yates-Mischen). Sie müssen deshalb - abhängig vom Maß der wahrgenommenen Unordnung - vom Benutzer „manuell“ beendet werden. Natürlich könnte man auch einen Test einfügen, der die Unordnung - anhand welcher Merkmale auch immer - „mißt“, um das Mischen vom Programm abbrechen zu lassen. Doch das wäre sehr rechenaufwendig und würde das Mischen dementsprechend stark verlangsamen.

In diesem Programm sind insgesamt 14 Mischungsalgorithmen implementiert, die sich teilweise am Mischen von Spielkarten anlehnen (Blättern/Bogen- und Überhandmischen).

Um das Mischen gut verfolgen zu können, ist es ratsam - ganz im Gegensatz zum Sortieren - mit einer möglichst geordneten Elementemenge zu beginnen (sortierte Startmengenstruktur oder „Anzahl n verschiedener Elemente“ auf 1 senken).

zurück zum Sortieren
zurück zum Seitenanfang

Theoriequellen

Über Sortieralgorithmen finden sich unzählige Veröffentlichungen in der Literatur und im Internet. Besondere Schwergewichte sind nach meiner Meinung:

zurück zum Sortieren
zurück zum Seitenanfang




Programm

zurück zum Seitenanfang

Downloads

Von diesem Programm existieren drei Versionen: Eine deutsch- und eine englischsprachige sowie eine Lazarusversion (letztere mit etwas verringerter Funktionalität gegenüber erstgenannten und nur für Experimente). Die Archivdateien enthalten jeweils sowohl die ausführbare Programmdatei als auch alle zum Compilieren (ab Delphi 2) nötigen Quelldateien:

Compiliert wurden die beiden ersten mit Borland Delphi 7. Das ist insofern wichtig, weil das Multithreadingverhalten bzw. die Threadablaufsteuerung (relevant für das simultane Sortieren) der erzeugten Programme (Compilate) je nach verwendeter Delphiversionen unterschiedlich sein kann. Ab Delphi 7 sind die Ergebnisse zufriedenstellend. Die Compilate niedriger Delphiversionen können hingegen sogar ein inkonsistenes Multithreadingverhalten zeigen. Bei Lazarus war die Version 0.9.28.2 (32 Bit) die Programmierumgebung bzw. sein Compiler FPC 2.2.4 der Compiler meiner Wahl.

64-Bit-Programmversionen bzw. Compilate für Windows (64 Bit) können bei Interesse bereitgestellt werden, sind allerdings zum einen deutlich größer und zum anderen nicht nötig, s. Systemanforderungen.

zurück zum Programm
zurück zum Seitenanfang

Systemanforderungen

Das Programm läuft auf jedem Windows-Desktop ab Windows 98 und 2000 (evtl. auch schon ab 95 und / oder NT 4.0) mit beliebigen Bildschirmauflösungen. Bei mir funktionieren alle Algorithmen im Vollbildmodus bis zur WQUXGA-Auflösung (3.840 * 2.400 Pixel). Mir steht derzeit leider kein größerer Monitor zur Verfügung, um darüberhinaus die volle Funktion zu prüfen. Interessieren würde es mich, ob das Programm auch mit 4.096 Pixeln in der Breite (Maximum des 4K-Standards) oder gar auf 5K-Displays (z.B. der neue Bildschirm des Typs „Dell UltraSharp UP2715K“, der immerhin eine sagenhafte Auflösung von 5.120 * 2.880 Pixel sein eigen nennt) im Vollbildmodus funktioniert. Wenn jemand einen solchen Bildschirm besitzt, wäre ich über eine diesbezügliche Mitteilung dankbar.

zurück zum Programm
zurück zum Seitenanfang

Bedienung

Das Programm besteht aus einer einzigen Exe-Datei, an der es nichts zu installieren gibt. Sie wird einfach irgendwo(hin) abgelegt und daraufhin gestartet. Das Programm greift weder lesend noch schreibend auf die Windows-Registrierung zu. Lediglich die Startparameter können optional gespeichert und gelesen werden (s. den letzten Abschnitt in diesem Menüpunkt).

Die eigentliche Bedienung des Programmes ist sehr simpel, sie sollte selbsterklärend und intuitiv möglich sein, auch wenn das beim Programmstart sofort im Vordergrund erscheinende Bedienformular:

wegen der Vielzahl der Einstelloptionen zugegebenermaßen recht vollgepackt, im ersten Augenblicke vielleicht sogar ein wenig „erschlagend“ wirkt. Es sollte jedoch soviel wie möglich auf den ersten Blick erkenn- und softwareergonomisch ohne unnötige Mausklicks bedienbar sein. Ebenfalls zwecks maximaler Softwarergonomie verändert sich die im Hintergrund sichtbare zu sortierende Startmenge sofort entsprechend den umgeschalteten Optionen. Der voreingestellte Farbgradient („Startmenge“) soll dem Sichtbarmachen der (In-)Stabilität dienen.

Änderungen an der Startmenge wie ihre Art, ihre Vorsortierung, die Farbgestaltung der Linien sowie Anzahl benutzter Spalten und Zeilen werden sofort im dahinter-/darunterliegenden (Sortier-)Formular dargestellt bzw. umgeschaltet.

Das Sortieren, das nach dem Druck auf die gleichnamige Schaltfläche beginnt (vorher einen Sortieralgorithmus auswählen), kann mit Tastendruck oder Mausklick auf die Sortierfläche (vorzeitig) abgebrochen werden. Einzige Ausnahme: Mit den Tasten „ + “ und „ - “ (längeres oder wiederholtes Drücken) kann während des Sortierens die Bremse verstellt, das Sortieren also beschleunigt oder verlangsamt werden, dieser Wert ist aber auch vorher schon auf diesem Formular einstellbar. Bitte beachten: „ + “ beschleunigt das Sortieren, vermindert demnach den Bremsfaktor (und umgekehrt).

Nach dem Sortieren erfolgen optional die vorab gewählten Ausgaben in einer sog. Messagebox, und danach wird wieder auf die Starteinstellungen umgeschaltet.

Sämtliche Einstellungen können auch (in eine(r) ini-Datei) gespeichert werden, sodaß das Programm nach seinem Neustart mit genau denselben Einstellungen, mit denen es beendet wurde, wieder zur Verfügung steht. Dieses Speichern erfolgt möglichst in demselben Verzeichnis, in dem sich die Programmdatei befindet, ansonsten, wenn die Ini-Datei dort nicht abgelegt bzw. geschrieben werden kann, dann im immer beschreibbaren Temp-Verzeichnis des aktuellen (Be-)Nutzers. Deshalb ist das Programm auch netzwerktauglich: Es kann auf einem zentralen Serverlaufwerk abgelegt und von verschiedenen Clients aus dort gestartet werden, hat aber auf jedem Clientcomputer die eingestellten lokalen Optionen verfügbar.

zurück zum Programm
zurück zum Seitenanfang

Versionshistorie

30. Juni 2016:

23. Juni 2016:

10. Juni 2016:

30. Mai 2016:

19. Mai 2016:

15. Mai 2016:

12. Mai 2016:

1. Mai 2016:

24. April 2016:

19. April 2016:

12. April 2016:

30. März 2016:

21. März 2016:

19. März 2016:

17. März 2016:

6. März 2016:

29. Februar 2016:

21. Februar 2016:

26. Januar 2016:

24. Januar 2016:

19. Januar 2016:

18. Januar 2016:

17. Januar 2016:

16. Januar 2016:

10. Januar 2016:

zurück zum Programm
zurück zum Seitenanfang

Einsatzfelder

Hier seien Gymnasien für ein erstes Kennenlernen der Sortieralgorithmen im Informatikunterricht genannt. Bestenfalls kann damit soviel Interesse geweckt werden, daß eine lebenslange Faszination und Beschäftigung daraus erwächst. Vielleicht kann es auch in Einführungslehrveranstaltungen der Informatik an Berufskollegs und Hochschulen gute Dienste leisten.

Didaktisch wertvoll sind Sortieralgorithmen - insbesondere ihre visualisierten / animierten Versionen - insofern, als daß sie offensichtlich (im wahrsten Sinne des Wortes) der weitverbreiteten, falschen Ansicht entgegentreten, Algorithmen seien Berechnungsvorschriften. Das sind sie oft, aber eben nicht immer.

zurück zum Programm
zurück zum Seitenanfang

Wie alles begann

Als Freund der Ordnung und der Übersicht erweckten Sortieralgorithmen schon recht früh meine Aufmerksamkeit, ja Faszination. Anfang der 90er Jahre bereits schrieb ich deshalb einmal ein vergleichsweise kleines Sortieranimationsprogramm mit Turbo-Pascal (6.0) für DOS und war schon damals erstaunt, wieviele deutlich verschiedene Lösungswege für ein und dasselbe Ziel möglich sind. Nachdem ich alle aus meiner Sicht wichtigen Sortieralgorithmen aus Robert Sedgewicks Buch „Algorithmen“ implementierte, denn ich wollte es nicht nur auf dem Papier sehen, sondern animiert erleben, war die Neugier(de) zunächst befriedigt, und das Interesse dafür erlosch, zumal andere Dinge in den Vordergrund rückten. Es gab damals auch nur vergleichsweise wenig Möglichkeiten, diese Sache mit vertretbarem Aufwand fortzuführen.

2009, warum auch immer, nahm mein Interesse an dieser Thematik wieder zu, was ich dann mithilfe des Internets anging. Natürlich findet man im Internet eine ganze Reihe Sortieranimationen, die mir jedoch allesamt nicht rundweg gefielen, auch wenn ich die Mühe der jeweiligen Ersteller damit nicht abzuwerten beabsichtige. Entweder waren es recht kleine browserinterne Animationen, für die die aktuellen Browser schon zu neu waren oder nur allzuoft ein sog. Plugin zu installieren war, und auch danach war das Funktionieren nicht gewiß, oder auch in eigenständigen Programmen wurde die Anzahl der zu sortierenden Elemente deutlich kleiner als das darstellbare Maximum (hängt von der Bildschirm-/Monitorauflösung ab) gehalten, veränderbar war diese Anzahl oft genug auch nicht. Die Geschwindigkeit konnte nicht verändert werden. Oft gab es nur wenige Standardalgorithmen und vereinzelte selbstgeschriebene „Exoten“. Es enstand der Wunsch, all' das zu verbessern und zudem „echtes Kinogefühl“ aufkommen zu lassen.

So nahm ich meine Programmieraktivität auch auf diesem Gebiet wieder auf und versuchte mich daran, das auch in Delphi (dem Turbo-/Borland-Pascal-Nachfolger) umzusetzen, wobei mein mit Turbo-Pascal erstelltes Sortierprogramm als Vorbild sozusagen Pate stand. Seitdem läßt mich dieses Thema nicht mehr los, das Programm wuchs und wuchs.

Nachdem ich es jahrelang in zwei Delphiforen veröffentlichte und pflegte, folgt nun dieser eigene Internetauftritt.

zurück zum Programm
zurück zum Seitenanfang

Was nicht implementiert wurde

Von den Anregungen und eigenen Ideen für dieses Programm wurde folgendes zwar teilweise ausprobiert, jedoch letztlich nicht umgesetzt:

zurück zum Programm
zurück zum Seitenanfang

Was das Programm nicht leistet

ist die gleichzeitige Animation mehrerer bzw. verschiedener Sortieralgorithmen, wie hier gezeigt.

Da die gesamte Animation auf dem Bildschirm abläuft und dieser die zu sortierende Startmenge und ihre allmähliche Transformation in die sortierte Endmenge repräsentiert, kann die Verwendung zusätzlichen Speichers nicht dargestellt werden. Das ist insbesondere bei solchen Sortieralgorithmen betrüblich, die zusätzlichen Speicher exzessiv verwenden, um die Daten in eine neu aufzubauende, sortierte Daten(menge) sukzessiv einzufügen oder an diese anfügen, so AVL-, B-, Merge-, Skip- und Splaysort.

zurück zum Programm
zurück zum Seitenanfang

Was noch zu tun wäre

zurück zum Programm
zurück zum Seitenanfang

Lizenz

Das Programm ist mitsamt seinen Quellen frei, es darf mithin beliebig verbreitet, weitergegeben, veröffentlicht (was alles sogar ausdrücklich erwünscht ist) und auch modifiziert und sogar weiterentwickelt werden. Nur sollte sich für seine jetzige, vollständige Form niemand als dessen Urheber ausgeben, der er nicht ist.

Grund dafür ist zum einen fehlendes kommerzielles Interesse, zum anderen, daß dieses Programm weitgehend eine Fleißarbeit war und eine Collage ist, es wurde im wesentlichen zusammengetragen. Was ich aus einem allgemein zugänglichen Fundus kostenlos entnehme, gebe ich an diesen in gleicher Weise auch wieder zurück.

zurück zum Programm
zurück zum Seitenanfang



Danksagungen

Etliche (alphabetisch aufgeführte) Personen halfen mir auf unterschiedliche Weise (teils aktiv über Korrespondenz, teils mit der Zurverfügungstellung von Quellcode(s), teils mit ihren Veröffentlichungen und teils mit ihrem meine Motivation steigernden Interesse) bei der Erstellung und Perfektionierung dieses Programmes. Ohne sie gäbe es das Sortierkino entweder gar nicht, oder es sähe deutlich ärmer aus, auch diese Internetseite hätte bedeutend weniger Inhalt. Nicht aufgeführt wurden die Autoren der Algorithmen, die schon seit langem (teilweise Jahrzehnten) sozusagen Allgemeingut (geworden) sind. Im einzelnen geht der Dank an:

zurück zum Seitenanfang

Kontakt

Sehr geehrter Interessent, Ihre Fragen, Anregungen und Kritik sind jederzeit willkommen. Bitte schicken Sie mir dazu eine e-Mail an: sortierkino@gmx.de
Autor des Programmes und dieser Internetseite: Ansgar Matthes (Dr.-Ing.), Rostock

zurück zum Seitenanfang