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 enthält über 300 Sortierverfahren mit den unterschiedlichsten Merkmalen (allgemein/speziell, 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 „sortiert“ (in der zweitobersten Combobox „Struktur der Startmenge“) und „Rotation“ mit einem Wert kleiner bzw. größer 0 gebildet wird (dabei „n verschiedene Elemente“ groß lassen), sortiert von Swirlsort vorwärts bzw. Swirlsort rückwärts. Probieren Sie es einfach aus, so etwas sahen Sie zuvor sicher noch nie!

Als besondere Zugabe sind in diesem Programm auch 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 (läuft darauf aber auch)


Sortieren


zurück zum Seitenanfang

Was heißt Sortieren?

Sortieren heißt der Wortbedeutung nach (An-)Ordnen, Gruppieren oder Separieren von Objekten anhand ihrer Sorte. Sortieren kann man z.B. ein Gemenge aus Schrauben, Muttern, Nägeln, Nieten, Splinten usw. 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“ (nach der Größe oder einem anderen Ordnungskriterium, z.B. alphabetisch). So ist z.B. die Menge 3, 1, 2, 1, 3, 1 umgeordnet zu z.B. 2, 3, 3, 1, 1, 1 bereits eigentlich und genaugenommen sortiert (Gruppierung nach der natürlichen Zahl, also Sorte), jedoch erst im Zustande 1, 1, 1, 2, 3, 3 auch der Größe nach (aufsteigend) geordnet (und mithin im landläufigen Sinne sortiert). Werden „auf natürliche Weise entstandene“ reelle Zahlen wie z.B. sehr genaue Meßwerte erhoben und später sortiert, dürfte es eigentlich überhaupt keine gleichen Werte bzw. Sortierelemente(schlüssel) geben, und das Sortieren derselben ist dann überhaupt kein Gruppieren, sondern ein reines Ordnen nach der Größe.

Das Wort „Sortieren“ ist demnach semantisch (=begrifflich) leicht und zudem fehlerhaft überladen. Die Bezeichnung „Sortieren“ für bloßes „Ordnen“ ist also 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.:

Alle Sortierprogramme und Sortieralgorithmen gruppieren nicht nur nach der Sorte, sondern ordnen nach meiner Kenntnis auch nach der Größe, und zwar jede, auch noch so ungeordnete Ausgangsmenge (sonst wären sie nicht allgemeingültig). Wichtig, für das Sortieren i.S.d. Größenordnens ja geradezu evident ist auch das Vorliegen einer sog. totalen Ordnung, d.h., es muß für alle beliebigen Elemente a, b und c der Menge immer gelten: Wenn a<b und b<c, dann folgt daraus immer a<c. Das ist nicht so selbstverständlich, wie es auf den ersten Blicke erscheint, denn z.B. bei Schere-Stein-Papier(-Brunnen), auch Schnick-Schnack-Schnuck genannt, gilt das nicht, ebenso bei sportlichen Wettbewerben.

Auch wenn das Gruppieren nach Sorten und das Ordnen nach der Größe eigentlich zwei verschiedene Dinge sind, so gibt es doch eine Schnittmenge beider. Werden in einer Menge mit möglichst verschiedenen Sorten Elemente gleicher Sorte jeweils mit einem gemeinsam mit dem gleichen Sortierschlüssel (s.u.) versehen (zweckmäßigerweise natürliche bzw. Ganzzahlen), was bereits eine gewisse Sortierung darstellt, und wird diese Menge dann anhand dieser Sortierschlüssel der Größe nach geordnet, so liegen die Fraktionen/Teilmengen mit gleichem Sortierschlüssel auch räumlich konzentriert, demnach sortiert vor. Während z.B. beliebige dichtliegende Zahlen (rationale, algebraische, reelle) wirklich nur der Größe nach geordnet werden können, weil nur unwahrscheinlich zwei gleiche vorhanden sind, so bilden bei integren Zahlen (natürliche, ganze) alle gleichgroßen Zahlen auch impizit eine Sorte.

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 ein rein kulturelles Phänomen reduzieren zu können. 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). Diese gewünschte Reihenfolge ist eine (1) Permutation der Ausgangsmenge (bei stabilen Sortierverfahren) oder ggf. bei einer Menge von Permutationen (bei instabilen Sortierverfahren) gegeben.

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 ihrem Geburtstag. 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 am häufigsten auftretdenden 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.

Ein klein wenig Mathematik (Kombinatorik): Faßt man die i.d.R. mehr oder weniger ungeordnete Ausgangsmenge A als Permutation (Änderung der Anordnung i.S. einer Reihenfolge) π der im Idealfalle geordneten bzw. sortierten, tatsächlich aber oft noch nicht jemals so vorliegenden (bislang also fiktiven) Menge M auf (der ungeordnete Zustand ist wohl meistens der anfangs vorliegende; A und M werden hier - mengentheoretisch unüblich - trotz gleicher Elemente als ungleich angesehen, weil in diesem Kontext auch noch die Elementeanordnung relevant ist):

A = M ∘ π

, so besteht das Sortieren darin, diejenige (zu π inverse) Permutation π-1 für A zu suchen bzw. zu finden und vor allem auf A anzuwenden (A ist eben zu ordnen bzw. zu sortieren), sodaß gilt:

M = A ∘ π-1

wir demnach als Folge dieser Permutation π-1 das gewünschte M, das eben sortiert bzw. geordnet ist, erhalten.

Während π die Unordnung charakterisiert und sozusagen von ganz allein im alltäglichen Leben entsteht (Entropieerhöhung) und jede beliebige Permutation darstellt, stellt π-1 das Sortieren dar, muß paßgenau zu π sein und ist mithin mit zeitlichem und energetischem Aufwand verbunden (Entropieverminderung).

*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. Weiterhin ist es möglich, daß das zweite Prinzip im ersteren enthalten ist: So bauen die iterativen Mergesorts zunächst über die gesamte Sortiermenge zunächst kleine, komplett sortierte Bereiche auf, die allmählich wachsen und anzahlig geringer werden, bis schließlich die gesamte Menge sortiert ist.

