Index

Erstellen einfacher Programme

2. Algorithmen (9b)

Sortieralgorithmen
- 2. Sortieren durch Auswahl - Teil b

Unsortierte Liste:

90 20 12 72 2 51 47 80

Hinweis: Das momentan kleinste Element ist rot, das Vergleichselement grün dargestellt.

1. Durchlauf:
90 20 12 72 2 51 47 80
Vergleichen 20 < 90 -> Austausch:
20 90 12 72 2 51 47 80
Nächstes Element der Liste:
20 90 12 72 2 51 47 80
Vergleichen 12 < 20 -> Austausch:
12 90 20 72 2 51 47 80
Nächstes Element der Liste:
12 90 20 72 2 51 47 80
Vergleichen 12 < 72 kein Austausch, nächstes Element der Liste:
12 90 20 72 2 51 47 80
Vergleichen 2 < 12 -> Austausch:
2 90 20 72 12 51 47 80
Nächstes Element der Liste:
2 90 20 72 12 51 47 80
Vergleichen 2 < 51 kein Austausch, nächstes Element der Liste:
2 90 20 72 12 51 47 80
Vergleichen 2 < 47 kein Austausch, nächstes Element der Liste:
2 90 20 72 12 51 47 80
Vergleichen 2 < 80 kein Austausch.
2 90 20 72 12 51 47 80

Nach dem ersten Durchlauf steht das kleinste Element auf Platz 1. Der zweite Durchlauf erfolgt damit ab Platz 2 in derselben Weise:

2. Durchlauf:
2 90 20 72 12 51 47 80
Vergleichen 20 < 90 -> Austausch, nächstes Element der Liste:
2 20 90 72 12 51 47 80
Vergleichen 20 < 72 kein Austausch, nächstes Element der Liste:
2 20 90 72 12 51 47 80
Vergleichen 12 < 20 -> Austausch, nächstes Element der Liste:
2 12 90 72 20 51 47 80
usw.
2 12 90 72 20 51 47 80
2 12 90 72 20 51 47 80

3. Durchlauf:
2 12 90 72 20 51 47 80
2 12 72 90 20 51 47 80
2 12 20 90 72 51 47 80
2 12 20 90 72 51 47 80
2 12 20 90 72 51 47 80

Nach 4. Durchlauf:
2 12 20 47 90 72 51 80

Nach 5. Durchlauf:
2 12 20 47 51 90 72 80

Nach 6. Durchlauf:
2 12 20 47 51 72 90 80

Nach 7. Durchlauf:
2 12 20 47 51 72 80 90

Da das letzte Element das größte sein muss und ein weiterer Vergleich nicht mehr möglich ist, gibt es keinen weiteren Durchlauf. Die Liste ist sortiert.

Sortierte Liste:

2 12 20 47 51 72 80 90

Unabhängig vom bereits sortierten Zustand einer Liste mit n Elementen ist immer dieselbe Anzahl von Vergleichen erforderlich.

Bestimmung der Anzahl der Vergleiche:
Es sind (n - 1) Durchläufe nötig. Beim ersten Durchlauf muss der erste Platz mit (n - 1) weiteren verglichen werden, beim zweiten Durchlauf der zweite Platz mit (n - 2) weiteren usw. Die Anzahl der Vergleiche summiert sich also in der Form 1 + 2 + 3 + ... + (n - 2) + (n - 1) = n(n - 1)/2.

Die Anzahl der Austausch-Operationen hängt von der Anfangssortierung ab. Im ungünstigsten Fall ist sie gleich der Zahl der Vergleiche.

Der Aufwand ist also quadratisch zur Anzahl der Elemente. O(n²)

[Struktogramm] zu diesem Sortieralgorithmus.

[Index] [Zurück/Sortieren 2a] [Fortsetzung/Sortieren 3]

Autor: Jürgen Dehmer
Letzte Änderung: 28. April 2001