Sortieren Animation Sortieralgorithmus Visualisierung Sortieranimation Sortierverfahren Sortiervisualisierung

Sortierkino - ein Sortieranimationsprogramm

Sortierkino

Ein Sortieranimationsprogramm


Sehr geehrter Besucher,

herzlich willkommen auf meiner Internetpräsenz „Sortierkino“!

Wahrscheinlich hat Sie Ihr Interesse für das Sortieren und die dafür existierenden Verfahren hierher geführt. Dann sind Sie hier richtig.

Das Sortierkino ist ein in der Programmiersprache Pascal geschriebenes und mit der Entwicklungsumgebung Delphi erstelltes Graphikprogramm für den Windows-Desktop* 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 250 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. Neben einer Vielzahl an Sortieralgorithmen wurde aber auch auf die Erstellbarkeit mannigfaltig verschiedenster zu sortierender Startmengen Wert gelegt, weil Sortieralgorithmen darauf ggf. unterschiedlich reagieren. Bei bestimmten Startmengen können Sortieralgorithmen in bezug auf ihre Geschwindigkeit sogar „einbrechen“, so z.B. das wegen seiner ansonsten großen Sortiergeschwindigkeit berühmte Quicksort.

Mein persönlicher Favorit (wegen des seltsamsten aller Sortierverhalten) 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 18 Mischungsalgorithmen enthalten („implementiert“).

Vielen Dank schon mal für Ihren Besuch und Ihr Interesse, und ebensoviel Spaß und Unterhaltung!

*also keine „App“ für „Modern UI“, vormals „Metro“ ab Windows 8




Sortieren


zurück zum Seitenanfang

Was heißt Sortieren?

Sortieren heißt der Worbedeutung nach (An-)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, Abfälle anhand ihrer Materialien (und nicht (Müll-)„Trennen“, die waren ja vorher nicht miteinander verbunden), 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“. Das Wort „Sortieren“ ist demnach semantisch (=begrifflich) leicht und zudem fehlerhaft überladen. Die Bezeichnung „Sortieren“ für bloßes „Ordnen“ ist genaugenommen falsch, wird hier aber beibehalten, da sie sich allgemein durchgesetzt hat. Zum Glück ist das nicht nur mir allein, sondern auch Hadmut Danisch aufgefallen. Letztlich hat sich damit eine verbale Schlamperei im Bereich der Computer eingeschlichen und durchgesetzt, wie es dort auch einige andere gibt, so z. B. „Textverarbeitung“ (statt Textprogramm oder Schreibprogram), „Benutzeroberfläche“ (statt Benutzungsoberfläche), „Anwendung“ (statt (Anwendungs-)Programm), „Kopierschutz“ (statt Kopiersperre), „teilen“ (statt verbreiten) und „Menü“ (was eben keines ist, da Wahlfreiheit herrscht).

Das Sortieren ist wahrscheinlich so alt wie die Menschheit, wobei die Anzahl der infragkommenden Objekte deutlich anwuchs, als der Mensch seßhaft wurde und Dinge um sich herum anzuhäufen begann, also seit (dem Beginn) der Jungsteinzeit (Neolithikum). Überschaubar war diese Menge dennoch, sodaß das Vorgehen beim Ordnungschaffen eher intuitiv denn systematisch war.

Das Problem des Sortierens und auch dessen Lösung sind für den menschlichen Intellekt und die menschliche Intuition ein Kinderspiel, zumal ein gewisser Hang zur Ordnung wahrscheinlich sogar angeboren ist, denn dafür ist dieses Phänomen kulturübergreifend zu weit verbreitet, als es auf rein kulturelles Phänomen zu reduzieren. Interessant wäre, ob dieses Problem bzw. konkret dessen Lösung so fundamental und trivial ist, daß man es sogar auch Menschenaffen beibringen kann / könnte, wenigstens Schimpansen und Bonobos oder gar nur Bonobos, sowohl das Anordnen nach der Größe als auch das Separieren anhand der Sorte. Über derlei Versuche ist mir nichts bekannt und auf die Schnelle auch nichts zu finden.

Auch wir sortieren im alltäglichen Leben manchmal und dann meistens intuitiv, jedenfalls oft 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, aufgenommene Spielkarten anhand ihres Wertes, nach der Wäsche die Kleidungsstücke anhand ihrer jeweiligen Träger und Erledigungen anhand ihrer Wichtigkeit und/oder Dringlichkeit u.v.m. Wir bringen demnach mit dem Sortieren diese Elemente anhand eines Ordnungskritierums/-merkmales in die gewünschte, „richtige“ Reihenfolge (wobei sich bei den Büchern und Spielkarten Insertion- oder Minsertion- und bei den Terminen Selectionsort anböten, ja geradezu aufdrängen).

Doch auch Computer sortieren. Bezeichnenderweise wird der Rechner / Computer sogar in einigen romanischen Sprachen als Ordnungsmaschine angesehen (im Französischen heißt er „ordinateur“, im Spanischen, Galizischen und Katalanischen wird er „ordenador“ genannt), es steht also dort nicht das (Be-)Rechnen, sondern das Ordnen im Vordergrund. So gesehen, sind Sortieralgorithmen fast so fundamentale Algorithmen wie arithmetische. Das systematische Vorgehen beim Sortieren ist nicht nur wegen der exakten, algorithmenbasierten Arbeitsweise der Computer vonnöten, sondern auch wegen der meistens großen bis sehr großen Anzahl zu sortierender Objekte (Daten).

Sortiert werden einzelne Daten, wie z.B. Zahlen und/oder Wörter, 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.

Die meisten Sortieralgorithmen sind nicht nur ziemlich kompliziert, sondern praktisch alle sind fragil, was sie allerdings mit vielen anderen Algorithmen gemein haben. Kleinste Konzeptions- und/oder Programmierunsauberkeiten führen (aller-)meistens zum Zerstören des Sortierzieles, sodaß die Menge nicht mehr zuverlässig komplett sortiert wird. In selteneren, „milderen“ Fällen wird - bei stabilen Sortieralgorithmen - „nur“ die Stabilität zerstört, oder die Sortierdauer erhöht sich deutlich. Bei der Entwicklung dieses darstellungs-/ausgabeorientierten Programmes zeigten sich viele dieser Fehler in den teilweise abenteuerlichsten Mustern während des „Sortierens“ (dynamisch), aber auch nach dessen Ende, also beim „Sortier“ergebnis (statisch). Führen Veränderungen bestimmer Variablen nicht zur Veränderung des Sortierergebnisses, sind in dieser Hinsicht demnach Invarianten (was recht bzw. ziemlich selten ist), und beeinflussen sie dennoch wenigstens den Sortierverlauf, bieten sich diese für einzugebende Parameter an.

Tückisch sind zudem versteckte, selten oder gar nur ausnahmsweise auftretende Fehler bei zunächst für gut befundenen Sortieralgorithmen, auf die man sich deshalb verläßt. Wird das fehlerhafte Sortierergebnis nicht bemerkt, was bei großen, unüberschaubaren Mengen recht wahrscheinlich ist, kann der Schaden immens werden. Timsort z.B. schleppte seit seiner Entwicklung 14 Jahre einen Fehler mit sich, bis dieser endlich entdeckt und behoben wurde. Eigentlich müßte deshalb grundsätzlich nach jedem Sortieren eine Prüfung auf Sortiertheit und - bei stabilen Sortieralgorithmen - auf Stabilität erfolgen.

Interpretiert man eine unsortierte Menge als Anordnungsvariante (Permutation) einer „eigentlich geordneten“*, eher „ordentlichen“ Menge, so ist das Sortieren genaugenommen nichts anderes als das Finden und ggf. Ausführen der inversen Permutation, die die maximale Ordnung, den maximalen Ordnungszustand (wieder-)herstellt.

*Das Partizip II „geordnet“, das einen vorangegangenen Ordnungsprozeß suggeriert, ist hier eigentlich irreführend, da die ungeordnete Menge normalerweise vorher nicht geordnet vorlag.

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. Weitergehende Sortiergründe - vor allem für Gegenstände - finden sich bei Hadmut Danisch.

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ächsisch „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. Auch für jemanden mit Vorkenntnissen dürfte es damit oft schwierig, auf den ersten Blick nahezu unmöglich sein, den dahinterstehenden Sortieralgorithmus zu erkennen, die Informationsmenge reicht entweder nicht aus oder ist nicht menschengerecht genug aufbereitet. Letztlich zeigt eine solche Visualisierung, die eher ein Stilleben ist, ä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.

Animationen sind nicht nur unterhaltsam und „Futter für die Augen“, sondern können zu einem echten Erkenntnisgewinn führen. So sind z.B. eigentlich rekursive, aber iterativ umgestaltete Algorithmen nicht von ihren rekursiven Pendants zu unterscheiden, was darauf schließen läßt, das unterschiedliche Algorithmen zu einem gleichen Prozeß (ihres Ablaufens, ihres Ausführens) führen. Auch ist damit z.B. erkennbar, daß Stupidsort ein Insertionsort ist, obwohl der Algorithmus das keinesfalls erkennen läßt, jedenfalls nicht auf den ersten Blick. So konnte z.B. das im Internet teilweise kursierende simultane Bubblesort in Wirklichkeit als (simultanes) Oetsort erkannt werden, weshalb bisher kein simlutanes Bubblesort implementiert wurde.

zurück zum Sortieren
zurück zum Seitenanfang

Sortierprinzipien


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

Viele, wenn nicht sogar die meisten 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 diesem Programm in der sog. Combobox „Vorsortierung/-mischung“ rechts oben im Bedienformular. Je nach Sortierprinzip kann bzw. muß das Maß der Vorsortierung unterschiedlich eingestellt werden. Nur beim Merge- und beim Quicksort ist das nicht ganz korrekt, denn dieses sind eigentlich rekursiv und wurden je in eine iterative Ersatzstruktur transformiert.

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