Es gibt bei beiden Prinzipien auch weitere Unterschiede. So ist es beim ersten möglich, daß mehrere sortierte Teilmengen gebildet werden, die immer mehr Elemente enthalten und deshalb anteilig schrumpfen (z.B. Merge - und Shearsort). Oder das Ordnungsniveau wird ohne diese Eigenschaft insgesamt erhöht (Shellsort). Besonders rätselhaft ist letzteres bei Radixsort LSD, wo in den ersten Durchgängen überhaupt keine Steigerung des Ordnugnsniveaus wahrnehmbar ist, diese natürlich aber dennoch stattfindet.

Beim zweiten Prinzip kann die sortierte Teilmenge sich unverändert in der sortierten Endmenge wiederfinden (z.B. Bubble,- Heap- und Selectionsort) oder noch weitere Elemente eingefügt bekommen (z.B. Insertion- und Mergesort).

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. Auch erinnert mich dieses Bild an diese meine Klassifikation.

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


Allgemeine versus spezielle Sortieralgorithmen

Bei den Sortieralgorithmen gibt es zwei grundlegend unterschiedliche Typen, die allgemeinen und die spzeiellen.

Die meisten Sortieralgorithmen sind allgemeine oder vergleichsbasierte Algorithmen, bei denen die Bewegungen der Sortierelemente zum Zwecke des Sortierens von vorherigen Größenvergleichen ihrer Sortierschlüssel abhängen. Das ist immer dann vonnöten, wenn die Sortierschlüssel eine Unzahl an Werten annehmen können (z.B. Wörter). Das ist auch im realen Leben nötig, da z.B. die Körpergröße eine kontinuierliche Größe (reelle Zahl) ist. Es können sozusagen unendlich viele verschiedene Körpergrößen vorkommen. Die allermeisten Sortieralgorithmen dieses Programmes sind allgemeine.

Ist der Wertevorrat der Sortierschlüssel jedoch eng begrenzt - z.B. nur die natürlichen Zahlen bis 100 oder 1000 oder ähnlich - so können auch spezielle Sortieralgorithmen verwandt werden, die darauf beruhen, jeden - vorab bekannten! - Sortierschlüssel zu erfassen und zu zählen oder die gesamten Sortierelemente schlüsselweise zu sammeln. Vergleiche zwischen den Sortierelementen bzw. konkret deren -schlüsseln sind nicht nur unnötig, sondern kommen bei dieser Erfassung auch gar nicht vor. Zum Ende des Sortierens werden die anzahlig bzw. summarisch erfaßten Sortierelemente ausgebeben. Diese Sortieralgorithmen sind spezielle.

Salopp formuliert, kann man mit allgemeinen Sortieralgorithmen reelle bzw. Fließkommazahlen, mit speziellen lediglich integre bzw. ganze Zahlen sortieren.

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, sind adaptiv, weil (vor-)sortierte gegenüber völlig chaotischen Mengen weniger Vertauschungen erfordern. Aber auch die Anzahl der Vergleiche allein hängt bei manchen Sortieralgorithmen schon von der Elementeordnung ab (z.B. Insertionsort), bei anderen nicht (z.B. Bubblesort). Es gibt demnach genaugenommen eine Adaptivität hinsichtlich der Elementvergleiche und eine hinsichtlich der Elementebewegungen (Verschiebungen und / oder Vertauschungen).

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).

Je geringer die Adaptivität eines Sortieralgorithmus' ist, desto wahrscheinlicher ist es, daß er sich als Sortiernetz(werk) realisieren läßt.

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. Bei instabilen Sortierverfahren sind hingegen beliebige Permutationen innerhalb der Teilmengen mit jeweils gleichem Sortierschhlüssel möglich.

Ein Beispiel: Aus der unsortierten Menge 2A 1A 2B 3A 1B 3B 2C wird nach instabiler Sortierung z.B. 1A 1B 2B 2C 2A 3A 3B (die Reihenfolge der Zweien ist gegenüber der Ausgangsreihenfolge verändert, deren Anordnung also permutiert, das kann mit jeder Teilmenge mit jeweils gleichen Elemente(schlüssel)n geschehen), bei stabiler Sortierung hingegen nur 1A 1B 2A 2B 2C 3A 3B.

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. Außerdem kann die Stabilität den Sortieralgorithmus etwas oder erheblich verlangsamen.

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, Elementebewegungen (Vertauschungen, Verschiebungen) über größere „Entfernungen“ in der noch unsortierten Teilmenge jedoch nicht, letztere also demnach instabil sind. Bei Bewegungen innerhalb der schon sortierten Elementemenge hängt es vom Algorithmus ab. Im Gegenzuge können Bewegungen ü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“ (oder „semistabil“)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: Einen Sortier-, Partitionierungs- oder Verschmelzungsalgorithmus stabil zu halten oder zu „stabilisieren“ ist mindestens genauso anspruchsvoll, wie ihn zu beschleunigen, zumindest dann, wenn die Laufzeit bestenfalls nur unwesentlich darunter leiden soll. 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-, Binary-Search-Tree-, Fibonacci-, Merge-, Patience-, Red-Black-, Skip-, Splay-, Tree- 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.

Noch kompliziertere Datenstrukturen (z.B. Bäume, Skiplisten) sind möglich, doch tendenziell verkomplizieren diese naturgemäß auch die Sortieralgorithmen, die auf sie angewandt werden.

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, wurden schon seit den Sortierfrühzeiten Algorithmen, die Kompositionen / Konglomerate bereits bestehender Ideen sind, angestrebt. Selbstredend sind solche Algorithmen aufwendiger als ihre reinen (aber nicht notwendigerweise simplen) Pendants zu implementieren.

Es kann z.B. bei verschiedengroßen Teilarrays zwischen verschiedenen Sortieralgorithmen umgeschaltet werden („Umschalthybride“). Grund dafür 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 dieser „Umschalthybriden“ könnte Timsort sein, das zwar generell ein Naturalmergesort ist, bei kleinen Teilarrays jedoch Insertionsort verwendet.

