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. Sortier(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.:

  • „Anwendung“ (statt (Anwendungs-)Programm; ein Programm anzuwenden ist die Programmanwendung bzw. Anwendung des Programmes, es gibt aber keine Anwendung der Anwendung) 
  • „Benutzeroberfläche“ (statt Benutzungsoberfläche, die Benutzeroberfläche ist die menschliche Haut) „Betriebssystem“ (mit „System“ läßt sich alles beschreiben, besser wäre Betriebsprogramm)
  • „Kopierschutz“ (statt Kopiersperre, wenigstens aus Sicht des Computerbenutzers)
  • „Menü“ (was keines ist, da Wahlfreiheit herrscht) „Multimedia“ (Substantiv? Falls ja, welchen grammatikalischen Geschlechtes?)
  • „Teilen“ (statt Verbreiten)
  • „Textverarbeitung“ (statt besser bzw. einfach nur Text- oder Schreibprogramm, verarbeitet werden die Texte mit solchen Programmen eher nicht, höchstens noch bearbeitet)
  • „der Virus“ (Virus ist ein Neutrum)

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

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 finden und 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.

Kontaktformular