Während die erste Teilmenge überwiegend von iterativen Algorithmen realisiert wird, werden für die zweite eher rekursive Algorithmen verwendet.

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 angewandt 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-, Selection- und Slowsort) 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 ggf. spürbar beschleunigt werden, wenn nicht die zu sortierenden Elemente selbst (im Speicher), sondern indirekt 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 Sortiergeschwindigkeit hängt auch von der verwandten Datenstruktur ab. So sind Insertion- und Bubblesort gemeinhin langsam, auch und vor allem deshalb, weil sie i.d.R. Vektoren zu sortieren haben und dabei viele (eigentlich unnötige) Datenbewegungen verursachen. Läßt man diese Sortierverfahren jedoch auf Listen los, entfallen diese Datenbewegungen und werden von vergleichsweise wenigen Datenverknüpfungen ersetzt, die besagten Algorithmen mithin deutlich beschleunigt. Ein weiteres Optimierungspotential ist beim Insertionsort eine effizentere Suche (Intervallhalbierung) in der schon sortierten Teilmenge.

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 zu haben, 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 (z.B. die verschiedenen Heapsorts (nicht jedoch Smoothsort) und Mergesorts (nicht jedoch Naturalmergesort)). 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 (vergleichsbasierten) 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 Sortieralgorithmen gibt, die ohnenhin am Ende der Hauptschleife auf Sortiertheit prüfen.

Ein adaptiver Sortieralgorithmus kann zusätzlich beschleunigt werden, indem absteigende Elementefolgen bzw. Teilmengen (sog. inverse „Run“s) der zu sortierenden Startmenge vor dem eigentlichen Sortieren invertiert bzw. gewendet werden (z.B. Naturalmergesort).

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.

Wenn bspw. eine Liste alphabetisch sortierter Personendateien nach dem Geburtsdatum neu sortiert wird, dann bleiben unter einem stabilen Sortierverfahren alle Personen mit gleichem Geburtsdatum alphabetisch sortiert.“

Etwas ausführlicher: 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 Wahrnehmung verwendet Windows ein stabiles Sortierverfahren. Weitere Beispiele, die stabiles Sortieren benötigen, wären Tabellenprogramme wie Excel oder Datenbankprogramme wie Access.

Das bedeutet also, daß ein Sortieralgorithmus strenggenommen schon dann instabil ist, wenn er das Vertauschen gleich(groß)er Elemente (bzw. solcher mit gleich(groß)en Schlüsseln) nicht sicher ausschließen kann - unabhängig davon, ob das tatsächlich geschieht (i.d.R. jedoch mit sehr großer Wahrscheinlichkeit, außer bei sehr kleinen Elementeanzahlen). In Ausnahmefällen, also bei (sehr) kleinen Elementeanzahlen, kann auch ein instabiler Sortieralgorithmus - scheinbar - praktisch - stabil sein. In der Sortieralgorithmenliste des „Sortierkinos“ steht in jedem Eintrag auch, ob der Algorithmus (in-)stabil ist. Damit ist erstgenannte, strenggenommene Eigenschaft des Algorithmus' gemeint. Zusätzlich kann man sich die (In-)Stabilität zum Ende eines (jeden) Sortiervorganges anzeigen lassen, das ist dann die tatsächliche, „gemessene“ (In-)Stabilität in bezug auf dieses konkrete Sortierergebnis.

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.

Instabile Sortieralgorithmen sind mithin nur für Erstsortierungen unsortierter „Rohdatenmengen“ oder von Mengen mit Elementen, die nur einen Sortierschlüssel haben (bzw. mit diesem identisch sind), uneingeschränkt geeignet. Mit anderen Worten: Stabile Sortierverfahren sind angebracht für:


Es gibt - analog zu den parallelisierbaren Sortieralgorithmen, die parallele und nichtparallele Varianten haben - durchaus Sortieralgorithmen, die eine stabile und eine instabile Variante / Version besitzen, z. B. Trippelsort und diverse Mergingalgorithmen. 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“. Davon abgesehen, kann die Stabilität auch schnell zerstört werden: Statt eines „<“ ein „<=“ (oder umgekehrt) bzw. statt eines „>“ ein „>=“ (oder andersherum), und schon ist es um die Stabilität geschehen (unwahrscheinlicher sogar um das Sortierergebnis schlechthin). Umgekehrt läßt sich die Stabilität mit dem Wechsel solcher Vergleichsoperationen in manchen Fällen erreichen.

Als Faustregel läßt sich sagen, daß Sortieralgorithmen ohne Vertauschungen (z. B. die (Natural-)Mergesort(s) mit einfachem Verschmelzen) wie auch solche mit Vertauschungen nur benachbarter Elemente (z. B. Bozosort 3, Bubble-, Insertion-, Oet- und Shakersort) die Stabilität gewährleisten, Vertauschungen über größere Entfernungen jedoch nicht, letztere also demnach instabil sind. Im Gegenzug können Vertauschungen über größere „Entfernungen“ jedoch das Sortieren beschleunigen, s. die im Programm enthaltene instabile Bubble- und Trippelsortvariante.

Die allermeisten stabilen Sortieralgorithmen funktionieren mit bloßem Zugriff auf die Elemente(schlüssel), sie sind also uneingeschränkt stabil. Es gibt in diesem Programm jedoch auch Sortieralgorithmenm, bei denen die Stabilität nur durch zusätzliches Lesen und Auswerten der Startposition der Sortierelemente bei den Vergleichsoperationen „<=“ und „>=“ erreicht werden konnte. Diese Algorithmen sind demnach nur „bedingt stabil“ und werden so auch tituliert. Werden damit nur einfache Daten, so z.B. Zahlen sortiert, sind diese Algorithmen instabil, allerdings sind gleiche Elemente dann auch nicht zu unterscheiden (gleichen einander wie ein Ei dem anderen), sodaß das nicht in's Gewicht fällt.

Die Stabilität ist keine triviale Eigenschaft: Eine Sortieralgorithmus stabil zu halten oder zu „stabilisieren“ ist mindestens genauso anspruchsvoll, wie ihn zu beschleunigen. Eine besondere Herausforderung ist die Stabilität beim In-Situ-Sortieren.

zurück zum Sortieren
zurück zum Seitenanfang

in situ versus ex situ

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 Engpaß 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-, Patience-, Red-Black-, Skip-, Splay- und Trisort (eine stabile Variante des Quicksorts).

Eine genaue Definition und Unterscheidungsmöglichkeit beider Vorgehensweise fand ich bis heute nicht. Aus meiner Sicht ist ein Algorithmus dann nicht mehr ex situ, sondern in situ, wenn er mit so wenig Speicher auskommen muß, daß sich Tauschvorgänge nicht vermeiden lassen, währendhingegen bei ausreichendem Speicher ausschließlich Verschiebungen möglich sind. Ganz so allgemeingültig ist das aber nicht, da z.B. Bubble- und Insertionsort ohne großen Änderungsaufwand und mit demselben Speicherbedarf (mit nur einem zusätzlichen Speicherplatz!) sowohl auf der Basis von Verschiebungen als auch Vertauschungen realisiert werden können.

zurück zum Sortieren
zurück zum Seitenanfang

Vektor versus Liste

In diesem Programm wird nur eine eindimensionale Datenmenge sortiert (es lassen sich auch mehrdimensionale Datenmengen sortieren), d.h., die Elemente befinden sich in einer Reihenfolge mit eben zwei Enden. Es stellt sich dabei die Frage nach der Struktur der Datenmenge. Am naheliegendsten und einfachsten existieren dafür Datenfelder („Arrays“, eindimensonal als Vektoren, zweidimensional als Matrizen, ggf. noch höherdimensional) oder Listen.

Vektoren haben den Vorteil der freien Indizierbarkeit - wie die Indizes in der Mathematik - und damit des raschen, unkomplizierten Zugriffs auf seine einzelnen Elemente. Schwieriger ist es jedoch, wenn diese Felder bzw. Vektoren in der Länge verändert oder einzelne Elemente aus ihrem Inneren entfernt oder in das Innere eingefügt werden (sollen / müssen). Dann müssen sämtliche folgenden Elemente des Vektors ebenfalls bewegt, konkret um eine Position verschoben werden, was recht aufwendig ist.

Diesen Nachteil haben Listen - vor allem ihre beiden einfachsten Varianten, nämlich die einfach und die doppelt verketteten Listen - nicht. Ihre Elemente kennen jeweils nur ihren Nachfolger und sonst niemanden, bei doppelt verketteten auch ihren jeweiligen Vorgänger. Das hat große Vorteile beim Verändern der Listenlänge oder dem Hinzufügen oder Löschen einzelner Elemente in ihrem Innern. Es müssen nur Einträge in einem bis drei Listenelementen verändert werden. Schwieriger ist es jedoch, zu den einzelnen Listenelementen zu gelangen, da wegen des Fehlens des Index' keine Zugriffsfreiheit herrscht. Es muß sich vom ersten Element vorwärts - oder, bei doppelte verketteten Listen, vom letzten Element abwärts - mühsam zum gewünschten Element „gehangelt“ werden. Ein Beispiel einer einfach verketten Liste ist übrigens das Alphabet. Da man es i.d.R. nur vorwärts mehr oder weniger auswendig lernt und man deshalb immer nur den Nachfolger jedes Buchstabens kennt, kann man es auch nur in dieser Reihenfolge (wenigstens flüssig) aufsagen.