Eine andere Möglichkeit besteht darin, intern einen nicht sehr effizienten (Kern-)Sortieralgorithmus von einem anderen (nicht zwangsläufig auch Sortier-)Algorithums zu „umhüllen“ und so in Richtung wesentlicher Beschleunigung zu steuern. So beinhaltet Shell- intern Insertion- oder Bubblesort, Combsort beinhaltet Ripple-, Bubblesort oder Oetsort und die Shearsorts Oetsort. Umhüllende Hybridalgorithmen der besonderen Art sind die Radixsorts. Sie sind speziell, d.h., sie funktionieren nur mit ganzen Zahlen als Sortierelemente(schlüssel). Radixsort LSD (least significant digit) kann grundsätzlich sogar mit jedem stabilen internen Sortieralgorithmus kombiniert werden.

Eine dritte Hybridmöglichkeit besteht im Nacheinanderanwenden verschiedener Algorithmen. Da wäre z.B. 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. Patiencesort erstellt erst aufsteigende Teilarays „Runs“, was die Ordnung erhöht, um diese dann mit Naturalmergesort endgültig zu sortieren.

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 (was ich ebenfalls nirgendwo erwähnt fand): Ihre „sichtbare Oberkante“ ist der (an der Diagonale links unten nach rechts oben gespiegelte) Graph der (kumulierten / kumulativen) Verteilungsfunktion der Wahrscheinlichkeitsverteilung ihrer Elemente. Das soll erläutert werden. Zunächst der einfachste Fall, eine stetig gleichverteilte Startmenge, bei der alle Elemente(größen) gleich wahrscheinlich sind:

Nach Sortierung derselben ergibt sich eine sortierte Menge mit nahezu linearer Oberkante:

Eine Spiegelung an der eingangs genannten Diagonale ändert diese Linie nicht, sodaß diese sortierte Menge bereits den Graphen ihrer Verteilungsfunktion repräsentiert.

Der nächstkomplizierte Fall: Addiert man die jeweiligen Zufallswerte zweier Gleichverteilungen (man „faltet“ diese Verteilungen), ergibt sich eine sog. Dreiecksverteilung:

Hier ist bereits deutlich zu sehen, daß sich die Werte stärker auf halber Höhe als bei der Gleichverteilung drängen. Dreiecksverteilt wird diese Verteilung deshalb genannt, weil der Graph der Wahrscheinlichkeitsdichtefunktion ein (symmetrisches bzw. gleichschenkliges) Dreieck ist. Man kann sich das so vorstellen, daß die mittelgroßen Werte die am häufigsten bzw. wahrscheinlichsten auftretenden sind, und, je mehr die Werte nach unten und oben von dem am wahrscheinlichsten / häufigsten auftretenden Wert abweichen, immer unwahrscheinlicher werden. Der Abfall der Wahrscheinlichkeiten ist beidseitig linear, sodaß der Graph der gesamten Dichtefunktion dreiecksförmig verläuft. Sortiert man nun auch diese Startmenge:

ist die Oberkante der sortierten Menge nicht mehr linear. Spiegelt man an der genannten Diagonale (oder wendet äquivalente Operationen/Transformationen an):

liegt nunmehr der Graph der Verteilungsfunktion einer dreiecksverteilten Startmenge bzw. Zufallsgröße/-funktion vor. Da die kleinen und großen Elemente die seltensten sind, ist dort der Anstieg des Graphen am geringsten (flachesten), währendhingegen bei den am häufigsten auftretenden, den mittelgroßen Elementen, der Anstieg am stärksten (steilsten) ist.

zurück zum Sortieren
zurück zum Seitenanfang


Der perfekte Sortieralgorithmus

Sortieralgorithmen sollen vor allem schnell und meistens auch stabil sein sowie möglichst wenig (zusätzlichen) Speicher benötigen, nicht zuletzt nicht gar zu komplex und damit realistisch implementierbar sein. Alle diese Ziele gleichermaßen zu erreichen bzw. zu optimieren hat sich als Zielkonflikt herausgestellt.

Bei den schnellen Sortieralgorithmen gibt es einige, die aus der Menge der unsortierten Daten eine komplett neue aufbauen, und das meistens sogar stabil. Sie duplizieren sozusagen die Sortiermenge mit veränderter, geordneter, sortierter, meistens sogar stabiler Struktur, die am Ende zurückgeschrieben, d.h., die unsortierte Startmenge damit überschrieben wird. Selbstredend benötigen diese Algorithmen viel zusätzlichen Speicher. Duchweg reichlich kompliziert sind sie obendrein. Vertreter in diesem Programm sind AVL-, B-, Binary-Search-Tree-, Fibonacci- (instabil), Patience-, Red-Black-, Skip-, Splay-, Tree- (instabil) und Trisort.

Weitere schnelle Sortieralgorithmen sind Heap- (inkl. seiner starken Abwandlung Smooth-), Merge- (inkl. Naturalmerge-) und Quicksort.

Mergesort ist neben schnell auch stabil, arbeitet aber rekursiv und benötigt dafür zusätzlichen (Stack-)Speicher. Diesen Nachteil haben das einfache iterative und das Naturalmergesort nicht. Jedoch läuft das gewöhnliche Verschmelzen aller Mergesorts parallel zu der zu sortierenden Menge im Speicher ab (Datenduplizierung) und benötigt mithin erheblichen zusätzlichen Speicher. Dieser Nachteil wurde mit den In-Situ-Verschmelzungsalgorithmen (etliche in diesem Programm enthalten) mehr oder weniger beseitigt, doch wirken diese sich negativ auf die Geschwindigkeit aus, von der Komplexität dieser Sortier- und vor allem Verschmelzungsalgorithmen ganz zu schweigen. Auch die Stabilität geht bei manchen verloren.

