Algorithmensammlung: Sortierverfahren: Selectionsort

Algorithmensammlung: Sortierverfahren

SelectionsortBearbeiten

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 ProgrammiersprachenBearbeiten

  AdaBearbeiten

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;

  CBearbeiten

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;
    }
}

  EiffelBearbeiten

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

  HaskellBearbeiten

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.

  JavaBearbeiten

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;
    }
}

Bearbeiten

;Bestimmt Index des kleinsten Elements in a, geprüft ab Element start
to minIdx :start :a
 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

  OberonBearbeiten

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;

  PascalBearbeiten

{ 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 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 }

  PHPBearbeiten

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')));

  PythonBearbeiten

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]

  RubyBearbeiten

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

  SchemeBearbeiten

(require (lib "list.ss"))
(define selection_sort
  (lambda (l)
    (if (empty? l) 
        '()
        (let ((m (apply min l)))
          (cons m (selection_sort (remove m l)))
         ))))

  SmalltalkBearbeiten

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 BasicBearbeiten

 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 .NETBearbeiten

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

VariantenBearbeiten

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.

PerlBearbeiten

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"

PythonBearbeiten

# 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