In diesem Programm ist die zu sortierende Menge ein Vektor. Zum einen, weil es die Algorithmen einfacher gestaltet, zum anderen wegen des starken Graphik(ausgabe)bezuges. Dennoch gibt es in diesem Programm auch Sortieralgorithmen mit Listen. Zwischen dem Sortiermengenvektor und den jeweiligen Listen wird dann „in einem Rutsch“ elementweise übergeben.

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“ der zu sortierenden Menge 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 zuvor sortiert werden, usw. (es handelt sich hierbei um einen sog. selbstähnlichen Prozeß). Wegen des starken, primären Geometriebezuges ist die Bezeichnung „parallel“ für „gleichzeitig“ aus Sicht des Programmautors unglücklich, hat sich allerdings genau wie „Sortieren“ durchgesetzt und wird demnach wenigstens teilweise verwendet. Sofern diese Gleichzeitigkeit tatsächlich und nicht nur scheinbar (in Form sehr vieler und schneller Umschaltungen zwischen den einzelnen Teilsortierungen) existiert, kann damit auch eine Beschleunigung des Sortierens verbunden sein. Die Geschwindigkeitszunahme ist dabei keinesfalls (indirekt) proportional zum Maß der Parallelität, saloppes Beispiel: Wird immer an zwei Stellen gleichzeitig sortiert, dauert das Sortieren leider länger als die Hälfte der Zeit, die benötigt wird, als wenn immer nur eine Operation zu jedem Zeitpunkt erfolgt. Zum einen zehrt der Koordinations- und Verwaltungsaufwand vieler gleichzeitiger Aufgaben viel der Beschleunigung wieder auf, zum anderen gibt es teilweise Warteverluste beim ungleichzeitigen Beenden von Teilaufgaben, auf deren gemeinsames Ende gewartet wird. Auch im Bereich der menschlichen Wertschöpfung ist es schließlich so, daß etwas, was 10 Mannjahre benötigt (also von einer Arbeitskraft in 10 Jahren geschaffen werden kann), eher nicht von 10 Personen in einem Jahr und schon gar nicht von 100 Personen in einem Zehnteljahr abgearbeitet ist.

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 (das gilt nicht nur für Sortier-, sondern für alle Algorithmen, so z.B. auch für das Verschmelzen / Merging). 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. Als Faustregel läßt sich sagen, daß (nicht nur Sortier-)Algorithmen dann parallelisierbar sind, wenn - zwangsläufig voneinander unabhängige - Dinge in ihnen in inverser oder gar beliebiger Reihenfolge und dann nämlich auch gleichzeitig abgearbeitet werden können. Um das zu verdeutlichen, wurden einige (rekursive) Algorithmen neben dem normalen und dem simultanen auch mit inversem und stackoptimiertem / zufälligem Verlauf implementiert.

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- und/oder Verschmelzungs-)Threads variabel ist. Jede Teilsortieraufgabe wird in einem eigenen Thread abgearbeitet. Diese Threads, die gar nicht gleichzeitig starten (können), sondern versetzt wie bei einem Kanon, arbeiten asynchron, aber auch nicht sequentiell, sondern eben „versetzt gleichzeitig“. Da sie in aller Regel unterschiedlich schnell ablaufen, weil sie verschieden oft und verschieden lang unterbrochen werden, werden sie sogar dann, wenn Sie alle gleichviel zu erledigen haben, im Gegensatz zu einem Kanon kaum in der (bzw. der gleichen) Reihenfolge und schon gar nicht mit den gleichen Zeitabständen fertigwerden, in der / mit denen sie begannen.

Was in der von der Programmierung abstrahierten Theorie noch recht simpel anmutet, weil man es auch im alltäglichen Leben so kennt (A erledigt dieses, B erledigt jenes, evtl. noch mehr Beteiligte, alle starten - mehr oder weniger - gleichzeitig, und wer fertig wird/ist, meldet es dem/den jeweils anderen und/oder seinem Vorgesetzten), hat in der Programmierung seine ganz eigene Tücken, seine Detailteufel. Teuflisch ist auch, daß man immer wieder auf die Denkweise hereinfällt und man sich doch von ihr lösen muß, daß die Dinge in der Reihenfolge stattfinden bzw. beendet werden, in der sie notiert sind bzw. begannen. Diese Gleichzeitigkeit, Asynchronizität und ggf. andere Beendigungs- als Startreihenfolge sind Dinge, die einem nicht immer bewußt sind, für die unser Denken im Verlaufe der Evolution wohl nicht optimiert wurde, auch wenn neuerdings modern ist, seine „Multitaskingfähigkeit“ hervorzuheben. Die Suche der Programm(ier)fehler über das sog. Debuggen ist bei Multithreadingalgorithmen zudem erschwert bis unmöglich, also muß sie stärker als sonst über das Betrachten des Quellcodes und vor allem Hineindenken in den Ablauf erfolgen.

Bei der Parallelisierbarkeit der Sortieralgorithmen gibt es deutliche Unterschiede: von

Gerade die im drittletzten Punkt genannten Sortieralgorithmen benötigen Threads mit nur sehr geringem Arbeitsumfang: Jeweils zwei Elemente vergleichen und optional (wenn sie sich in der i.S. der Sortierung falschen Reihenfolge befinden) vertauschen. Das hat eine stark (quadratisch) mit der Anzahl der zu sortierenden Elemente wachsende Threadanzahl zur Folge, die Windows schnell an seine Leistungsfähigkeit bringen kann: Das Programm bleibt dann einfach ohne die Erzeugung neuer/weiterer Threads stehen (auch wenn die Anzahl gleichzeitiger Threads zu jedem Zeitpunkt recht gering bleibt), auch wird weder ein Fehler von Windows ausgegeben noch läßt sich ein Fehler vom Programm auslesen. Meine Experimente ergaben z.B. auf einem Windows XP, daß nach ca. 337.000 Threads Schluß ist, auch dann, wenn diese Anzahl erst nach wiederholten Multithreadsortierungen erreicht wird, diese Grenze ist nicht zu überschreiten (außer evtl., aber auch nicht sicher durch einen Neustart des Programmes). Auf Windows 7 ist diese Maximalanzahl deutlich höher, aber auch dieses Betriebsprogramm wird letztlich davon über Gebühr beansprucht, der Speicherbedarf wächst ins Uferlose. Sicher ist das eine Qual für Windows, eine „Vergewaltigung“ des Betriebsprogrammes und auch nicht im Sinne des Erfinders, eher ein Mißbrauch der Threadfunktionalität. Zudem ist der Verwaltungsaufwand für das ständige Erzeugen und Beenden der Threads dermaßen hoch, daß die Algorithmen deutlich langsamer als ihre nichtsimultanen Originale ablaufen. Plakativ ausgedrückt: Der Computer hat mehr mit den Threads als mit der eigentlichen Sortierung zu tun. Zurück zur Parallelisierbarkeit: Teilweise hängt sie auch von der konkreten Ausgestaltung des Sortieralgorithmus' ab, sodaß bei manchen Sortieralgorithmen verschiedene Varianten - parallel(isierbar)e und nichtparallel(isierbar)e - möglich sind, analog zur Stabilität.

Einen Sortieralgorithmus zu parallelisieren ist das eine. Dieses simultane 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 abläuft (das ist unschön, weil unrealistisch, aber wenigstens noch simultan), anderenmal ist sie so sequentiell, daß eine Gleichzeitigkeit nicht mehr erkennbar ist (völlig inakzeptabel, da kein Unterschied zur reinen Sequentialität). Der Grund für diese Schwierigkeiten, asynchron, aber nicht parallel und schon gar nicht sequentiell darzustellen, ist, daß die für die Ausgabe nötigen Zugriffe auf den Bildschirm (Linienzeichnenbefehle) meistens gleichzeitig und damit konkurrierend erfolgen, jedoch über eine Synchronisation nur sequentiell auf den Bildschirm erfolgen dürfen bzw. können, denn die Bildschirmausgabe erfolgt nicht per Multithreading, sondern die Graphikbefehle werden nacheinander abgearbeitet. Hinzu kommen konkurrierende (gleichzeitige lesende und/oder schreibende) Zugriffe auf gemeinsame Variablen aus verschiedenen Threads, was i.d.R. durch sogenannte kritische Abschnitte geschützt (also sequentialisiert) werden muß. Je mehr Wirklichkeitstreue man der Ausgabe abzuringen sich bemüht (ggf. auch durch behutsames Weglassen der Synchronisation und/oder Verkleinern/Weglassen der kritischen Abschnitte), desto eher neigt das Programm dazu, „hängenzubleiben“ oder sich mit einer Fehlermeldung „zu verabschieden“. Die verschiedenen Implementationen der Thread-Funktionalität in verschiedenen Delphi-Versionen kommen hinzu. Es ist viel Probieren bei dieser äußerst undankbaren und erfolgsunsicheren, aber auch faszinierenden Programmierung erforderlich, um halbwegs konsistente Ausgaben unter verschiedenen Windows' zu erreichen. Schon mit einer anderen Delphi-Version compiliert oder auf einem anderen Windows laufengelassen, kann das Ergebnis fragil sein, deshalb kann ich für nichts garantieren und bin über jedwede Rückmeldung dankbar. Hier stößt man mithin an eine Grenze dieser Programmierung. Meine Wahl fiel letztlich auf Delphi 7. Bis Delphi 5 laufen das simultane rekursive Bitonicmergesort und einfache simultane rekursive Mergesort, das die größte Anzahl gleichzeitiger Threads erzeugt, auf Windows XP (und kleiner?) völlig synchron, mit Delphi 6 sind auf Windows XP schon zarte Ansätze einer Asynchronizität zu erkennen. Erst ab Delphi 7 sind bei diesen Algorithmen die Ergebnisse zufriedenstellend (fehlerfrei und eben asynchron).

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 bzw. 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 aktive (!) 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 ablaufen, was sich allerdings recht zäh gestaltet), jedoch kann die Maximalanzahl gleichzeitiger Threads „manuell“ begrenzt werden. Da die Graphikausgabe letztlich nur in einem Thread abläuft, ist diese der Engpaß (neudeutsch „Flaschenhals“), weshalb die Animationen der Multithreadingalgorithmen keine Chance haben, gegenüber ihren Single-Threads-Pendants signifikant schneller zu sein.