Quicksort ist zwar für gewöhnlich, d.h., auf unsortierte Mengen angewandt, sehr schnell, dafür aber instabil und ebenfalls rekursiv. Doch es gab erfolgreiche Versuche, beide Nachteile aufzuheben. Die aufgestöberten bzw. gefundenen, mehr oder weniger komplizierten Vertreter sind in diesem Programm implementiert. Leider wurden beide mühsam erkämpften Vorteile bisher nicht in einem Algorithmus kombiniert bzw. vereint.

Bliebe das Heapsort, das sowohl schnell als auch speichersparend ist. Davon ist im Programm eine stabile Version enthalten, bei der jedoch die Geschwindigkeit einbricht. Gelänge es, Stabilität zu erreichen und mit Geschwindigkeit zu vereinen, wäre auch hier ein (evtl. nahezu) perfekter Sortieralgorithmus gefunden, sofern er nicht überbordernd kompliziert ist. Seine Abwandlung Smoothsort hingegen ist bereits wieder sehr kompliziert und damit nur schwierig zu implementieren sowie instabil und wohl auch nicht stabilisierbar.

Es wurde(n) demnach faktisch nur die Hälfte, bestenfalls zwei Drittel (bei nichtgeforderter Stabilität) aller Anforderungen in den besten Sortieralgorithmen vereint. Die jahrzehntelange, bisher vergebliche Suche macht es wahrscheinlich, daß es, wenn überhaupt, keine einfache Lösung gibt, sodaß, wenn eine gefunden wird, diese zwar schnell, stabil und speichersparend, nicht jedoch trivial sein wird. Es gibt also für die (theoretische) Informatik auch auf dem Gebiet der Sortieralgorithmen noch sehr viel zu tun.

zurück zum Sortieren
zurück zum Seitenanfang


Der schlimmste Sortieralgorithmus

Die meisten Sortieralgorithmen beruhen ausschließlich oder vorwiegend auf dem Befehlspaar „Vergleichen und und optionales Tauschen (wenn die Reihenfolge der verglichenen Elemente der gewünschten Ordnung zuwiderläuft) jeweils zweier Elemente“. Doch es gibt auch Sortieralgorithmen, die diese Befehlsreihenfolge umkehren und mithin der Erreichung des Sortierzieles maximal entgegenwirken. Dabei werden erst zwei beliebige Elemente vertauscht und erst dann die gesamte Menge auf Ordnung bzw. Sortiertheit geprüft (oder, wenn man zuerst prüft, dann kann man so wenigstens schon sortierte Mengen von überflüssiger „Sortierung“ befreien). Die Wahl der zu tauschenden Elemente erfolgt entweder zufällig (Bozosort) oder durch systematische Permutationsenumeration (Bogosort). Diese Sortieralgorithmen, die auch schon erreichte Teilordnungen immer wieder sehr wahrscheinlich zerstören, sind die ineffizientesten überhaupt, aber auch sie können die Sortierung nach Zeitaltern, die jegliche astronomische / kosmologische Zeiträume schnell und weit überschreiten, nicht für alle Ewigkeit verhindern. Während beim Bogosort nach spätestens n! Vertauschungen und Prüfen der Menge auf Sortiertheit Schluß sein muß (n: Anzahl der Sortierelemente), weil alle Permutationen der Sortierelemente geprüft wurden, kann es beim Bozosort noch wesentlich länger dauern.

zurück zum Sortieren
zurück zum Seitenanfang


Sortiernetz(werk)e

Die in diesem Programm implementierten bzw. vorgestellten Sortieralgorithmen sind flexibel, weil sie für eine prinzipiell beliebige Anzahl an Sortierelementen geeignet sind. Ist deren Anzahl hingegen bekannt oder überschreitet zumindest eine geplante Anzahl nicht (die fehlenden Sortierelemente können dann einfach durch Null- oder Maximalelemente, sog. „Dummies“, vertreten werden), können auch sog. Sortiernetzwerke oder Sortiernetze verwandt werden. Das sind funktional eingeschränkte Sortieralgorithmen, die nur auf Vergleichen und Vertauschungen (in dieser Reihenfolge kombiniert, ggf. auch zusätzlich nur Vertauschungen ohne vorherige Vergleiche, also bedingungslose Vergleiche) beruhen. Verschiebungen und Wertezwischenspeicherungen (z.B., um ein Minimum oder Maximum zu suchen) kommen in ihnen nicht vor. Diese kann man auch als Hardwarelösung mithilfe „fester Verdrahtungen“ lösen. Jedoch sind sie für Parallelisierungen hervorragend geeignet. Selbstredend ist ein solches Sortiernetzwerk wie jeder Sortieralgorithmus erst dann vollständig, wenn es jede beliebige Eingabemenge zuverlässig sortiert. Da die Vergleiche und Vertauschungen mithin auch ihre Anzahl, Position und damit auch Ausführungsreihenfolge unabhängig von der Struktur der Startmenge, also auch bei erhöhten Ordnungsniveaus, von vornherein feststehen (determiniert sind), sind solche Netz(werk)e auch nicht adaptiv.

