2.2 Auswahlsort

Diese Sortiermethode gehört zu den einfacheren, deren Zeitverhalten proportional zum Quadrat der zu sortierenden Elemente ist. Der Algorithmus ist sehr anschaulich und geht wie folgt:

1. Mache die Annahme: das erste Element ist das kleinste Element und merke diese Index.
2. Durchwandere das restliche Feld und tue für jedes Element folgendes:
   Ist das aktuelle Element kleiner als das gemerkte, merke diesen Index für das neue kleinste Element.
3. Vertausche das erste Element mit dem gefundenen kleinsten Element
4. Führe die Schritte 1 - 3 für das restliche unsortierte Feld durch, das nun ein Element weniger hat. Enthält das restliche Feld nur noch ein Element, ist das ganze Feld sortiert.

Dazu ein Beipiel mit folgenden unsortierten Feld:

Wir nehmen an, 3 ist das kleinste Element.

1 ist kleiner als 3, wir haben ein neues kleinstes Element.

2 ist nicht kleiner als 1. 1 bleibt das kleinste Element.

Wir vertauschen 1 und 3.

Wir fahren mit dem um eins kleineren Rest fort.

Wir nehmen an, 3 ist das kleinste Element.

2 ist kleiner als 3, wir haben ein neues kleinstes Element.

Wir vertauschen 2 und 3.

Das restliche Feld hat nur ein Element, wir sind fertig.

Der Algorithmus kann noch soweit verbessert werden, daß in einem Durchgang das kleinste und das größte Element gesucht werden und die Vertauschung nur dann durchgeführt wird, wenn in Schritt 2 ein neues kleinste Element gefunden wurde. Der Vergleich wird maximal N^2 durchgeführt, die Vertauschung aber nur maximal N mal. Damit ist der Aufwand bei langen Datensätzen günstiger als bei Bubblesort.

English version not yet available.