Sortieren durch Auswählen / Selectionsort

Die Grundidee

Die folgende Abbildung verdeutlicht die Grundidee eines Sortierverfahrens, das "Sortieren durch Auswahl" oder "Selectionsort" genannt wird.

Aufgabe 1

(a) Welches Element wird hier jeweils ausgewählt (und mit einem Pfeil markiert)? Was wird mit diesem Element gemacht? Welche Eigenschaft hat der blau unterlegte Bereich? Beschreibe die Grundidee des Verfahrens in Worten.

(b) Spiele den beschrieben Sortiervorgang einige Schritte weiter (bis zum Ende) durch. Du kannst die folgende Kurznotation zur Dokumentation benutzen:

[]     [25  17  32  56  25  19   8  66  29   6  20  29]
                                             ^

[6]        [25  17  32  56  25  19   8  66  29  20  29]
                                     ^		 

[6   8]        [25  17  32  56  25  19  66  29  20  29]
                     ^		 

[6   8  17]        [25  32  56  25  19  66  29  20  29]
                                     ^		 

(c) Hier eine Variante des oben beschriebenen Sortierverfahrens. Was wird hier anders gemacht?

(d) Im Internet gibt es zahlreiche Animationen zum Sortierverfahren "Selectionsort", z.B. Selectionsort. Überprüfe mit einer Animation, ob du das Verfahren verstanden hast.

Ablaufmodellierung

Die Idee des Sortierverfahrens Sortieren durch Auswählen ist sehr einfach: Man sucht das kleinste Element im unsortierten Bereich und plaziert es in einen sortierten Bereich. Das macht man solange, wie Elemente im unsortierten Bereich sind.

Wir betrachten die Version mit zwei getrennten Bereichen (Listen):

[]     [25  17  32  56  25  19   8  66  29   6  20  29]
                                             ^
											 
[6]        [25  17  32  56  25  19   8  66  29  20  29]
                                     ^		 

[6   8]        [25  17  32  56  25  19  66  29  20  29]
                     ^		 

[6   8  17]        [25  32  56  25  19  66  29  20  29]
                                     ^

...

Informell lässt sich dieser Ablauf so beschreiben:

ALGORITHMUS selectionsort
Übergabe: Liste L
unsortierter Bereich ist die gesamte Liste L
der sortierte Bereich ist zunächst leer
SOLANGE der unsortierte Bereich noch Elemente hat:
    suche das kleinste Element im unsortierten Bereich
    entferne es im unsortierten Bereich
    füge es im sortierten Bereich an letzter Stelle an
Rückgabe: sortierter Bereich

Aufgabe 2

(a) Ergänze das folgende Struktogramm zur Präzisierung des Algorithmus selectionsort.

Beachte, dass hier ein Algorithmus entfernen benutzt wird, der an anderer Stelle präzisiert werden muss.

(b) Betrachte die Version mit einem Bereiche (Liste):

[25  17  32  56  25  19   8  66  29   6  20  29]
                                      ^

[ 6| 17  32  56  25  19   8  66  29  25  20  29]
                          ^		 

[ 6   8| 32  56  25  19  17  66  29  25  20  29]
                          ^		 

[ 6   8  17| 56  25  19  32  66  29  25  20  29]
                      ^		 

...

Beschreibe den Ablauf zunächst informell und modelliere ihn anschließend mit einem Algorithmus in Struktogrammform.

Aufgabe 3

Implementiere den Algorithmus selectionsort (in einer der betrachteten Varianten) und teste das entwickelte Programm.