Index

Erstellen einfacher Programme

2. Algorithmen (10)


Sortieralgorithmen
- 3. Sortieren durch Einfügen

Bei diesem Verfahren werden die Datenelemente aus einer unsortierten Liste der Reihen nach entnommen und in einer neuen Liste an der alphabetisch richtigen Position eingefügt.
Dies geschieht dadurch, dass das neue Element z.B. am Ende angehängt wird und durch Vergleichen mit dem Vorgängerelement solange mit diesem vertauscht wird, wie dieses größer ist.

Zwar liegt auch hier ein quadratischer Aufwand (O(n²)) zur Anzahl der Datenelemente vor, wenn aber wenige neue Daten zu einer bereits sortierten Datenmenge hinzugefügt werden sollen, ist dieses Verfahren durchaus interessant.

Unsortierte Liste:

90 20 12 72 2 51 47 80

Sortierte Liste:

Unsortierte Liste:

1. Einsortieren:
90   20 12 72 2 51 47 80

2. Einsortieren:
90 20   12 72 2 51 47 80
Tauschen:
20 90   12 72 2 51 47 80

3. Einsortieren:
20 90 12   72 2 51 47 80
Tauschen:
20 12 90   72 2 51 47 80
Tauschen:
12 20 90   72 2 51 47 80

4. Einsortieren:
12 20 90 72   2 51 47 80
Tauschen:
12 20 72 90   2 51 47 80

5. Einsortieren:
12 20 72 90 2   51 47 80
Tauschen:
12 20 72 2 90   51 47 80
Tauschen:
12 20 2 72 90   51 47 80
Tauschen:
12 2 20 72 90   51 47 80
Tauschen:
2 12 20 72 90   51 47 80

6. Einsortieren:
2 12 20 72 90 51   47 80
Tauschen:
2 12 20 72 51 90   47 80
Tauschen:
2 12 20 51 72 90   47 80

7. Einsortieren:
2 12 20 51 72 90 47   80
Tauschen:
2 12 20 51 72 47 90   80
Tauschen:
2 12 20 51 47 72 90   80
Tauschen:
2 12 20 47 51 72 90   80

8. Einsortieren:
2 12 20 47 51 72 90 80  
Tauschen:
2 12 20 47 51 72 80 90  

Sortierte Liste:

2 12 20 47 51 72 80 90

In diesem Beispiel waren
18 Vergleiche und
14 Vertauschungen nötig.

Die Anordnung zeigt, dass auch hier nur eine Liste benötigt wird, deren erster Teil die sortierten und deren zweiter Teil die unsortierten Datenelemente enthält.

[Struktogramm] zu diesem Sortieralgorithmus.

[Index] [Zurück/Sortieren 2] [Fortsetzung/Sortieren 4]


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