Algorithmensammlung: Sortierverfahren: Selectionsort
Selectionsort Bearbeiten
Selectionsort ist ein naiver Sortieralgorithmus, der in-place arbeitet und in seiner Grundform instabil ist, wobei er sich auch stabil implementieren lässt. Die Komplexität von Selectionsort ist, in der Landau-Notation ausgedrückt, . Das Sortierverfahren Selectionsort kann in mehreren Youtube Videos in bildlicher Darstellung genossen werden.
Für weitere Informationen siehe Selectionsort.
Implementierung in diversen Programmiersprachen Bearbeiten
Ada Bearbeiten
begin
for i in 1..n loop
min:=A(i);
pos:=i;
for j in i+1..n loop
if A(j)< min then
min:=A(j);
pos:=j;
end if;
end loop;
A(pos):=A(i);
A(i):=min;
end loop;
end;
C Bearbeiten
void selectionsort( int anzahl, int daten[]) // Anzahl und Array mit Daten
{
int i, k, t, min; // i ist Kontrollvariable für die äußere, k für die innere Schleife.
// t ist Zwischenspeicher beim Tauschen. min merkt sich den kleinsten Wert
// im Teilarray.
for( i = 0; i < anzahl-1; i++)
{
min = i;
for( k = i+1; k < anzahl; k++)
{
if( daten[k] < daten[min])
min = k;
}
t = daten[min]; // Tauschen
daten[min] = daten[i];
daten[i] = t;
}
}
C# Bearbeiten
static void SelectionSort(ref List<int> feld)
{
// alle Zahlen durchlaufen
for (int i = 0; i < feld.Count; i++)
{
// Position min der kleinsten Zahl ab Position i suchen
int min = i;
for (int j = i + 1; j < feld.Count; j++)
{
if (feld[j] < feld[min])
{
min = j;
}
}
// Zahl an Position i mit der kleinsten Zahl vertauschen
int tmp = feld[min];
feld[min] = feld[i];
feld[i] = tmp;
}
}
Eiffel Bearbeiten
Aufgeteilt in zwei Features (arraymin und selectionsort), damit der Code übersichtlicher ist.
arraymin(array: ARRAY [INTEGER]; lower, upper: INTEGER) is
-- Get index of Array minimum between lower and upper index
local
i, smallestsofar, index: INTEGER
do
from
i:=lower
smallestsofar := array.item (i)
index := i
until
i+1 > upper
loop
if array.item(i+1) < smallestsofar then
smallestsofar := array.item(i+1)
index := i+1
end
i := i + 1
end
minindex := index
minitem := array.item (index)
end
minindex: INTEGER
--stores the index of the minimum with arraymin
minitem: INTEGER
--stores the minimum of the value found with arraymin
selectionsort (x: ARRAY [INTEGER]) is
-- sort Array x with selectionsort
local
count: INTEGER
size: INTEGER
do
from
count:=1
size := x.count
until
count > size
loop
arraymin (x, count, size)
x.put (x.item (count), minindex)
x.put (minitem, count)
count := count + 1
end
end
Haskell Bearbeiten
import Data.List (delete)
sSort :: (Ord a) => [a] -> [a]
sSort [] = []
sSort xs = m : sSort (delete m xs)
where
m = minimum xs
-- delete löscht das erste Auftreten eines Elements
-- in einer Liste.
Java Bearbeiten
public class SelectionSorter
{
private int[] a; // zu sortierendes Array
// übernimmt die Referenz auf ein Array und sortiert es
public void sort(int[] anArray)
{
a=anArray;
selectionSort();
}
// sortiert das Array a mit Selectionsort
private void selectionSort()
{
for (int i=0; i<a.length-1; i++)
{
int minpos=minimumPosition(i);
swap(minpos, i);
}
}
// findet die Position der kleinsten Zahl ab Position from
private int minimumPosition(int from)
{
int minpos=from;
for (int i=from+1; i<a.length; i++)
if (a[i]<a[minpos])
minpos=i;
return minpos;
}
// vertauscht zwei Einträge im Array
private void swap(int i, int j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
Logo Bearbeiten
;Bestimmt Index des kleinsten Elements in a, geprüft ab Element start to minIdx :start :ab localmake "result :start localmake "i :start while [:i <= count :a] [ if (item :i :a) < (item :result :a) [make "result :i] make "i :i + 1 ] output :result end ;Vertauscht im Array a das x-te mit dem y-ten Element to swap :a :x :y localmake "hilf item :x :a setitem :x :a item :y :a setitem :y :a :hilf end ;Sortiert das Array a to selSort :a localmake "i 1 while [:i < count :a] [ swap :a :i minIdx :i :a make "i :i + 1 ] end ;Aufruf: make "array {6 4 8 0 7 5 1} selsort :array show :array
Oberon Bearbeiten
PROCEDURE SelectSort* ( VAR a : ARRAY OF INTEGER ; n : INTEGER );
VAR
i, j, min, temp : INTEGER;
BEGIN
FOR i := 0 TO n-2 DO
min := i;
FOR j := i+1 TO n-1 DO
IF a[j] < a[min] THEN min := j END
END;
IF min # i THEN
temp := a[i]; a[i] := a[min]; a[min] := temp;
END
END
END SelectSort;
Pascal Bearbeiten
{ Parameter: Zu sortierendes Array, das mit ganzen Zahlen belegt ist }
Procedure SelectionSort(Var Feld: Array Of LongInt);
Var
i, j : LongInt; { Zaehlvariablen }
Temp, Min: LongInt; { Hilfsvariable, Position des Minimums }
Begin
For i := Low(Feld) To Pred(High(Feld)) Do
Begin
Min := i;
For j := i+1 To High(Feld) Do
If Feld[j] < Feld[Min] Then
Min := j;
Temp := Feld[Min];
Feld[Min] := Feld[i];
Feld[i] := Temp;
End;
End; { Procedure SelectionSort }
PHP Bearbeiten
function selectionSort($array)
{
for ($i=0; $i<count($array); $i++)
{
// Position des kleinsten Elements suchen
$minpos=$i;
for ($j=$i+1; $j<count($array); $j++)
if ($array[$j]<$array[$minpos])
{
$minpos=$j;
}
// Elemente vertauschen
$tmp=$array[$minpos];
$array[$minpos]=$array[$i];
$array[$i]=$tmp;
}
return $array;
}
//Zur Kontrolle
print_r(selectionSort(array('F', 'A', 'B', 'E', 'D', 'C', 'H', 'G')));
Python Bearbeiten
def selectionsort(seq):
for i in range(len(seq) - 1):
k = i
for j in range(i + 1, len(seq)):
if seq[j] < seq[k]:
k = j
seq[i], seq[k] = seq[k], seq[i]
Ruby Bearbeiten
def selectionsort(list)
0.upto(list.size-2) do |start|
min = start
(start+1).upto(list.size-1) do |i|
min = i if list[i] < list[min]
end
list[start], list[min] = list[min], list[start]
end
list
end
oder alternativ mit for-in-Schleifen und Range-Objekten:
def selSort(list)
for i in (0..list.size-2)
for j in (i.succ..list.size.pred)
list[i], list[j] = list[j], list[i] if list[i] > list[j]
end
end
end
Hinweise: Die Methode #succ ermittelt den Nachfolger (successor) eines Ordinalwertes, #pred steht für den Vorgänger (predecessor).
Scheme Bearbeiten
(require (lib "list.ss"))
(define selection_sort
(lambda (l)
(if (empty? l)
'()
(let ((m (apply min l)))
(cons m (selection_sort (remove m l)))
))))
Smalltalk Bearbeiten
Die erste Zeile gibt an, in welche Klasse man die Methoden einfügt.
!SequenceableCollection methodsFor: 'sorting' !
selectionSort
self withIndexDo: [:e :i| self swap:i with: (self indexOf:(self last:self size-i+1) min) ]! !
Ergebnis: #(1 2 3 4) shuffled selectionSort → #(1 2 3 4)
Visual Basic Bearbeiten
Sub SelectionSort()
Dim Lowest As Integer, Temp As Integer, I As Integer, J As Integer
For I = 0 To UBound(Feld) - 1
Lowest = I
For J = I + 1 To UBound(Feld)
If Feld(J) < Feld(Lowest) Then
Lowest = J
End If
Next J
Temp = Feld(I)
Feld(I) = Feld(Lowest)
Feld(Lowest) = Temp
Next I
End Sub
Visual Basic .NET Bearbeiten
Sub SelectionSort()
Dim feld() as Integer = {2, 9, 5, 4, 7, 3, 1, 8, 6}
For i as Integer = 0 To feld.Length - 1
Dim lowest as Integer = i
For j as Integer = i + 1 to feld.Length
lowest = If(feld(j) > feld(lowest), j, lowest)
next
Dim temp as Integer = feld(i)
feld(i) = feld(lowest)
feld(lowest) = temp
next
End Sub
Varianten Bearbeiten
Heapsort arbeitet nach demselben Prinzip wie SelectionSort, benutzt jedoch die Eigenschaften eines Heaps, um das Minimum schneller zu bestimmen.
Es besteht die Möglichkeit MinSort und MaxSort miteinander zu kombinieren. Es wird dann gleichzeitig sowohl nach dem jeweils größten, als auch nach dem jeweils kleinsten Element gesucht.
Perl Bearbeiten
sub minmax{
my $n,$l,$i,$j;
$n=$_;
$l=int($#_/2);
for($i=0;$i<=$l;$i++){
for($j=$i+1;$j<$n;$j++){
if($_[$i]>$_[$n]){
($_[$i],$_[$n])=($_[$n],$_[$i])
}
if($_[$j]<$_[$i]){
($_[$i],$_[$j])=($_[$j],$_[$i])
}elsif($_[$j]>$_[$n]){
($_[$j],$_[$n])=($_[$n],$_[$j])
}
}$n--
}return@_
}
@array=minmax(@array);
print"@array\n"
Python Bearbeiten
# Zu Gunsten der Eleganz wurde teilweise auf Effizienz verzichtet.
def minmaxpos(liste):
if len(liste) < 1:
raise IndexError('Die Liste muss mindestens ein Element enthalten!')
min, max = len(liste) - 1, len(liste) - 1
for p in xrange(0, len(liste) - 1, 2):
if liste[p] <= liste[p + 1]:
kleiner, groeszer = p, p + 1
else:
kleiner, groeszer = p + 1, p
if liste[kleiner] < liste[min]:
min = kleiner
if liste[groeszer] > liste[max]:
max = groeszer
return min, max
def maxpos(liste):
max = 0
for p in xrange(1, len(liste)):
if liste[p] > liste[max]:
max = p
return max
def minmaxsort(liste):
if len(liste) <= 1:
return
unter, ober = 0, len(liste) - 1
if len(liste) % 2 == 0:# Die Anzahl der Elemente muss ungerade sein.
# Ist sie gerade, so wird das letzte Element mit dem Maximum vertauscht und dann ignoriert.
max = maxpos(liste)
liste[ober], liste[max] = liste[max], liste[ober]
ober -= 1
while unter < ober:
min, max = minmaxpos(liste[unter: ober + 1])# Minimum und Maximum der Restliste bestimmen
min, max = min + unter, max + unter# unter wurde in der Funktion mit 0 adressiert
# Minimum<->Untergrenze; Maximum<->Obergrenze
if max == unter:# Da unter und min getauscht werden,
max = min # muss ober mit dem ehemaligen min (nach dem Tausch max) getauscht werden
liste[min], liste[unter] = liste[unter], liste[min]
liste[max], liste[ober] = liste[ober], liste[max]
unter, ober = unter + 1, ober - 1# Grenzen einengen