Nicht nur Sortier-, sondern auch viele andere Algorithmen lassen sich parallelisieren, so auch manche Mergingalgorithmen. Implementiert wurden bisher das rekursive simultane (bestens dafür geeignet) und das iterative simultane (sehr gut geeignet) bitonische Verschmelzen, zu finden unter den bitonischen Mergesorts.

Mein letzter bzw. jüngster - und erfolgreicher - Versuch war die Parallelisierung auf zwei Ebenen: Simultanes bitonisches Mergesort (iterativ und rekursiv) mit jeweiligen simultanen (bitonischen) Verschmelzungen; beides wurde und wird im Programm angeboten, jedoch bisher noch nicht miteinander kombiniert.

Inzwischen ist dieses Gebiet mit mittlerweile etlichen implementierten simultanen Sortieralgorithmen mein Steckenpferd geworden, es erforderte mithin den größten Zeitanteil an diesem Program und auch den größten Aufwand bei der Erstellung dieses Internetsauftrittes. 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, z.B. hier, dort sind es aber nur Filmchen, bei denen man eben keine Parameter eingeben kann und die auch immer das gleiche zeigen.

*Angelsächsisch Thread (=Faden) ist in diesem Kontext ein einzelner Berechnungs- oder Anweisungsstrang (Befehlsfolge). In einem (jeden) Prozeß im Computerbetriebsprogramm können im Prinzip beliebig viele davon gleichzeitig existieren und auch ablaufen bzw. abgearbeitet werden.

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 die meisten iterativen (nicht nur Sortier-)Algorithmen wohl recht simpel in ihre rekursiven Pendants umgewandelt werden können, ist der umgekehrte Weg meistens deutlich schwieriger. Oft ist es nur (?) möglich, indem eine für die Rekursion wichtige Speicherstruktur (der sog. Stack) nachgebildet („emuliert“) und anstatt des echten Stacks, der bei der Rekursion zum Zuge kommt, entsprechend verwendet wird. Allerdings ist auch diese Umwandlung grundsätzlich als gelungen anzusehen, weil die Hauptstruktur dann eine Schleife ist. Salopp könnte man solche Algorithmen als pseudorekursiv-stackiterativ (oder nur eines von beiden) bezeichnen. Vollendet ist diese Umwandlung erst, wenn auch dieser (Pseudo-)Stack entbehrlich wird. Beispiele dafür sind im Programm das Dekompositionsmerge und diverse Quicksorts. Bei zwei (pseudo-)iterativen Sortieralgorithmen, nämlich den beiden Naturalmergesorts, die wie einfaches Mergesort aussehen und eben einen (Pseudo-)Stack benötigen, ist dem Programmautor eine Umwandlung in die rekursiven Pendants bisher nicht gelungen und wohl auch nichttrivial.

Um die simultanen / parallelen / Multithreadingalgorithmen hinsichtlich der Anzahl zu sortierender Elemente möglichst uneingeschränkt nutzen zu können, war es nötig, den während der Programmlaufzeit leider konstanten sog. Stackspeicher des Programmes (und damit aller seiner Threads) soweit wie möglich zu reduzieren. Dieser wird jedoch für die Rekursionen benötigt, sodaß das Programm dann ggf. wegen (Stack-)Speichermangels abbricht. Infolgedessen wandelte ich alle von mir wahrgenommenen Rekursionen in Iterationen um. Die Grundideen dazu (nötige Stack-Ersatzsspeicherstruktur, Methodik der Umwandlung) entnahm ich Robert Sedgewicks Buch „Algorithmen“. Diese Transformation hat keinen signifikanten Einfluß auf die Laufzeit und überhaupt keinen auf die Animation der Algorithmen.

Die Rekursion bei Sortieralgorithmen wird gern und bevorzugt zur Realisierung des sog. Verteile-und-herrsche-Prinzips („divide et impera“) verwendet.

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, 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, oder manche funktionieren bei der Sortierung von Teilmengen nicht hinab bis zur kleinstmöglichen, für die Sortierung sinnvollen Elementeanzahl (die da 2 wäre, denn bei einem Element gibt es nichts mehr zu sortieren).

Der vielleicht populärste und inzwischen weitverbreitetste Vertreter könnte Timsort sein. Auch die Shearsorts gehören dazu. Ein Hybridalgorithmus der besonderen Art ist das Merge-Insertion-Sort, das beide Algorithmen in dieser Reihenfolge anwendet und speziell dafür geschaffen wurde, die Anzahl der Vergleiche zu minimieren. Die Implementation dieses Algorithmus' im Sortierkino kann diese Eigenschaft leider nicht verdeutlichen.

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 und ggf. Vertauschen werden maximal je 2 Elemente in den Hauptspeicher geladen. Bei solcherart erschwertem Zugriff könnten als Kompormiß auch nur Elementenummern und ihre Sortierschlüssel in den Hauptspeicher geladen werden, oder man operiert mit Zeigern, wie schon dargelegt.

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

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. Bei stabilen Sortieralgorithmen müssen alle gleich(schlüsselig)en Elemente zudem in der Ausgangsreihenfolge vorliegen, sonst ist er instabil.

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

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:

zurück zum Sortieren
zurück zum Seitenanfang

Selbstähnlichkeit

Ein häufiges, wenn nicht sogar das vorherrschende Strukturmerkmal nicht nur, vor allem aber hierarchischer bzw. hierarchisch strukturierter Systeme in sowohl lebender als auch nichtlebender Natur, Wissenschaft, Gesellschaft, Technik und sogar Mathematik (Fraktale, Algorithmen, Kettenbrüche und -wurzeln, rekursive Funktionen, Mehrfachintegrale) ist die Selbstähnlichkeit, die bedeutet, daß Sub-/Teilsysteme ähnlich wie das Gesamtsystem oder wenigstens das Hyper-/Meta(teil)system aufgebaut - strukturiert - sind, und, da Ähnlichkeit immer beidseitig ist, auch umgekehrt, die Meta-/Hyper-/Gesamtstruktur ähnelt jedem ihrer Teile. Das bedeutet zudem auch, daß die Sub-/Teilsysteme, konkret ihre Strukturen selbst einander ähneln. Diese hierarchieübergriefende Ähnlichkeit kann sich über mehrere, bei mathematischen Objekten sogar unendlich viele Hierarchieebenen (evtl. nur nach „unten“, sichtbar durch Vergrößerung (siehe z.B. die Mandelbrotmenge, das sog. „Apfelmännchen“) und ggf. sogar auch nach „oben“, sichtbar durch Verkleinerung, s. beide Animationen am Sierpinski-Dreieck) hinwegziehen.

Noch eindrucksvoller ist diese Unendlichkeit nach oben und nach unten m.E. bei diesen beiden „Flügen“ über den Sierpinski-Teppich sichtbar:

Erstmalig ausführlich beschrieben und mathematisch formuliert wurde diese autoreferentielle (=selbstbezügliche) System- bzw. konkret Struktureigenschaft vom Mathematker Benoît B. Mandelbrot.

Die Selbstähnlichkeit findet sich auch im Bereich der (nicht nur Sortier-)Algorithmen, doch dazu fand ich bislang in der Literatur nichts. Hierbei muß streng zwischen der Selbstähnlichkeit des Algorithmus' selbst, also der Deskription, des Abbildes, des Planes des (Sortier-)Prozesses, und der des eigentlichen (Sortier-)Prozesses, also des Ablaufens des Algorithmus', unterschieden werden.

Eine elegante Möglichkeit, die Selbstähnlichkeit der (Algorithmenablauf-)Prozesse algorithmisch und programmiertechnisch zu beschreiben bzw. abzubilden, womöglich sogar die einzig adäquate, sofern die Anzahl der Hierarchieebenen unbekannt ist, ist die sog. Rekursion. So enthalten z.B. die rekursiven Versionen der Sortieralgorithmen einen, zwei oder noch mehr (rekursive) Aufruf(e) ihrer selbst. Ja sogar jeder einfache Schleifendurchlauf läßt sich durch einen rekursiven Aufruf ersetzen. Wenn z.B. Quicksort sich im Algorithmus selbst zweimal aufruft, bedeutet das, daß während des Quicksorts der gesamten zu sortierenden Menge (oder eines übergeordneten Teilabschnittes) vollständige Quicksorts, wenn auch kleinerer, untergeordneter Bereiche, durchlaufen werden. Das setzt sich, wenn dieser Algorithmus eben auf der gesamten Sortiermenge abläuft, ggf. über mehrere Hierarchieebenen mit etlichen Aufrufen abwärts hinweg, sodaß zum Schluß nur noch einelementige Sortierbereiche, an denen es nichts mehr zu sortieren gibt, oder zweielementige, die mit einer einfachen Vergleichs- und ggf. Tauschoperation zu sortieren sind, übrigbleiben.

Die Eigenschaft „Selbstähnlichkeit“ des Algorithmus' färbt also auf den Prozeß seines Ablaufens ab und umgekehrt, beide bedingen einander.

