Zum Hauptinhalt springen

Sortieren

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.

Aufgabe

Selection Sort ist:

Insertion Sort ist: