Zwei einfache Sortierverfahren

Ein zentrales Problem in der Informatik besteht im Sortieren von Daten. Das setzt voraus, dass zwischen den Einzeldaten eine Größer-Kleiner-Beziehung existiert, was z.B. bei Zahlen selbst-verständlich ist. Aber auch Zeichen- und Zeichenketten erlauben eine solche Beziehung, die durch das Alphabet gegeben ist. Diese lexikalische Anordnung ist in den meisten Programmier-sprachen implementiert, so dass z.B. in JAVA ein Vergleich der beiden Strings „papst“ > „papier“ möglich ist.

Wir betrachten als Beispiele einfache Felder von Ganzzahlen. Die Überlegungen sind ohne Probleme auf andere sortierbare Datentypen übertragbar.

1. Sortieren durch direktes Auswählen (MINSORT)

Prinzip: Das kleinste Element im unsortierten Teil des Feldes wird mit dem 1. Element des unsortierten Teils getauscht. Danach ist der unsortierte Teil um 1 Element kleiner geworden. Deshalb auch die Bezeichnung „Minsort“.