Diese Selbstähnlichkeit des Algorithmus', genauer des Prozesses seines Ablaufens ist ggf. auch visuell bzw. dynamisch wahrnehmbar, sofern einem klar ist, daß man auf ähnliche Abläufe in verschiedenen Größenbereichen zu achten hat. Mehr noch: Diese Eigenschaft ist ggf. auch an der teilsortierten Menge, demnach statisch zu erkennen. Besonders gut ist das beim Circlesort der Fall. Am besten ist es, man startet mit einer unsortierten gleichverteilten Menge (voreingestellt) und läßt dann mit Circlesort die Startmenge mit nur einem Schleifendurchlauf vorsortieren. Die Struktur der daraufhin erhaltenen Menge ist gut erkennbar selbstähnlich: Jede Hälfte der vorsortierten Menge sieht etwa wie die auf die Hälfte verkleinerte Gesamtmenge aus, und umgekehrt sieht die Gesamtmenge wie eine auf da Doppelte vergrößerte halbe Menge aus. Weiterhin sehen die Viertel wie verkleinerte Hälften, die Hälften wie vergrößerte Viertel aus, usw., das zieht sich auch noch feiner in kleinere Bereiche hinein, s. Bild:


Man kann aber auch größere Interpretationssprünge machen: Jede Menge enhält vier Viertel oder acht Achtel usw. ihrer selbst und umgekehrt in Richtung Meta-/Hyper(teil)system/-struktur.

Nicht ganz so schön, aber immer noch gut zu erkennen ist die Selbstähnlichkeit auch an der teilsortierten Gesamtmenge beim Quicksort: Dort enthält die Gesamt- bzw. jede Teilmenge (außer der kleinsten) ein ähnliches, verkleinertes Abbild ihrer selbst, allerdings nur einmal:


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. Auch ist die dahintersteckende Mathematik keinesfalls trivial. Die Schwierigkeit geht schon damit los, ein Maß für die Unordnung zu definieren - was ist die perfekte, also die maximale Unordnung? Aus Sicht des Seitenbetreibers am ehesten eine solche, die zu beschreiben die maximale Informationsmenge erfordert.

In diesem Programm sind insgesamt 18 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, die alle nur ein paar hundert kByte groß sind, enthalten jeweils sowohl die ausführbare Programmdatei als auch alle zum Compilieren (ab Delphi 4*) nötigen Quelldateien:

Compiliert wurden die beiden ersten mit Borland Delphi 7, s. simultanes Sortieren. Bei Lazarus nahm ich eine aktuelle Version, um die kontextsensitive bzw. Direkthilfe - mit Einschränkungen - zu ermöglichen.

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.

*Jedoch werden bei mit Delphi 4 erstellten Compilaten einigen simultane Algorithmen nicht zur Zufriedenheit funktionieren. Je höher die Delphiversion, desto ausgereifter und zuverlässiger arbeitet deren Threadklasse, zumindest tendenziell.

zurück zum Programm
zurück zum Seitenanfang

Systemanforderungen

Das Programm läuft (wahrscheinlich) auf jedem Windows-Desktop ab Windows 98 und 2000 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 größeren Bildschirmauflösungen, inbsesondere in der Breite, 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. Zudem greift es 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. Um die anfängliche Verwirrung zu mindern und die Bedienbarkeit zu erhöhen, sind die für bestimmte Einstellungen irrelevante Optionen in Form deaktivierter Bedienelemente abgeschaltet. Ebenfalls zwecks maximaler Softwarergonomie verändert sich die im Hintergrund sichtbare zu verarbeitende 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 Verarbeitungsormular dargestellt bzw. umgeschaltet.

Das Verarbeiten (Sortieren oder / bzw. Mischen), das nach dem Druck auf die gleichnamige Schaltfläche beginnt (vorher einen Sortier-/Mischungsalgorithmus auswählen), kann mit Tastendruck oder Mausklick auf das Verarbeitungsformular (vorzeitig) abgebrochen werden. Einzige Ausnahme: Mit den Tasten „ + “ und „ - “ (längeres oder wiederholtes Drücken) kann während des Verarbeitens die Bremse verstellt, das Verarbeiten also beschleunigt oder verlangsamt werden, dieser Wert ist aber auch vorher schon auf diesem Formular einstellbar. Bitte beachten: „ + “ beschleunigt das Verarbeiten, vermindert demnach den Bremsfaktor (und umgekehrt). Die farbliche Markierung der Vergleiche ist während des Sortierens mit Druck auf „V“ (Vergleiche, Sortierkino) bzw. „C“ (comparisons, sorting cinema) umschaltbar. Derlei Hinweise finden sich auch in der kontextsensitiven Hilfe, die über die Checkbox links unten zuschaltbar ist.

Nach dem Verarbeiten 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 Anwendungsdaten-/AppData-Verzeichnis des aktuellen Benutzers. 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

seit Bestehen dieser Internetseite (Januar 2016, vollständige Änderungsliste hingegen hier):

14. September 2018:

15. August 2018:

17. Juli 2018:

3. Mai 2018:

21. März 2018: Nur interne Änderungen ohne Einfluß auf Bedienung und / oder Animation:

14. März 2018:

8. März 2018:

2. März 2018: Die Möglichkeit, mit jedem Mausklick auf das Verarbeitungsformular eine neue Startmenge zu erstellen, kann jetzt mit einer weiteren Checkbox abgeschaltet werden.

1. März 2018: 6 weitere Mergingalgorithmen nach Jyrki Katajainen & Co. (Quelle s. Danksagungen) hinzugefügt:

11. Februar 2018:

6. Februar 2018:

4. Februar 2018: Drei Mergesorts mit asymmetrischer Partitionierung hinzugefügt, zwei davon erlauben eine Eingabe zur Variation des Größenverhältnisses der Teilarrays.

26. Januar 2018: zwei einfache, schnelle In-Situ-Blocktauschalgorithmen (einer auf Basis von Verschiebungen, der andere auf der Basis von Vertauschungen) implementiert

22. Januar 2018 (Quellen s. Danksagungen): Drei Verschmelzungsalgorithmen hinzugefügt:

11. Januar 2018 (Quellen s. Danksagungen):

6. Januar 2018: 4 neue Sortieralgorithmen hinzugefügt (Quellen s. Danksagungen):

2. Januar 2018: Die Option, mit der einzugebende Parameter hinzu- oder abgeschaltet werden können, ist nunmehr nur noch bei den dafür relevanten Sortieralgorithmen freigeschaltet.

31. Dezember 2017: Stabiles Quicksort mit einem stabilen Partitionsalgorithmus und einen weiteren Blockswappingalgorithmus, beide nach Ronald Linn Rivest, implementiert

28. Dezember 2017:

17. Dezember 2017: 38 Sortieralgorithmen über zusätzlichen optionalen Vergleich der Startpositionen der Sortieralgorithmen bedingt stabilisiert.

10. Dezember 2017: Die globale Stabilisierung nach dem Sortieren wurde beschleunigt; sie funktioniert jetzt außerdem auch nach den simultanen Sortieralgorithmen

5. Dezember 2017:

2. Dezember 2017:

23. November 2017: Blockmerge sowie stabiles und instabiles Partitionsmerge nach Luis Isidoro Trabb Pardo (s. Danksagungen) gemäß dieser Anleitung implementiert.

16. Oktober 2017:

14. Oktober 2017:

7. Oktober 2017: folgende vier neue Sortieralgorithmen hinzugefügt / implementiert:

2. Oktober 2017: folgende vier neue Sortieralgorithmen hinzugefügt / implementiert:

27. September 2017:

31. August 2017: Patiencesort in situ (2 Varianten) und ex situ implementiert.

23. August 2017: Quelltext überarbeitet, den Code (auch den ausführungsrelevanten) dabei etwas komprimiert.

14. August 2017: Den neuen Mergealgorithmus von Prof. John Ellis und Prof. Ulrike Stege erneut überarbeitet (2 weitere Fehler korrigiert und ihn zudem „stabilisiert“, d.h., stabil gemacht).

6. August 2017:

12. Juli 2017: Ein Merge- und ein Naturalmergesort jeweils mit einem neuen Mergingalgorithmus nach Prof. John Ellis und Prof. Ulrike Stege (s. Danksagungen) gemäß dieser Anleitung implementiert. Laut Beschreibung ist er stabil, jedoch konnte die Stabilität in dieser Implementation nicht erreicht werden, Grund unbekannt. Wird sobald wie möglich verbessert.

9. Juli 2017:

7. Juli 2017: Fehler beseitigt, der auftrat, wenn bei den Zufallszahlen die Anzahl n verschiedener Elemente auf 1 gesetzt und danach für die Werteerzeugung die natürlichen Zahlen (je einmal) gewählt wurde(n).

25. Juni 2017:

19. Juni 2017:

1. Juni 2017: Mergesort mit In-Situ-Verschmelzen aus dem zuvor genannten Projekt extrahiert und in dieses Projekt implementiert.

29. Mai 2017:

  • Fehlerkorrektur: Grailmerge „stabilisiert“.

  • Kontextsensitive Hilfe für die Radiogruppe zur Auswahl des Blocktauschalgorithmus' hinzugefügt.

28. Mai 2017:

  • Grailsort in eine originale Variante mit dem Grailmerge und eine mit dem einfachen Verschmelzen aufgespaltet.

  • Merge- und Naturalmergesort je einmal mit dem Grailmerge hinzugefügt.

  • Sqrt-Sort aus dem Projekt wie im Eintrag zuvor implementiert.

  • Rekursives Grailmerge aus demselben Projekt für Grail-, Merge- und Naturalmergesort implementiert.

16. Mai 2017:

  • Grail-, Tim- und Naturalmergesort (das wie einfaches Mergesort aussieht) implementiert. Die beiden erstgenannten wurden aus diesem bzw. jenem Projekt extrahiert.

  • Fehler beseitigt: Beim häufigen Klicken auf das Prozeßformular vor dem Sortieren bzw. Mischen wurden die etliche Startmengenstrukturen manchmal nicht korrekt dargestellt.

