Was heißt Sortieren?

Sortieren heißt der Worbedeutung nach (An-)Ordnen, Gruppieren oder Separieren von Objekten anhand ihrer Sorte. Sortieren kann man z.B. ein Gemenge aus Schrauben und Muttern oder Lebewesen nach dem Geschlecht oder der Artzugehörigkeit, Abfälle anhand ihrer Materialien (und nicht (Müll-)„Trennen“, die waren ja vorher nicht miteinander verbunden), also nach qualitativen Merkmalen, eben der allgemeinen Kategorie, die hier „Sorte“ genannt wird (und worunter sich alles mögliche subsumieren läßt). Ordnet man nur nach der Größe, der Wertigkeit oder anhand einer anderen quantitativen Größe, wie es meistens der Fall ist, handelt es sich eigentlich nur um ein „Ordnen“. Das Wort „Sortieren“ ist demnach semantisch (=begrifflich) leicht und zudem fehlerhaft überladen. Die Bezeichnung „Sortieren“ für bloßes „Ordnen“ ist genaugenommen falsch, wird hier aber beibehalten, da sie sich allgemein durchgesetzt hat. Zum Glück ist das nicht nur mir allein, sondern auch Hadmut Danisch aufgefallen. Letztlich hat sich damit eine verbale Schlamperei im Bereich der Computer eingeschlichen und durchgesetzt, wie es dort auch einige andere gibt, so z. B. „Textverarbeitung“ (statt Textprogramm oder Schreibprogram), „Benutzeroberfläche“ (statt Benutzungsoberfläche), „Anwendung“ (statt (Anwendungs-)Programm), „Kopierschutz“ (statt Kopiersperre), „teilen“ (statt verbreiten) und „Menü“ (was eben keines ist, da Wahlfreiheit herrscht).

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

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

Auch wir sortieren im alltäglichen Leben manchmal und dann meistens intuitiv, jedenfalls oft nicht streng i.S. eines konkreten Verfahren bzw. konkreten Algorithmus', so die Bücher im Regal (z.B. alphabetisch), Briefe und Photographien anhand ihres Alters / Entstehungsdatums, aufgenommene Spielkarten anhand ihres Wertes, nach der Wäsche die Kleidungsstücke anhand ihrer jeweiligen Träger und Erledigungen anhand ihrer Wichtigkeit und/oder Dringlichkeit u.v.m. Wir bringen demnach mit dem Sortieren diese Elemente anhand eines Ordnungskritierums/-merkmales in die gewünschte, „richtige“ Reihenfolge (wobei sich bei den Büchern und Spielkarten Insertion- oder Minsertion- und bei den Terminen Selectionsort anböten, ja geradezu aufdrängen).

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

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

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

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

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

Kontaktformular