02 – Sortieren mit “Selection Sort”

 

In diesem Kapitel wird der Suchalgorithmus “Selection Sort” vorgeführt.

Die Grundlage dieses Algorithmus ist es, eine gegebene Liste mit n Einträgen (a0, a1, …, an-1) so umzusortieren, dass die entstehende Permutation der n Einträge aufsteigend angeordnet ist.

Beispiel:

Die folgende Liste soll sortiert werden:

Hierzu wird in jedem Schritt i das kleinste Element gesucht und mit dem i-ten vertauscht:

1. Schritt:

2. Schritt:

3. Schritt:

4. Schritt:

5. Schritt:

Die Liste ist immer nach n-1 Schritten fertig sortiert, da eine Liste mit einem Eintrag automatisch sortiert ist.

Das schrittweise Vorgehen, bei dem jedes Mal das gleiche für einen anderen Wert getan wird, nennt man “iteratives Vorgehen”.

Implementierung als Pseudocode

Sei A[0...n-1] eine Liste, die z.B. auf dem Rechner als zusammenhängender, per Index adressierbarer Bereich des Arbeitsspeichers reserviert ist. Eine solche Liste nennt man auch “Feld” oder englisch “array”.

Die Sortierung unterteilt sich nun in zwei Teilbereiche:

1. Finde im i-ten Schritt den Ort des kleinsten Elementes der Liste A[i...n-1].

In Pseudocode:

small = i
for j = i+1 to n-1:
	if A[j] < A[small]:
		small = j

Die Liste ab dem i+1-ten Element wird durchgegangen, immer wenn ein Element kleiner ist als der an der Stelle “small”, wird “small” aktualisiert.

2. Teilaufgabe: Vertausche kleinstes Element mit i-tem Element
Hier brauchen wir ein temporäres Element, um den Wert des i-ten Elementes zwischenzuspeichern. Dies ist vergleichbar mit dem Problem, dass man zwei Autos umparken möchte: man kann mit dem einen Auto nicht auf den Parkplatz des anderen Autos fahren, solange dieses noch dort steht. Es muss also zunächst ausgelagert werden.
Im Pseudocode:

temp = A[i]
A[i] = A[small]
A[small] = temp

Sortieralgorithmus “Selection Sort” vollständig in Pseudocode:

for i = 0 to n-2:
{
	small = i
	for j = i+1 to n-1:
		if A[j] < A[small]:
			small = j
	temp = A[i]
	A[i] = A[small]
	A[small] = temp
}

Implementierung in Java

Sortieralgorithmus “Selection Sort” vollständig in Javacode:

for (int i = 0; i < n-1; ++ i)
{
	int small = i;
	for (int j = i+1; j < n; ++ j)
		if (A[j] < A[small])
			small = j;
	int temp = A[i];
	A[i] = A[small];
	A[small] = temp;
}