3. Mai 2017:

  • Fehler beseitigt, die meistens auftraten, wenn bei den letzten beiden stabilen Quicksorts die Puffergrößen größer als 0 eingegeben wurden.

  • Die aus dem originalen Quelltext übernommene Stackersatzstruktur (Array) für die drei stabilen Quicksorts durch die „hauseigene“ Stackemulatorklasse ersetzt.

27. April 2017:

  • Bei den Vertauschungen wird jetzt nicht mehr der Verschiebungszähler um drei (Vertauschungen bestehen aus drei Verschiebungen), sondern ein eigens eingeführter Vertauschungszähler um ein erhöht.

  • Bubble- und Insertionssort vorwärts und invers liegen jetzt in je einer Variante auf der Basis von Verschiebungen und je einer Variante auf der Basis von Vertauschungen vor.

23. April 2017: Stabiles Heapsort und eine weitere Smoothsort-Variante gemäß diesem bzw. jenem Projekt implementiert.

19. April 2017:

  • Zwei weitere stabile Quicksorts gemäß diesem bzw. jenem Projekt implementiert.

  • wenige geringfügige Detailverbesserungen

11. April 2017:

  • Stabiles Quicksort gemäß diesem bzw. jenem Projekt implementiert.

  • Die Startparameter (für manche Sortieralgorithmen relevant) werden nun in die optionale Speicherung und Ladung der Einstellungen einbezogen.

  • Kleine Fehler beseitigt.

5. April 2017: In-Situ-Variante des Splitsorts implementiert.

1. April 2017:

  • Zähler für die Threads und optionales Anzeigenlassen dieses Wertes nach Sortierende implementiert.

  • Fehler, daß manche simultanen Bitonicmergesorts nicht starteten, korrigiert.

29. März 2017:

  • Das iterative und das rekursive simultane Bitonicmergesort haben jetzt - neben dem einfachen bitonischen Verschmelzen, das sie als Verschmelzungsverfahren schon hatten - jetzt je auch ein iteratives simultanes bitonisches und ein rekursives simultanes bitonischesVerschmelzen bekommen (Simultaneität auf zwei Ebenen).

  • Das Merge- und das Naturalmergesort mit dem stabilen Verschmelzen von Ellis und Markov haben jetzt je auch eine instabile Versions des Verschmelzens der genannten Autoren.

  • Nicht nur die Position des Bedienformulares, wie es schon lang möglich ist, sondern nunmehr auch die Position des Prozeßformulares (das, auf dem das Sortieren bzw. Mischen stattfinden) wird jetzt vom optionalen Speichern und Laden erfaßt, sofern das Prozeßformular einen umgrenzten bzw. Fenstermodus hat und mithin verschiebbar ist.

20. März 2017:

  • In die Liste der Vorsortierungsalgorithmen wurden Merge- und Quicksort je invers und zufällig sowie zwei weitere Mischungsalgorithmen (Fisher-Yates 1.2 und 2.2) aufgenommen.

  • Mit einer weiteren Option (Checkbox) kann nun eingestellt werden, daß die Elemente nur dann getauscht werden, wenn sie ungleich (groß) sind.

  • Quelltext überarbeitet: Die Algorithmen, die von der Vorsortierung und von der eigentlichen Sortierung benutzt werden, in gemeinsame(n) Unterprogramme(n) vereint.

  • Fehlerbeseitigung: Auch die zufallsbasierten Startmengen können jetzt wieder alle Strukturen der Startmenge bilden.

17. März 2017:

  • Smoothsort der Liste der Vorsortieralgorithmen hinzugefügt.

  • 3 weitere Bitonicmergesorts implementiert (stehen am Ende der Bitonicmergesorts: iterativ einfach sowie iterativ und rekursiv simultan).

14. März 2017:

  • Der Mauscursor zur Laufzeit der Verarbeitung (Sortieren bzw. Mischen) kann jetzt zwischen „unsichtbar“ und „hintergrundaktiv“ umgeschaltet werden.

  • Sofern der Mauscursor während der Verarbeitung sichtbar ist, wird nun auch bei den simultanen Sortiervorgängen korrekt angezeigt (Standard: Pfeil und Sanduhr).

  • Simultanes Shellsort mit eigenem Startthread korrigiert, es blieb zuvor stehen.

13. März 2017:

  • Heapsort-Variante von Dr. Hartwig Thomas implementiert.

  • Das Smoothsort von Keith Schwarz und das von Hartwig Thomas sind jetzt abbrechenbar.

  • Die Ini-Dateien für das optionale Speichern des Startzustandes bzw. der Startoptionen werden, sofern sie nicht „neben“ der Programmdatei abgespeichert werden können (also im selben Verzeichnis), jetzt nicht mehr im Temp-, sondern im Anwendungsdaten-/„AppData“-Verzeichnis des jeweiligen Benutzers gespeichert.

  • Mauscursor „Hintergrundaktivität“ während der Verarbeitung (Sortierens bzw. Mischen), das ist in der Standardeinstellung ein Pfeil inklusive Sanduhr

11. März 2017: Smoothsort von Hartwig Thomas (Klasse und Routinen) geringfügig überarbeitet und optimiert

10. März 2017:

  • Smoothsort-Variante von Dr. Hartwig Thomas implementiert

  • Implementation des Smoothsorts von Keith Schwarz geringfügig überarbeitet (Booleanarray wurde durch Integerzahl ersetzt)
  • 3 Fehler korrigiert: Die Schleifenanzahl beim Binärmischen als Vormischungsalgorithmus ist jetzt auf das sinnvolle Maximum begrenzt, und der Sortier- bzw. Mischungsalgorithmus wird jetzt auch nach dem Start eingelesen, sofern die Optionen gespeichert werden. Weiterhin wird das Formular nun hoffentlich endlich an der Position placiert, an der es sich bei gespeicherten Optionen zuletzt befunden hatte.

5. März 2017:

  • Die kontextsensitive Hilfe funktioniert jetzt auch beim Lazaruscompilat (halbwegs), dazu war allerdings die Verwendung eines aktuellen Lazarus' erforderlich.

  • Multithreadingalgorithmen überarbeitet, müßten jetzt noch stabiler laufen
  • Beseitigung weiterer kleiner Fehler und Ungenauigkeiten

3. März 2017:

  • Kontextsensitive Hilfe für einige Bedienelemente implementiert, ist zuschaltbar (funktioniert im Lazarus-Compilat allerdings nicht zufriedenstellend).

  • Checkbox zum Ab-/Zuschalten der Vergleichseinfärbung wiedereingeführt.
  • Layout der Lazarus-Version überarbeitet, ist jetzt an die beiden Delphi-Versionen angepaßt.

2. März 2017:

  • Neues Merge- und Naturalmergesort mit einem einfachen (instabilen und langsamen) Verschmelzen hinzugefügt.

  • 3 neue Vorsortieralgorithmen (Bubble, Insertion und Selection je invers).

  • Die Bubblesort-Variante ist in Wahrheit / Wirklichkeit ein Simplesort und steht jetzt als Simplesort1 in der Algorithmenliste, das ursprüngliche Simplesort1 ist nun Simplesort 1 invers.

  • Quelltext überarbeitet, Änderungen an der Algorithmenliste sind nunmehr schneller und fehlerärmer möglich

  • Fehlerkorrekturen: Quicksort in Mischprozedur (Vorbereitung der Menge zum Sortieren bzw. Mischen) und instabiles Trippelsort, Fehlerquelle beim Abbrechen des stabilen Mergingalgorithmus von Kim/Kutzner 2006 beseitigt (ggf. Division durch 0), lag an der Implementation, nicht am Algorithmus selbst

25. Februar 2017:

  • 3 weitere (simple) Blocktauschalgorithmen hinzugefügt.

  • Die (optionale, wenn Ausgaben erfolgen) Ausgabemessagebox wird jetzt so hinter dem Mauscursor positioniert, daß die Schaltfläche „OK“ unter dem Mauscursor sich befindet.

  • Fehlerkorrektur: Das Bedienformular wurde, sofern die Einstellungen automatisch (beim Programmende) gespeichert und (beim Programmstart) geladen werden, nicht an die letzte Stelle positioniert, sondern immer zentriert.

24. Februar 2017:

  • Das Bedienformulares erhielt ein neues, übersichtlicheres, besser strukturiertes Layout (nicht in der Lazarus-Version).

  • simultanes Bitonicnaturalmergesort implementiert

  • alternatives Smoothsort gemäß dieser Vorlage (C++-Quelltext) implementiert

  • Nach der Tastenkombination „Alt+F4“, gesendet direkt auf das Sortier-/Mischungsformular, außerdem gesendet über die Taskleiste und nach „Task beenden“ im Taskmanager wird das Programm nunmehr korrekt beendet.

11. Februar 2017:

  • mehrere Sortieralgorithmen (Merge-, Oet-, Partit- und Shakersort) der Liste der Vorsortier-/-mischungsalgorithmen hinzugefügt

  • Die Liste der Vorsortier-/-mischungsalgorithmen ist wegen der neuen Einträge nicht mehr in einer Radiogruppe, sondern ab jetzt in einer Combobox enthalten. Damit ist wieder mehr Platz auf dem Bedienformular, dessen Layout etwas umgestaltet wurde.

  • mehrere kleine Fehlerbereinigungen

3. Februar 2017:

  • 10 weitere Varianten des Bitonicmergesorts, davon 4 mit simultanem Verschmelzen, sowie Mergesort mit zufälliger Verschmelzungsreihenfolge implementiert

  • Quicksort in die Liste der Vorsortierungen aufgenommen, das Maß der Vorsortierung kann über die Anzahl der Vorsortierschleifen justiert werden. Das ist eigentlich gemogelt, weil Quicksort rekursiv und eben nicht schleifenbasiert ist, mit der iterierten Variante ist es aber doch möglich.

  • kleine Fehlerbereinigungen