Bestimmte Sortieralgorithmen lassen sich als Sortiernetze abbilden und umgekehrt bestimmte Sortiernetzwerke (die mit einer elementeanzahlsverallgemeinerbaren Vorgehensweise) als elementeanzahlsflexible Sortieralgorithmen verallgemeinern. Das bedeutet, daß sich solche Sortiernetze für beliebige Elementeanzahlen verallgemeinern lassen und demnach einen anzahlsflexiblen Sortieralgorithmus realisieren. Manche Sortieralgorithmen lassen sich 1:1 als Sortiernetze abbilden bzw. umgekehrt (Bitonic, Bose-Nelson-, Circle-, Odd-Even- und Pairwise-Network-Mergesort, AKS,- Bubble-, Odd-Even-Transposition-, Quick- (mit (meistens) gleichgroßen Partitionen bzw. perfekter Halbierung)-, Shell-, Simple- und Zig-Zag-Sort. Einige dieser Sortieralgorithmen sind nur mit Effizienzverlust als Sortiernetze realisierbar, weil alle denkbar möglichen Vertauschungen unabhängig vom tatsächlich schon erreichten Ordnungsniveau vor dem Sortieren und während des Sortierens berücksichtigt werden müssen (z.B. Insertionsort, allerdings ist auch da die fast schon unsinnige, nichtoptimierte Variante der ersten Gruppe angehörend). Die Sortieralgorithmen der letzten Gruppe lassen sich überhaupt nicht als Sortiernetze abbilden, weil der Sortierverlauf von der Elementeanordnung abhängt (z.B. Heap- und Quicksort) oder deren Vergleiche nichtdeterminiert sind (Spin-The-Bottle- und Annealing-Sort), wobei diese Merkmale genaugenommen gemeinsam auftreten. Bemerkenswert ist, daß viele dieser Netz(werk)e Zweierpotenzen als Elementeanzahlen voraussetzen, was damit zu tun hat, daß die Sortieraufgabe mit ihnen nicht flexibel aufgespaltet werden kann.

Alle Vergleichsoperationen und nachfolgenden optionalen Vertauschungen heißen hier Vergleicher. Sortiernetzwerke, deren Vergleicher sich nur auf benachbarte Elemente beziehen, heißen primitiv (steht unter Vergleichernetzen) und sind stabil. Alle jeweils gleichzeitig ausführbaren Vergleicher bilden je eine Vergleicherstufe, das Sortiernetz läßt sich also zu deutlich weniger Vergleicherstufen im Vergleich zur Anzahl der Vergleicher verdichten. Bei maximaler Parallelisierung hängt die Sortiergeschwindigkeit demnach nur von der Anzahl der Vergleicherstufen ab. Die Anzahl aller Vergleicher wird als Größe, die maximale Anzahl Vergleicher, die ein Element während des Sortierens durchlaufen kann, als Tiefe des Sortiernetzes bezeichnet. Da diese Vergleicher sequentiell durchlaufen werden (müssen), muß die Tiefe des Sortiernetzwerkes der Anzahl der Vergleicherstufen entsprechen. Weil zudem die Anzahl der Vergleicher pro Vergleicherstufe maximal ½ n (n: Anzahl der Elemente) beträgt bzw. betragen kann, kann die Anzahl Vergleicherstufen nicht beliebig gegenüber der Anzahl der Vergleicher reduziert werden, vielmehr stellt v / (½ n) (v: Anzahl der Vergleicher) hier eine untere Schranke dar. Die Parallelisierbarkeit und mithin die Parallelität / Simultaneität lassen sich demnach nicht beliebig steigern.

Man kann beliebige Sortiernetze konstruieren, indem man einfach ein noch leeres, d.h. vergleicherloses Sortiernetz mit allen möglichen (!) Startanordnungen bestückt / beschickt und bei allen Elementeanordnungen am Ausgang, die der sortierten Ordnung zuwiderlaufen (sog. Inversionen), einen Vergleicher an das jeweilige Ende des Sortiernetzes anfügt. Es reicht dabei allerdings aus, nur zwei voneinander verschiedene Schlüsselgrößen zu verwenden (z.B. 0 und 1, deshalb das sog. 0-1-Prinzip, was die Anzahl der möglichen Startmengen von n! auf „nur“ 2n reduziert. Das ist zum einen bei größeren Anzahlen aber immer noch äußerst aufwendig, und eine Systematik im Sinne eines elementanzahlsflexiblen Sortieralgorithmus' wird dabei wahrscheinlich auch nicht entstehen, das Sortiernetzwerk also nur für (maximal) diese Elementeanzahl geeignet sein. Mir ist nicht bekannt, ob dieses 0-1-Prinzip auch auf Sortieralgorithmen, die sich nicht als Sortiernetzwerke realisieren oder abbilden lassen, verallgemeinert bzw. erweitert werden kann.

Die bevorzugte Darstellung solcher Netz(werk)e sind sog. Knuth-Diagramme. Die folgenden Bilder zeigen verschiedene Sortiernetzwerke für (bis zu) 8 Elemente. Die Zeit läuft von links nach rechts. Evtl. gibt es Sortiernetze, die auch umgekehrt („zeitinvers“) oder bei anderweitig permutierten Vergleicherstufen funktionieren; bei den Vergleichern innerhalb derselben Stufe ist die Ausführungsreihenfolge ja beliebig. Jede waagerechte Linie speichert ein Sortierelement bzw. fungiert als Platzhalter für ein solches, und die Pfeile verkörpern je einen Vergleicher. Die dicht beieinanderstehenden Pfeile sind nur der Übersichtlichkeit und Eindeutigkeit halber versetzt angeordnet; diese Operationen stellen tatsächlich je eine Vergleicherstufe dar, wovon jeder der folgenden vier Sortiernetze sechs beinhaltet:




Es ist ein ungelöstes Problem der theoretischen Informatik, für jede beliebige Anzahl an Eingängen bzw. Sortierelementen das optimale Sortiernetz(werk) zu finden. Zum einen wäre da die minimale Anzahl der Vergleicher und / oder Vergleicherstufen, zum anderen muß ein solches Sortiernetzwerk auch gefunden bzw. entwickelt werden. Außerdem stellte es sich als ein Zielkonflikt heraus, sowohl die Vergleicher als auch die Vergleicherstufen anzahlig zu minimieren. Ein weiteres Qualitätsmerkmal könnte sein, wie simpel die Anzahl der Elemente reduziert werden kann und ob beim Herauslösen eines einzelnen Elementes wiederum ein solches Netzwerk mit derselben Eigenschaft entsteht. Das folgende Netzwerk mit 7 Elementen kann um jeweils eines (jeweils das untere) reduziert werden und vererbt diese Eigenschaft auch an jeden seiner Nachfolger:







Flexibler in der Darstellung sind Diagramme, in denen auch die Elementekanäle flexibel(er) sind. Das folgende Schema, mit Straßenkreide hinreichend groß auf einen Untergrund gemalt, könnte sogar ein Spiel für Kinder sein („Algorithmus zum Erleben“, analog den getanzten Sortieralgorithmen). Es sortiert dann z.B. (bis zu) 6 Kinder beliebiger Reihenfolge stets, d.h. bei jeder beliebigen Startanordnung, nach dem Geschlecht, der Größe oder einem anderen Sortiermerkmal:

Auch bekannte, rein vergleichsbasierte Sortieralgorithmen lassen sich per Sortiernetzwerke abbilden bzw. realisieren (s.o.) und mithin für beliebige Anzahlen verallgemeinern:


Hieraus läßt sich einiges erkennen:

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:

Die Partitionierung (Menge in Teilmengen aufspalten) und das Verschmelzen (Menge durch Vereinigen von Teilmengen bilden) sind in gewisser Weise gegensätzliche Algorithmen, obwohl beide das Ordnungsniveau heben. Das Simpleswapmerge nach Siegfried Sielaff bedient sich beider Konzepte.

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. Was sich vergleichsweise banal anhört, kann - wie das Sortieren - effizient oder ineffizient geschehen.

Auch Mischungsalgorithmen haben verschiedene Eigenschaften hinsichtlich ihrer Geschwindigkeit und ihres Speicherbedarfes, wobei das optimale Mischen wohl das von Fisher und Yates sein dürfte. 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.

Die in diesem Programm implementierten Mischungsalgorithmen lehnen sich teilweise an das Mischen von Spielkarten an (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

Zu Sortieralgorithmen im allgemeinen und Sortiernetz(werk)en im besonderen 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. 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 oder mit Entertastendruck 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. Die Verarbeitung kann mit Druck auf „P“ (Pause) prozessorschonend pausiert und mit gleichem Drucke auch wieder fortgesetzt werden. Derlei Hinweise finden sich auch in der kontextsensitiven Hilfe, die über die Checkbox links unten zuschaltbar ist. Im Auswahlmodus, also wenn das Bedienformular erscheint, kann das Programm auch mit ESC-Tastendruck beendet werden.

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, Änderungen zuvor siehe hier):

23. April 2023: M-Sort von Ahmad (oder Ahmed) Abdelfattah (oder Abdel Fattah, Quelle siehe Danksagungen) implementiert.

8. März 2023:

  • Sechs Insertionsortvarianten (zwei Blockinsertionsorts, Fastinsertionsort, Inplaceinsertionblocksort, Inplace-RB-Insertionsort und Selectionsertionsort) von Simone Faro, Francesco Pio Marino und Stefano Scafiti (siehe Danksagungen) implementiert.
  • Strandsort nach diesem Quelletext (Pascal) hinzugefügt
  • 28. Januar 2023: Ein weiteres stabiles Quicksort, diesmal von Sundararajan und Chakraborty, sowie K-Sort von Sundararajan, Pal, Chakraborty und Mahanti (siehe Danksagungen) implementiert.

    14. Januar 2023: Bei den Bogosorts mit dem Permutationsenumerationsalgorithmus von Steinhaus, Johnson und Trotter die iterative mit einer rekursiven Variante ersetzt.

    31. Dezember 2022:

    24. November 2022: Sechs Bogosorts mit den auf Vertauschungen beruhenden Permutationsenumarationsalgorithmen je von B. R. Heap, von F. M. Ives (normal und beschleunigt) sowie von Mark B. Wells und J. Boothroyd (normal, modifiziert und beschleunigt) integiert.

    15. Juni 2022: Zwei weitere Mischungsalgorithmen (Reverses / Invertierungen innen und außen) implementiert.

    22. Dezember 2021: n-Quicksort in zwei Varianten mit je unterschiedlichen n-Partitionierungen (unterscheiden sich jeweils nur in einem Vergleich) aufgespaltet.

    18. Dezember 2021: Effizient(er)es Quicksort von Maarten Herman van Emden (Quelle unter Danksagungen) implementiert.

    12. Dezember 2021: Vom (oder beim) n-Quicksort:

    28. November 2021:

    8. Oktober 2021: Popular Sort von Coenraad Bron und Wim H. Hesselink (Quelle unter Danksagungen) implementiert.

    23. September 2021: Nur für die beiden Delphi-Versionen:

    26. Mai 2021: Q-Sort von Jon Louis Bentley (Quelle unter Danksagungen) implementiert.

    30. April 2021: n-Quicksort mit dem Kernalgorithmus n-Partition (Verallgemeinerung der Lomuto-Partitionierung), der ein (Teil-)Array mit einer (fast) beliebigen Anzahl an Pivotelementen partitioniert, als Eigenentwicklung implementiert.

    15. April 2021: Merge- und Naturalmergesort mit Wandermerge (eigenentwickelter, bedingt stabiler In-Situ-Verschmelzungsalgorithmus) implementiert.

    20. Februar 2021: Friendssort nach Sardar Zafar Iqbal, Hina Gull und Abdul Wahab Muzaffar (Quelle unter Danksagungen) sowie beschleunigtes Friendssort implementiert.

    12. Februar 2021: Blockquicksort mit Finish-Partitionierung nach Stefan Edelkamp und Armin Weiß (Quellen unter Danksagungen) sowie ein weiteres iteratives Quicksort implementiert.

    10. Februar 2021:

    4. Februar 2021:

    2. Februar 2021:

    27. Januar 2021:

    19. Januar 2021:

    8. Dezember 2020: Beim Swirlsort eine Vorwärtsvariante implementiert (die bisherige funktioniert rückwärts).

    30. November 2020: Beim Dual-Pivot-Quicksort eine weitere Variante mit „inverser“ Partitionierung implementiert.

    20. November 2020: Healysort, Merge2Sort und Shovesort (letzteres vorwärts und rückwärts) hinzugefügt.

    6. November 2020: Das Fisher-Yates-Mischen gibt es jetzt auch in der Vorwärtsvariante (die bisherige arbeitete rückwärts) und sowohl die Vorwärts- als auch die Rückwärtsvariante nunmehr in zwei Versionen.

    28. Oktober 2020:

    22. Oktober 2020:

    12. Oktober 2020:

    26. September 2020:

    11. Juli 2020: Den Blocktauschalgorithmus aus dem Rotatequicksort der Liste (Radiogroup) der Blockswappingalgorithmen hinzugefügt.

    9. Juli 2020: 3 Sortieralgorithmen implementiert:

    24. Januar 2020: Binary Search Tree Sort auf der Grundlage des Quelltextes von Roman Tereshin alias ramntry (Quelle unter Danksagungen) implementiert.

    19. Januar 2020:

    28. Dezember 2019: 14 weitere Shellsorts mit je verschiedenen Distanzfolgen hinzugefügt.

    17. Dezember 2019:

    11. Dezember 2019: (Iteratives) In-Situ-Radixsort (LSD, least significant digit) von w0rthy (Quelle unter Danksagungen) implementiert.

    8. Dezember 2019: Einige Startmengenstrukturen können jetzt mit unterschiedlicher Qualität erstellt werden (die exakten Methoden sind die bisher schon implementierten).

    23. November 2019: Iteratives Odd-Even-Mergesort, iteratives Pairwise Sorting Network und Dual-Pivot-Quicksort (letzteres von Wladimir Jaroslawskii), alle gefunden in diesem Javaprojekt von Piotr Grochowski (s.a. Danksagungen), hinzugefügt.

    11. November 2019:

    31. Oktober 2019:

    5. Oktober 2019:

    2. Oktober 2019:

    29. September 2019:

    21. September 2019: Noch ein weiteres Bead-/Gravitysort hinzugefügt.

    15. September 2019: Ein weiteres Bead-/Gravitysort hinzugefügt.

    3. September 2019:

    6. August 2019: Vom beschleunigten Naturalmergesort, das abfallende Teilmengen erkennt und invertiert, eine instabile Version implementiert.

    9. Juni 2019:

    9. April 2019: 4 weitere Startmengenstrukturen (je zweimal zwei verschiedengroße sortierte Teilmengen und mehrere verschiedengroße sortierte Teilmengen) implementiert

    25. März 2019: 6 weitere Sortieralgorithmen implementiert:

    15. März 2019: Jeder Verarbeitungsalgorithmus (Sortieren bzw. Mischen) kann mit Druck auf „P“ oder „p“ prozessorschonend unterbrochen (pausiert) und mit gleichenm Drucke auch wieder fortgesetzt werden.

    9. März 2019: Fünf Versionen des Fun-Sortes (Quelle unter Danksagungen (Autorenkollektiv)) implementiert.

    11. Februar 2019: Drei mehr oder weniger vereinfachte und modifizierte Versionen des Zig-Zag-Sorts nach Michael T. Goodrich (Quelle unter Danksagungen) implementiert.

    30. Januar 2019: Randomisiertes Shellsort nach Michael T. Goodrich (Quelle unter Danksagungen) hinzugefügt.

    27. Januar 2019: Bitonisches Merge- und Naturalmergesort je mit rekursiver Verschmelzungsprozedur für beliebige Elementeanzahlen und mithin auch für unterschiedlich große Teilarrays implementiert (iterative Verschmelzungsprozedur auch für verschieden große Teilarrays und damit für (Natural-)Mergesort für beliebige Elementeanzahlen war schon implementiert).

    25. Januar 2019: Annealing- und Spin-the-bottle-Sort nach Michael T. Goodrich (Quelle unter Danksagungen) sowie Quicksorts, eines mit perfekter und das andere mit meistens perfekter Halbierung, hinzugefügt

    9. Januar 2019:

    22. November 2018: Rekursives Naturalmergesort hinzugefügt (Idee siehe Danksagungen bei William A. Greene).

    4. November 2018: Positionierung der Werteausgabemitteilungsfensters überarbeitet (in den beiden mit Delphi compilierten Versionen).

    31. Oktober 2018: Mergealgorithmus von Heikki Mannila und Esko Ukkonen, zu finden je einmal bei den Merge- und den Naturalmergesorts, überarbeitet. Er ist jetzt (pseudo)rekursiv.

    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.

    • 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-, Binary-Search-Tree-, Fibonacci-, Merge-, Red-Black-, Skip-, Splay-, Tree- und Trisort.

    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


    Mein Beitrag

    Mein Beitrag zu diesem Programm besteht aus folgenden Punkten:
    • Wandermerge, ein recht langsamer, dafür aber wenigstens bedingt stabiler und In-Situ-Verschmelzungsalgorithmus (implementiert beim Merge- und beim Naturalmergesort). Ich nannte ihn so, weil der sog. „Workspace“ sichtbar durch das Array wandert.
    • n-Quicksort mit dem Kernalgorithmus n-Partition (Verallgemeinerung der Lomuto-Partitionierung), der ein (Teil-)Array mit einer (fast) beliebigen Anzahl an Pivotelementen partitioniert.
    • Einige wenige Verschmelzungsalgorithmen in diesem Programm funktionieren nur mit gleichgroßen (d.h., gleiche Elementeanzahlen) Teilarrays. Diese sind nur bei Mergesort mit Elementeanzahlen gleich einer Zweierpotenz gewährleistet. Damit diese Verschmelzungsalgorithmen für beliebig bzw. verschieden große Teilarrays und mithin auch für normales und Naturalmergesort nutzbar werden, entwickelte ich ein zunächst rekursives Unterprogramm zwecks Verschmelzungen („equalmerge“), das diese anspruchsvollen Verschmelzungsalgorithmen von verschiedengroßen Teilarrays abschirmt und diese mit nur gleichgroßen Teilarrays aufruft. Später transformierte ich dessen Rekursion noch in eine Iteration, wie ich es überall im Programm tat, um den Stackspeicher zu schonen. Die Funktionalität dieses Unterprogrammes kann ich nicht beweisen, aber bislang führte es seine Funktion fehlerlos aus.
    • Die rekursive Variante des Permutationsenumerationsalgorithmus von Steinhaus, Johnson und Trotter (implementiert in zwei Bogosorts).
    • Weiterhin stammt der Blocktauschalgorithmus „Kreuzindex“ in allen drei Geschwindigkeitsstufen von mir. Er funktioniert so, daß jedes Sortierelement vor dem Tausch seine Zielposition angeheftet bekommt. Der Rest ist mehr oder minder effizientes In-Situ-Umordnen.
    • Zuguterletzt stammen das einfache iterative Quicksort, die Naturalmergesorts, die wie einfaches Mergesort aussehen, sowie einige weitere Vereinfachungen und Modifikationen einiger Sortier- und Verschmelzungsalgorithmen von mir.
    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


    Ähnliche Programme

    Hier wäre vor allem The Sound of Sorting von Dipl.-Inf./Dipl.-Math. Dr. Timo Bingmann zu nennen. Leider wird das Programm nicht weiterentwickelt oder auch nur korrigiert, obwohl es m.E. nicht ganz fehlerfrei ist. Dafür gibt es auf Youtube Videos, die auf diesem Programm beruhen.

    Apropos Youtube. Die Youtuber w0rthy (Ethan Pattie), Musicombo/TheSaxophonStar (John Reynolds) und groszak1 (Piotr Grochowski) veröffentlichten auf jener Plattform ähnliche Filmchen. Schwerpunkt bei ihnen war nicht so sehr eine möglichst große Anzahl an Sortieralgorithmen, Startmengen und Vorsortierungen wie in diesem Programm, sondern eher vielfältige Darstellungformen der Sortierungen, die teilweise sehr beeindruckend sind. Die dort verlinkten Quellen (auch in den Danksagungen) der Sortieralgorithmen und des Programmes, mit dem sie animiert wurden, könnten Quellen für weitere Sortieralgorithmen für dieses Programm werden.

    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


    Meine anderen Programme

    Im Verlaufe der Jahre erstellte ich mit Delphi auch etliche andere Programme unterschiedlichen Umfanges (das Sortierkino ist jedoch das größte), von denen ich hier diejenigen zu veröffentlichen wage, die - im Gegensatz zur hier ausführlich vorgestellten „Dauerbaustelle“ - das Experimental- und Entwicklungsstadium verließen und die vorzustellen ich mich mithin nicht schämen zu müssen vermute. Enthalten sind in den Archiven sämtliche Quelltexte sowie die Compilate.

    Prozesse war ursprünglich ein reines Auflistungsprogramm für die laufenden Windows-Prozesse, wurde aber immer größer und umfangreicher. Auch prozeßbezogene Heaps, Heapblöcke, Module, Threads, Fenster und Kindfenster können angezeigt, konkret aufgelistet, zudem per Mausrechtsklick diese Prozesse auch (mehr oder weniger „gewaltsam“) beendet, zudem die Prioritäten der Prozesse und Threads geändert und zuguterletzt deren Zuordnungen zu Prozessor(kern)en verändert werden. Mit F5-Tastendruck läßt sich die Darstellung jederzeit aktualisieren. Aber Vorsicht: Wird das Programm mit Administrations-/Administratorrechten gestartet, werden daraufhin maximale Privilegien angefordert und diese schlußendlich auch gewährt, kann man mit diesem Programm sogar sehr „systemnahe“ Prozesse von Windows beenden, mit der Folge, daß Windows abstürzt bzw. einfriert oder zumindest geordnet herunterfährt. Wie im Sortierkino gibt es eine eigenständige Variante für Lazarus bzw. den Freepascal-Compiler. Compiliert mit Delph 2-4 und XE2 für die 32-Bit-Variante, mit Delphi XE2 für die 64-Bit-Variante sowie mit Lazarus 32 und 64 Bit je für die 32- und die 64-Bit-Variante.

    BadReceive ist ein sog. Bildschirmschoner. Derlei Programme sind ja seit dem Ende der Röhrenmonitorära eigentlich entbehrlich geworden und mithin aus der Mode gekommen. Dennoch interessierte mich deren Programmierung. Als Bildschirmschonung wählte ich einen Anblick, den so manche gar nicht mehr kennen (dürften), nämlich das schwarz-weiß-verrauschte Bild, wenn ein Analogfernseher keinen oder nur sehr schlechten Empfang hat. Wundert mich, daß anscheinend noch niemand sonst auf diese Idee kam. War im Antennenpegel in der Frequenznähe zum aktuellen Kanal auch ein Farbsignal enthalten, das zwar schwach, aber immer noch stark genug war, um den Farbdekoder anspringen zu lassen, wurde das Rauschen sogar farbig. Compiliert mit dem „kleinsten“ Delphi für 32 Bit, nämlich Delphi 2 von 1996. Installiert wird der Schoner entweder nach Rechtsklick auf die SCR-Datei oder per Ablage derselben in das Windows-Verzeichnis.

    UserPreferencesMask lautet auch ein gleichnamiger Eintrag in der sog. Registry bei NT-Windows-Betriebsprogrammen (bzw. UserPreferenceMask bei Windows 9x bis ME), mit dem sich die Windows-Optik verändern läßt, nämlich mit Optionen, die von den „Windows-Bordmitteln“ so zum großen Teil gar nicht angeboten werden. Leider ist das „manuelle“ Editieren dieses Eintrages per Registryeditor schwierig und fehleranfällig, weil alle möglichen Werte zu einer unhandlichen Datenstruktur vereint werden. Das sollte mit diesem kleinen Hilfsprogramm jedoch kein Problem mehr sein. Erstellt und compiliert mit Delphi 4.

    zurück zum Seitenanfang

    Kontakt

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

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

    Diese Internetseite wurde nur mit reinem HTML-Code erstellt bzw. programmiert und dürfte mithin, außer den animierten Bildern (GIF-Dateien), nach ihrem Laden keine Prozessorleistung beanspruchen.

    zurück zum Seitenanfang