Suchen und Sortieren

Eine binäre Suche setzt voraus, dass die Daten nach dem zu suchenden Element sortiert sind.

• iteratives Vorgehen

• Komplexität: n

• aufzählbare Eintrage

Größe, die bei Eintritt gewisser Veränderungen unveränderlich bleibt.

Sagt bei Sortieralgorithmen aus, was geprüft während der Schleife gelten muss. So ist die Invariante bei einer While-Schleife, ungleich deren Bedingung

Viele Sortieralgorithmen nutzen eine Tausch bzw. Swapfunktion, bei der 2 Elemente deren Plätze tauschen.

Verwendet nicht Swap!!! Und es ist kein in-Place-Algorithmus!!!!

Stabiles Sortierverfahren mit der komplexität O(l*n)

l ist die maximale Schlüssellänge

Radix Sort teilt sich in die Partitionierungsphase und Sammelphase auf. Es gibt dabei genau l Durchgänge. Begonnen wird mit dem letzten Element des Schlüssels bis zum ersten