27. Januar 2017:

  • simultanes Pancakesort implementiert

  • Simultanes Quick-, Radix- (MSD rekursiv) und Splitsort überarbeitet und verbessert. Die Interthreadkommunikation ist bei diesen jetzt nicht mehr nur einseitig von den Eltern- zu den Kindsthreads, sondern wie bei den simultanen Mergesorts bidirektional (Duplex).

  • je einen Fehler im simultanen und nichtsimultanen iterativem Mergesort korrigiert

24. Januar 2017:

  • Bitonicmerge- und -naturalmergesort mit iterativem Verschmelzen / Merging (mit rekursivem war es schon vorhanden) implementiert - es entspricht dem sog. bitonischen Sortiernetz oder Bitonicsort

  • kleine Fehlerkorrekturen

21. Januar 2017:

  • 5 neue Sortierverfahren (Circlesort invers, zufällig ablaufend und simultan, Splitsort invers und stackoptimiert)

  • Circle- und Cyclesort der Liste (Radiogroup) der Vorsortieralgorithmen hinzugefügt

  • kleine Fehlerkorrekturen und Optimierungen

15. Januar 2017:

  • Circle- und Cyclesort gemäß dieser Veröffentlichung implementiert

  • kleine Fehlerkorrekturen, Quelltext überarbeitet (Anzahl der Unterprogramme reduziert)

9. Januar 2017:

  • 5 Multithreading-Sortieralgorithmen (Comb-, Insertion-, Oet- und Shakersort, letzteres aus Main- und mit extra Startthread) implementiert

  • kleine Fehlerkorrekturen

2. Januar 2017:

  • je eine Bubble- und eine Trippel-Sort-Variante (beide schneller als ihre stabilen Pendants, dafür instabil) hinzugefügt

  • 2 simultane Partitsorts implementiert (benötigen je maximal zwei parallele Sortierthreads, sodaß die Eingabe des Parameters für die Maximalanzahl gleichzeitiger Threads nur mit 1 sinnvoll ist, wenn eine Begrenzung erwünscht ist/wird)

  • Multithreadingalgorithmen /-klassen überarbeitet (deren interne Anzahl reduziert, die Anzahl der auswählbaren Multithreadingsortieralgorithmen blieb davon unberührt)

  • weitere kleine Codeoptimierungen und Fehlerkorrekturen

23. Dezember 2016:

  • Paralleles Selection- und Splitsort implementiert

  • Checkbox für Vergleichseinfärbungen entfernt

  • Die Vergleichseinfärbungen stehen jetzt (bei) jedem Sortieralgorithmus zur Verfügung; die Umschaltung dafür erfolgt weiterhin über den Tastendruck „V“ (bzw. „C“ in der englischsprachigen Version) während des Sortierens.

  • kleine Fehlerkorrekturen und Codeoptimierungen

15. Dezember 2016: Multithreadingalgorithmen verbessert

11. Dezember 2016: 6 weitere Werterzeugungsmethoden für die Startmenge(n) hinzugefügt

7. Dezember 2016: Implementation der inversen Variante des Slowsorts.

2. Dezember 2016:

  • Die beiden Multithreading-Mergesorts sind in den beiden Delphi-Compilaten jetzt (wieder) mit beliebigen Elementeanzahlen zu betreiben. Die Korrektur erfolgte, indem die maximale Stackgröße von ihrem Minimum (16384 bzw. 4000h) um 1 erhöht wurde. Beim Lazarus-Compilat funktioniert das beim 32-Bit-Compilat hingegen nicht, die Begrenzung der Elementeanzahlen muß bei diesem daher bestehenbleiben.

  • Kleine Fehler korrigiert.

30. November 2016: Multithreading-Sortieralgorithmen geringfügig überarbeitet

24. November 2016:

  • Treesort gemäß dieser Implementation hinzugefügt (der Dank geht an das Delphipraxis-Forumsmitglied „Blup“).

  • Die Anzahl zu sortierender Elemente bei den beiden simultanen Mergesorts ist nun auf 1024 bzw. 2048 begrenzt.

  • Mehrere Fehler korrigiert, Quelltext erheblich überarbeitet (Anzahl der Arrays verringert).

13. November 2016:

  • Fehlerkorrektur: Die Vergleiche bei Slow- und Trippelsort werden (nach Druck auf „V“ in der deutschen bzw. „C“ in der englischen Version) nunmehr auch bei monochromer Liniendarstellung angezeigt.

  • Mehrere kleine, nicht offen sichtbare Fehler korrigiert.

7. November 2016: IniFile-KLasse „TIniFile“ mit „TMemIniFile“ ersetzt (gilt für die beiden Delphi-Programme und dort ab Compilation mit Delphi 4, darunter bleibt TIniFile gültig).

28. Oktober 2016: Option (Checkbox) „maximaler Wertebereich“ hinzugefügt.

20. Oktober 2016: 2 kleine Fehler korrigiert.

16. Oktober 2016: Optimierte Variante des inversen Bubblesorts gemäß diesem Quellcode implementiert.

7. Oktober 2016:

  • Merge-Insertion-Sort-Variante (4-Ford-Johnson) hinzugefügt.

  • Mehrere Fehler beseitigt, der wichtigste ist, daß Splitsort nicht mehr als Block(ver)tauschmethode verfügbar ist, weil es erstens nicht bei jedem Sortieralgorithmus funktioniert und weil es zweitens auch sachlich fehlerhaft ist: Das Blöcke(ver)tauschen ist kein Sortierproblem.

13. September 2016:

  • Splaysort überarbeitet, es zeigt jetzt auch die Anzahl der Vergleiche und Verschiebungen an.

  • Red-Black-Sort (auf Basis einer Klasse für Rot-Schwarz-Bäume) hinzugefügt.

3. September 2016:

  • In die Liste „Werteerzeugung für die Startmenge“ wurde der Eintrag „n Werte, kubisch (Wurzel) verteilt“ hinzugefügt (das Prinzip gilt auch für alle höheren ungeraden Potenzen, genauer Exponenten).

  • Sortieralgorithmus „Merge-Insertion-Sort“ hinzugefügt.

30. Juni 2016: Der Radiogroup „Vorsortierung / -mischung“ wurden zwei Versionen des Fisher-Yates-Mischens hinzugefügt

23. Juni 2016: In die Liste „Werteerzeugung für die Startmenge“ wurde der Eintrag „n Werte, kubisch (Potenz) verteilt“ hinzugefügt (das Prinzip gilt auch für alle höheren ungeraden Potenzen, genauer Exponenten). Das Interessante an dieser Verteilung ist, daß die kumulierte Verteilungsfunktion (erkenntlich an der sortierten Menge) zwar stetig, aber an einer Stelle (nämlich in der „Mitte“) nicht differenzierbar ist.

10. Juni 2016: Die Startmengen lassen sich jetzt über zwei Comboboxen „Werteerzeugung für die Startmenge“ und „Struktur der Startmenge“ übersichtlicher erzeugen - damit ist zudem eine Erhöhung der Anzahl möglicher Startmengen verbunden.

30. Mai 2016: Die Startmenge „Permutation, Quadrat“ ist jetzt auch bei ungeraden Elementeanzahlen ohne Darstellungsmangel.

19. Mai 2016:

  • Jetzt kann bei allen zufallszahlenbasierten Startmengen die Anzahl unterschiedlicher Elemente eingestellt werden.

  • Kleine Fehlerkorrekturen

15. Mai 2016: Binärmischen ist jetzt eine Option in den Vorsortieralgorithmen (auch wenn es genaugenommen kein Sortieren ist). Damit konnten zwei Einträge in der Menge der Startmengen entfernt werden.

12. Mai 2016:

  • Binärmischen, das implizit schon in zwei Startmengen angeboten wird, ist jetzt auch in den Mischungsalgorithmen der Algorithmenliste enthalten.

  • Alle binären Mischungs- und Sortieralgorithmen werden jetzt zentral in einem Unterprogramm ausgeführt.

  • Kleinere Detailkorrekturen und -verbesserungen

1. Mai 2016:

  • Die farbliche Markierung der Vergleiche (bei Slow- und Trippelsort) ist nunmehr zur Laufzeit mit Druck auf „V“ (Vergleiche, Sortierkino) bzw. „C“ (comparisons, sorting cinema) umschaltbar.

  • Weitere Rekursionsbeseitigungen und Fehlerbehebungen.

24. April 2016: Die Anzahl der voneinander verschiedenen Elemente bei einigen Startmengen ist nunmehr einstellbar. Daraufhin wurden einige wenige Startmengen entfernt, weil diese sich nunmehr „konstruieren“ lassen.

19. April 2016: Heapsort zur Liste der Vorsortieralgorithmen hinzugefügt.

12. April 2016: 13 Mischungsalgorithmen implementiert.

30. März 2016: Der Wachstumsfaktor bei Proportion Extend und Symmetry Partition Sort kann jetzt als Gleitkomma-/Realzahl und auch kleiner als 2 eingegeben werden.

21. März 2016: Stackemulatorklasse leicht überarbeitet und fehlerbereinigt

19. März 2016:

17. März 2016:

  • alle noch verbliebenen Rekursionen „entrekursiviert“, d.h., in Iterationen verwandelt, das war Voraussetzung für den nächsten Punkt,

  • maximale Stackgröße auf das zulässige Minimum reduziert,

  • das Programm müßte nunmehr mit allen Monitoren (auch mit 5K-Displays) im Vollbildmodus arbeiten,

  • kleine Überarbeitungen und Fehlerbereinigungen

