Kurs Diskussion:Algorithmen und Datenstrukturen/Kapitel 2/SelectionSort

Ich würde das gern etwas umstellen. Mehr Details und genauere Formulierungen:

Herleitung

Wir haben bei BubbleSort beobachtet, dass der Algorithmus in jedem Durchlauf das größte Element ans Ende des Arrays geschoben wurde. Anstatt es direkt dorthin zu kopieren, wurde das Element um eine Stelle nach der anderen nach vorn geschoben.

Bei Selection Sort vermeidet man diese Ineffizienz. Es wird dort zwischen 2 Bereichen unterschieden: dem sortierten und dem unsortierten. Man geht bei der Sortierung folgendermaßen vor.

Am Anfang gibt es nur den unsortierten Bereich. Man sucht aus der gegebenen Liste das kleinste Element heraus und fügt es am Anfang der Liste ein. Dieses Element bildet den sortierten Bereich. Im nächsten Durchgang sucht man wieder im unsortierten Bereich nach dem kleinsten Element und fügt es am Ende des sortierten Bereiches an. Nicht vergessen, dass erste Element war das kleinste aus dem gesamten unsortierten Bereich und somit ist das zweit kleinste größer bzw. gleich dem ersten Element aus dem sortierten Bereich.

Man geht pro Durchgang also immer folgendermaßen vor:

kleinstes Element aus dem unsortierten Bereich heraussuchen
das Element dann an das Ende des sortierten Bereiches stellen

Am Ende liegt dann wieder eine sortierte Liste vor.

Implementierung in ObjectPascal

Nachfolgend wird Selection Sort in Object Pascal implementiert. Hier wird als Liste ein Array genommen.

 1. PROCEDURE SelectSort* ( VAR a : ARRAY OF INTEGER ; n : INTEGER );
 2.     VAR
 3.         i, j, min, temp : INTEGER;
 4.     BEGIN

            (* Arraylänge überprüfen *)
 5.         IF n > LEN(a) THEN
 6.             Out.String("Fehler: n ist größer als die Arraylaenge!"); Out.Ln;
 7.             RETURN;
 8.         END;

            (* Für jede Position... *)
 9.         FOR i := 0 TO n-2 DO

                (* Suche das Minimum *)
10.             min := i;
11.             FOR j := i+1 TO n-1 DO
12.                 IF a[j] < a[min] THEN min := j END
13.             END;

                (* Vertausche falls nötig *)
14.             IF min # i THEN
15.                 temp := a[i]; a[i] := a[min]; a[min] := temp;
16.             END

17.         END
18.     END SelectSort;

Anmerkung: Die Schleife über i (Zeilen 9 bis 17) durchläuft die Reihe nach alle Stellen des Arrays bis auf die letzte (TO n-2). Es wird angenommen, dass das kleinste Element ab der iten Stelle schon das Element an der Stelle i ist (Zeile 10). Danach werden alle Elemente ab dem iten mit dem vermeintlichen kleinsten Element verglichen (Schleife Zeilen 11 bis 13). Wir ein kleineres Element gefunden, so wird min neu gesetzt (Zeile 12). Ist das kleinste Element nun nicht mehr das an der iten Stelle, so wird es mit diesen Vertauscht (Zeile 15).

Für ein Array der Länge 6 sieht der Vorgang in Bildern wie folgt aus:

Der Name dieses Algorithmus (Selection Sort) kommt daher, dass wir iterativ das kleinste Element selektieren und an die richtige Stelle vertauschen. Der Algorithmus ist auch bekannt unter den Namen MinSort (oder auch MaxSort, je nach Richtung des Sortierens) oder auch einfach SelectSort.

Für detailliertere Informationen: Selection Sort bei Wikipedia

Abschnitt hinzufügen