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.