6. März 2016:

  • Elementeswapping bei gleichen Indizes ist sinnlos und wird nun abgelehnt,

  • alternatives Heapsort, hier im zweiten Beitrage gefunden (der Dank geht an Daniel) und implementiert,

  • die 3 Quicksorts heißen jetzt an- und absteigend sowie stackoptimiert, keine Unterscheidung mehr zwischen rekursivem und iterativem Quicksort (wegen des nächsten Punktes),

  • die meisten rekursiven Prozeduren in (pseudo-)iterative umstrukturiert, dabei eine eigene heapbasierte dynamische Stack-Objekt-Klasse verwendet, und die maximale Stackgröße moderat verringert (besser für die Multihtreadingsortieralgorithmen),

  • dem Shufflemerge der drei türkischen Informatiker Elif Acar, Mehmet Dalkiliiç und Görkem Tokatli (ein Eintrag unter Mergesort und in den Danksagungen) stehen nun alle Blockswappingalgorithmen zur Verfügung (wurde vorher nur durch jeweils 3 Rotationen realisiert) und

  • Quelltext(e) überarbeitet, einige kleine Fehlerkorrekturen

29. Februar 2016:

  • Mergealgorithmus nach Frank K. Hwang und Shen Lin, in und ex situ, für Merge- und Naturalmergesort (damit insgesamt vier neue Sortieralgorithmen) implementiert, er stammt aus dem unten genannten Benchmarkingtool.

  • Der Mergealgorithmus von 2007 ist jetzt rekursiv und damit „rein“.

  • Der Mergealgorithmus von 2006 instabil wurde gemäß seines stabilen Pendants etwas optimiert.

  • Der Mergealgorithmus von 2006 stabil überarbeitet.

  • einige Fehlerkorrekturen

21. Februar 2016:

  • 7 Mergingalgorithmen hinzugefügt (einer von Krysztof Dudzinki und Andrzej Dydek, einer von Jingchao Chen und fünf von Pok-Son Kim und Arne Kutzner, s. Danksagungen). Da alle mit verschiedengroßen Teilmengen umgehen können, wurde jeder einmal sowohl für Merge- als auch für Naturalmergesort implementiert, sodaß insgesamt vierzehn Sortieralgorithmen hinzugekommen sind.

  • Einen weiteren Blöcke(ver)tausch-/Arrayswap-/-rotationsalgorithmuns (Hybridrotation) hinzugefügt. Sowohl dieser als auch die zuvor genannten sieben Mergingalgorithmen entstammen Prof. Dr. Arne Kutzners Benchmarkingtool, s. Danksagungen.

  • Die Ausgabemessagebox erscheint jetzt ungefähr an der Stelle, an der zuvor das Bedienformular stand (vorher immer in der Bildschirmmitte).

  • kleine Optimierungen

26. Januar 2016:

  • Auch bei den drei letzten Vorsortieralgorithmen (ehemals als „Halbsortierung“ bezeichnet) ist jetzt das Maß der Vorsortierung veränderbar

  • kleine Fehlerkorrekturen

24. Januar 2016:

  • Für die Auswahl der zu sortierenden Startmengen wurden weitere Startmengen auf der Basis verschiedener Verteilungen (Dreiecks-, Trapez-, Normal- und asymmetrische Verteilung, teilweise auch inversen Verteilungen) hinzugefügt.

  • Die halbsortierten Mengen wurden aus der Auswahl der zu sortierenden Startmengen entfernt. Die Halbsortierung steht jetzt - gemeinsam mit der Vorsortierung - allen Startmengen zur Verfügung.

  • Startmengen werden nun wegen ihrer Vielzahl statt in einer Radiogroup nunmehr in einer Combobox angeboten. Damit konnte das Bedienformular verkleinert und sein Layout überarbeitet werden.

19. Januar 2016:

  • Fehler in Proportion Extend und Symmetry Partition Sort behoben, der bei Eingabe des Parameters 256 und 257 zum Programmabsturz führte. Den Ausschlag gab ein Hinweis von Herrn Prof. Jinchao Chen, dem Autor beider Algorithmen.

  • Geschwindigkeitsangaben in der Combobox geringfügig überarbeitet

18. Januar 2016:

  • Implementation einer Farbmarkierung während des Vergleichens. Da diese nur bei Slow- und Trippelsort gut sichtbar ist, wurde diese auch nur dafür freigeschaltet.

  • einige marginale Detailkorrekturen und -verbesserungen

17. Januar 2016: Fehler in Quicksort beseitigt (entstand während der Implementation des Vergleichszählers)

16. Januar 2016:

  • Zähler für Vergleiche und Vertauschungen hinzugefügt, kann am Sortierende angezeigt werden,

  • als neunter Blockswapping-/Arrayrotationsalgorithmus wurde eine stabile Sortierung (Splitsort) hinzugefügt (auch wenn das Swappingproblem eigentlich kein Sortierproblem ist, s. hier), damit wird Symmetry Partition Sort beim zweiten Aufruf mit diesem Algorithmus sogar stabil, und

  • kleine Fehlerbehebungen

10. Januar 2016:

  • Minsertion- und rlx-Sort hinzugefügt,

  • die acht Blockswapping-/Arrayrotationsalgorithmen aus der Radiogroup „Blocktauschalgorithmus“ stehen neben Symmetry Parition Sort nun auch den beiden modifizierten Simpleswapsorts und dem HP-/SGI-Mergesort zur Verfügung und

  • kleine Fehlerbehebungen

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 Berufsschulen, -kollegs und -akademien sowie 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. Weiterhin kann mit ihnen gezeigt werden, daß ein (scheinbar) banaler Vorgang, fast alltäglicher Vorgang, sobald man ihn systematisieren, algorithmieren, formalisieren (also einem Computer „beibringen“) möchte (ganz zu schweigen von der Verbesserung seiner Eigenschaften), außerordentlich tückisch und anspruchsvoll wird.

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:

  • Punkt- statt Linien-/Balkendarstellung, denn einzelne Punkte sind, zumal bei deren Beweglichkeit, bei heutigen Monitorauflösungen kaum schnell zu erfassen. Außerdem wäre die Darstellung mit Punkten noch um einiges schneller.

  • Bei geringen Größen des Sortierformulares die Zuordnung „1 Linie / Sortierelement“ zu verändern, die Linien also bei wenigen zu sortierenden Elementen zu verbreitern.

  • Eine Option, die horizontale Balken anbietet und vertikal sortiert. Das wäre nur eine optische Spielerei, von denen das Programm nun schon einige hat, ohne informationellen Mehrwert, auch müßte auf dem ohnehin schon dichtgedrängten Bedienformular Platz für eine weiteres Bedienelement geschaffen oder ersteres vergrößert werden. Unser Blickfeld ist horizonatal ausgeprägter und evtl. auch für horizontale Bewegungen empfänglicher, so sind auch die Desktop-Bildschirme proportioniert, und deshalb läuft auch diese Animation horizontal (allerdings werden Tablets und Smartphones eher im Hochformat benutzt).

  • Eine allgemeine Informationszusammentragung („Tutorial“) über Sortieralgorithmen. Dazu fehlen mir mangels einschlägigem Studium die Hintergrundkenntnisse und auch das Interesse. Zu empfehlen sind neben einer bekannten Internetenzyklopädie vor allem diese anspruchsvollen Theoriequellen.

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-, Red-Black-, Skip-, Splay- und Treesort.

zurück zum Programm
zurück zum Seitenanfang

Was noch zu tun wäre

  • Implementation weiterer Sortieralgorithmen und vor allem Mergesorts mit weiteren Mergingalgorithmen. Mir liegen noch einige PDF-Dateien zu Mergingalgorithmen dazu vor, jedoch ist deren Durcharbeitung sehr mühsam und deren Implementation ohne Quelltexte ziemlich ungewiß.

  • was Sie anregen; bevorzugt wären weitere Sortieralgorithmen, die einen optischen Neuheitswert haben, aber auch weitere Startmengen.

zurück zum Programm
zurück zum Seitenanfang

Lizenz

Das Programm ist mitsamt seinen Quelltexten 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

Wie alles begann

Als Freund der Ordnung und der Übersicht(lichkeit) sowie natürlich auch, sie zu schaffen, erweckten Sortieralgorithmen, aber auch andere Algorithmen schon recht früh meine Aufmerksamkeit, ja Faszination. Anfang der 90er Jahre fiel mir wegen meines Interesses für Algorithmen Robert Sedgewicks gleichnamiges Buch in die Hände, und das Eintauchen in die Welt der (nicht nur Sortier-)Algorithmen begann. Bereits damals schrieb ich 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 jenem Buche 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 selbstentwickelte „Exoten“ (nicht abwertend gemeint, ganz im Gegensatz). Es enstand der Wunsch, all' das zu verbessern und zudem „echtes Kinogefühl“ aufkommen zu lassen. Ich hoffe, daß meinem Programm die Akribie bei seiner Entwicklung anzumerken ist.

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 und wächst immer noch.

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

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 (sofern es sie überhaupt gäbe). Nicht aufgeführt wurden die Autoren der Algorithmen, die schon seit langem (teilweise Jahrzehnten) existieren und mithin sozusagen Allgemeingut (geworden) sind. Im einzelnen danke ich:

zurück zum Seitenanfang

Kontakt

Sehr geehrter Interessent, Ihre Fragen, Anregungen und Kritik sind jederzeit willkommen. Bitte senden Sie mir dazu eine E-Mail - vielen Dank!

Autor des Programmes und dieser Internetseite: Ansgar Matthes (Dr.-Ing.), Rostock

zurück zum Seitenanfang