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 haben bereits die beiden Sortier-Algorithmen "Selection-Sort" und "Insertion-Sort" angeschaut und auf ihre Komplexität und Eigenschaften hin vergleichen.
Eigenschaften
Folgende Eigenschaften lassen sich bei Sortier-Algorithmen unterscheiden:
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.
Selection Sort ist:
Insertion Sort ist:
Sortieren