Index

Erstellen einfacher Programme

2. Algorithmen (9a)


Sortieralgorithmen
- 2. Sortieren durch Auswahl - Teil a

Diese Art der Sortierung orientiert sich am üblichen Vorgehen, wie wir Daten "von Hand" sortieren. Man geht die Liste durch und sucht das kleinste Element aus und setzt es in eine neue Liste.

Unsortierte Liste:

90 20 12 72 2 51 47 80

1. Durchlauf:
90 20 12 72 2 51 47 80
Merken des momentan kleinsten Elements:
90
Vergleichen:
(90) 20 12 72 2 51 47 80
20 < 90 -> momentan kleinstes Element:
20
Vergleichen:
90 (20) 12 72 2 51 47 80
12 < 20 -> momentan kleinstes Element:
12
Vergleichen:
90 20 (12) 72 2 51 47 80
90 20 (12) 72 2 51 47 80
2 < 12 -> momentan kleinstes Element:
2
Vergleichen:
90 20 12 72 (2) 51 47 80
90 20 12 72 (2) 51 47 80
90 20 12 72 (2) 51 47 80

Nun wird das gefundene kleinste Element in eine neue Liste gesetzt und aus der alten Liste gestrichen. Das Streichen ist durch Klammerung angedeutet.

Unsortierte Liste:

90 20 12 72 (2) 51 47 80

Sortierte Liste:

2

Ein Problem stellt das Streichen eines Datenelements dar. Während man von Hand ein solches Element einfach durchstreichen kann, muss im Speicher eines Computers natürlich irgend ein Eintrag als Markierung einer Streichung festgelegt werden. Hierfür könnte ein Eintrag dienen, der mit Sicherheit nicht als Datenelement vorkommt. Aber weiß man das im vorraus?

Die Lösung dieses Problems ist recht simpel und sorgt sogar dafür, dass keine zwei getrennte Listen geführt werden müssen, also nicht zweifacher Speicher für die Daten benötigt wird:
Im ersten Durchlauf wird der erste Platz der Liste mit dem kleinsten Element besetzt. Da dieses an evtl. anderer Stelle nun seinen Platz "freimacht", kann dort das auf dem ersten Platz stehende Element untergebracht werden.

Enstprechend fährt man beim zweiten Durchlauf mit dem zweiten Platz fort, worauf man wieder das kleinste unter den restlichen Elementen setzt.

[Index] [Zurück/Sortieren 1] [Fortsetzung/Sortieren 2b]


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