Worum geht es in dieser Aktivität?

Es ist wesentlich einfacher Informationen in einer geordneten Liste zu finden, als wenn man sie in einer ungeordneten Liste suchen müsste. Telefonbücher, Wörterbücher und Verzeichnisse sind alphabetisch geordnet und das Leben wäre wesentlich weniger bequem, wenn sie es nicht wären. Wenn eine Liste von Zahlen (wie zum Beispiel eine Liste mit Ausgaben) geordnet vorliegt, ist es einfach die Extremen zu sehen, weil sie sich ganz am Anfang oder ganz am Schluss der Liste befinden, während sie in unsortierten Listen überall vorkommen können. Auch doppelte Einträge findet man einfach, da diese in sortierten Listen direkt nebeneinander liegen.

Computer verbringen einen großen Teil der Zeit damit, Dinge zu ordnen. Also ist es für InformatikerInnen von Interesse dies schnell und gut zu machen. Einige der langsameren Methoden, wie beispielsweise Sortieren durch Einfügen, Sortieren durch Auswählen oder Bubblesort, können in gewissen Situationen sehr nützlich sein, doch in den meisten Fällen verwendet man ein schnelles Verfahren, wie zum Beispiel Quicksort.

Quicksort verwendet ein Konzept, das man Rekursion nennt. Das bedeutet, dass wir die Liste immer wieder in kleinere Teile unterteilen und auf diesen kleineren Teilen genau dasselbe tun wie wir es vorher beim größeren Teil gemacht haben. Diesen Ansatz im Speziellen nennt man ,Teile und Herrsche’. Die Liste wird immer wieder unterteilt, bis wir schließlich fähig sind (wenn die Liste klein genug ist) deren Ordnung zu bestimmen. Im Falle von Quicksort werden die Listen unterteilt bis sie nur noch ein Element enthalten, da es einfach ist eine Menge mit nur einem Element zu sortieren. Das klingt zwar kompliziert, verhilft uns aber in der Praxis dazu, wesentlich schneller zum Ziel zu kommen als mit anderen Methoden.