Im letzten Kapitel haben wir gesehen, wieso man überhaupt sortiert: Man findet das Zeugs schneller!

Das Sortieren ist natürlich sehr aufwändig. Aber wenn man mal sortiert hat, dann kann man beliebig viele Suchen effizient durchführen.

Wir wollen uns nun verschiedene Sortier-Algorithmen anschauen und auf ihre Komplexität und Eigenschaften hin vergleichen.

Eigenschaften #

Folgende Eigenschaften werden wir anschauen:

in-place #

Ein Sortier-Algorithmus ist in-place, wenn während dem Sortieren nur eine konstante Anzahl Elemente ausserhalb der Eingabe-Liste gespeichert werden.

stabil #

Ein Sortier-Algorithmus ist stabil, wenn er die Reihenfolge von Elementen mit gleichem Wert nicht ändert.

rekursiv #

Ein Sortier-Algorithmus ist rekursiv, wenn er sich selbst aufruft.