Wie sortieren Sie eigentlich eine Liste? Stellen Sie sich mal vor, Sie wollen irgendwelche Unterlagen nach Datum sortieren – wie machen Sie das?
Die meisten machen einen neuen (anfangs leeren) Stapel und nehmen dann Beleg für Beleg und sortieren diese einzeln in den neuen Stapel ein. In der Informatik nennt man dieses Vorgehen „InsertionSort“. Funktioniert bei Belegen super, weil die meistens schon irgendwie vorsortiert sind, dadurch geht das meist recht fix.
Nun wollen wir die (nach Datum sortierte) Liste nach Absender-Adressen sortieren.
Machen wir das genauso wie oben, wird’s schnell nervig und dauert. In der Informatik im schlechtesten Fall O(n^2) – gesprochen „O von n Quadrat“ (sorry, Nerd-Stuff mal wieder). Denn wir müssen – im worst case – jedes Element mit jedem anderen vergleichen. Das wiederum bedeutet, dass wir bei 10 Elementen im schlechtesten Fall 10^2 also 100 Einzelschritte durchführen müssen – und bei 100 Elementen bereits 10.000, bei 1000 Elementen 1.000.000 Schritte. Bäh.
Also was tun wir?
Wir verwenden z.B. MergeSort – einen Algorithmus, der mit O(n log n), also mit logarithmischer Komplexität, läuft. Das ist initial zwar deutlich komplizierter, braucht im schlechtesten Fall bei 10 Elementen aber nur 30 Einzelschritte (statt 100), bei 100 Elementen nur 700 (statt 10.000) und bei 1000 Elementen nur schlappe 10.000 Schritte (statt 1.000.000).
MergeSort basiert auf der Idee, dass wir all unsere Belege erst mal willkürlich verteilen (wir werfen das Zeug einfach auf den Boden). Dann bilden wir kleine Stapel (z.B. immer fünf Belege), die wir sortieren. Dann nehmen wir die 5-er Stapel und vergleichen diese jeweils mit einem anderen Stapel und sortieren daraus einen neuen 10-er Stapel. Das ist einfach, weil ich ja immer nur die obersten Elemente vergleichen muss. Dann machen wir dasselbe mit den 10-er Stapeln usw.
Also: bei kleinen Listen ist InsertionSort super, einfach, schnell, intuitiv. Aber ab ca. 30 Elementen kippt das. Da nervt das „einfache“ Sortieren nur noch und der Aufwand, etwas „komplizierter“ zu denken, lohnt sich.
In der Informatik gibt es ca. 15 zentrale Sortier-Algorithmen und ca. 50 weitere Varianten und Spezialfälle, die sich alle durch Laufzeitverhalten, Speicherverbrauch und die Größe des Chaos auf Ihrem Fußboden unterscheiden (scheinbar hatten wir über Jahre nichts anderes zu tun, als uns darüber Gedanken zu machen….).
Für mich sind Sortier-Algorithmen aber ein hervorragendes Beispiel dafür, dass es eben nicht immer die eine einzige und beste Lösung gibt und dass man viel Input „drumherum“ braucht, um entscheiden zu können, wie man ein Problem am besten angeht (inklusive der Größe des Fussbodens…).
Und jetzt probieren Sie einfach mal aus, was passiert, wenn Sie die KI bitten, Ihnen einen Vorschlag für die Sortierung einer Liste zu machen….. eine gute KI fragt jetzt nach der Größe Ihres Fussbodens….
Schönen Sonntag!