 | SelectionSort
Ein recht ineffizienter Sortieralgorithmus ist der SelectionSort!
| |
| Einführung
Definition
Die Idee beim SelectionSort ist ganz einfach: Man suche in der Eingabesequenz A das kleinste Element m und setze es vorne vor die sortierte Restsequenz. Die eigentliche Arbeit steckt hier in den Hilfsfunktionen. [FUNPROG]
Dieses Sortierverfahren wird auch als MinSort bezeichnet, da hier stets nach dem kleinsten Element (Minimum) der jeweiligen Restliste gesucht wird. Komplexität
Der Aufwand dieser Funktion ist — bei einer Liste von n Elementen — quadratisch, also in der Größenordnung O(n²), weil jedes Element der Liste betrachtet wird und bei der Minimumsuche jedesmal die ganze (Rest-) Liste abgearbeitet werden muss. [FUNPROG]
Beispiel: Sortieren von Spielkarten
Bei Kartenspielen, bei denen die Karten zunächst aufgedeckt auf dem Tisch liegen können: Der Spieler nimmt die jeweils niedrigste der auf dem Tisch verbliebenen Karten auf und kann sie in der Hand links (oder rechts) an die bereits aufgenommenen Karten anfügen. Dieser Algorithmus wird SelectionSort genannt. [INFO2002]
Konkretes Zahlenbeispiel
Dabei sei nun [8,2,5,3,9,1,6,7,4] die zu sortierende Liste: [8,2,5,3,9,1,6,7,4][] [8,2,5,3,9,6,7,4][1] [8,5,3,9,6,7,4][1,2] [8,5,9,6,7,4][1,2,3] [8,5,9,6,7][1,2,3,4] [8,9,6,7][1,2,3,4,5] [8,9,7][1,2,3,4,5,6] [8,9][1,2,3,4,5,6,7] [9][1,2,3,4,5,6,7,8] [][1,2,3,4,5,6,7,8,9]
| |
| Implementierung
Implementierung mit SML
| | |
| (* minimum: Hilfsfunktion
gibt das kleinste Element der Liste zurück
bzw. x, falls x kleiner ist als alle Listenelemente. *)
fun minimum x nil = x
| minimum x (y::yl) =
if (x < y)
then minimum x yl
else minimum y yl;
(* delete: Hilfsfunktion
löscht x aus gegebener Liste. *)
fun delete x nil = nil
| delete x (y::yl) =
if (x = y)
then yl
else y :: delete x yl;
(* selectionsort: klar!
min: das kleinste Element der Liste xl.
rest: die Liste xl ohne min *)
fun selectionsort nil = nil
| selectionsort (x::xl) =
let
val min = minimum x xl;
val rest = delete min (x::xl);
in
min :: (selectionsort rest)
end;
(* Anwendungsbeispiel *)
val output1 = selectionsort [3, 6, 2, 9, 1, 8, 7, 4, 5];
val output2 = selectionsort [7, 7, 7, 2, 7, 2, 2, 2];
val output3 = selectionsort [~3, 3, ~2, 2];
(* Ausgabe:
val output1 = [1,2,3,4,5,6,7,8,9] : int list
val output2 = [2,2,2,2,7,7,7,7] : int list
val output3 = [~3,~2,2,3] : int list *) | |
| | |
Folgendes Implementierungsbeispiel in Delphi demonstriert ein In-Placement-Verfahren des SelectionSort.
Implementierung mit Delphi
| | |
| unit USelectionSort;
interface
procedure SelectionSort(var A: array of Integer);
implementation
procedure SelectionSort(var A: array of Integer);
procedure Swap(var X, Y: Integer);
var
Swp: Integer;
begin
Swp := X;
X := Y;
Y := Swp;
end;
var
I, J: Integer;
begin
(* Nach dem ersten Durchgang ist Low(A) der Index des kleinsten Elements.
An die I-te Position wird nach und nach das kleinste Element (Minimum)
des unsortierten Rests geswappt. *)
for I := Low(A) to High(A) - 1 do
for J := I + 1 to High(A) do // der unsortierte Rest
if A[I] > A[J] then Swap(A[I], A[J]);
end;
end. | |
| | |
| |
| Seiteninfo
Literatur
[FUNPROG] |
Prof. Dr. Peter Pepper (TU Berlin): Funktionale Programmierung, Springer-Verlag, 1999, ISBN 3-540-64541-1.
In OPAL, ML, HASKELL und GOFER mit 34 Abbildungen |
| [INFO2002] |
| Heinz-Peter Gumm, Manfred Sommer: Einführung in die Informatik, Oldenbourg Verlag, Auflage 5, 2002, ISBN 3-486-25635-1 |
| |