Startseite
Informatik
Algorithmen
Sortieren
BucketSort
RadixSort
QuickSort
MergeSort
HeapSort
BubbleSort
DRUCK
2004
2005
2006
2007
2008
2009
SelectionSort
InsertionSort
SlowSort
BogoSort
Komprimieren
Suchen
Primzahltest
Datenstrukturen
Software-Engineering
Programmiersprachen
Künstliche Intelligenz
Schach
Privates
Inhalt
SelectionSort
Ein recht ineffizienter Sortieralgorithmus ist der SelectionSort!
Ein recht ineffizienter Sortieralgorithmus ist der SelectionSort!
Einführung
Theorie: SelectionSort
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.
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 des SelectionSort
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.
Quellenangabe
-
[FUNPROG]
-
[INFO2002]