Selectionsort

aus Wikipedia, der freien Enzyklopädie

Der Begriff Sortierlese oder Selection-Sort (englisch selection »Auswahl«, to sort »sortieren«), auch MinSort (von Minimum) bzw. MaxSort (von Maximum), Selectsort oder ExchangeSort (AustauschSort) genannt, bezeichnet einen naiven 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, O(n²).

[Bearbeiten] Prinzip

Sei S der sortierte Teil des Arrays und U der unsortierte Teil. Am Anfang ist S noch leer, U entspricht dem ganzen Array. Das Sortieren durch Auswählen funktioniert so:

Suche das kleinste Element in U und vertausche es mit dem ersten Element.

Danach ist das Array bis zu dieser Position sortiert. S ist um ein Element gewachsen, U um ein Element kürzer geworden. Anschließend wird das Verfahren solange wiederholt, bis das gesamte Array abgearbeitet worden ist.

Alternativ sucht man das Maximum, also das Element mit dem größten Sortierschlüssel. Das Maximum wird dann mit dem letzten Element des Arrays vertauscht und man erhält ebenfalls ein sortiertes Teilarray der Länge 1, allerdings rechts, und ein unsortiertes Array der Länge n-1, diesmal links. Der Algorithmus wird dann auch auf das unsortierte Teilarray angewendet.

Zudem existieren auch Ansätze, in denen beide Varianten (MinSort und MaxSort) gemeinsam arbeiten, sprich während eines Durchlaufes das größte und das kleinste Element eines Arrays gesucht und dieses dann jeweils an den Anfang, bzw. an das Ende des Arrays, gesetzt werden. Dadurch hat man in der Regel eine Beschleunigung um den Faktor 2.

[Bearbeiten] Beispiel

Es soll ein Array mit dem Inhalt $[M | D | A | Z | G | Q]$ sortiert werden, wobei gilt: $A < B < C < ... < Y < Z$ . Rot eingefärbte Felder deuten eine Tauschoperation an, blau eingefärbte Felder liegen im bereits sortierten Teil des Arrays.

Das Minimum ist A. Vertausche also das 1. und das 3. Element

Das Minimum des rechten Teilarrays ist D. Da es bereits an 2. Position ist, muss praktisch nicht getauscht werden

Wir haben jetzt bereits ein sortiertes Teilarray der Länge 2. Wir vertauschen nun M und das Minimum G

Wir vertauschen Z und M

Wir vertauschen Z und Q

Das Array ist jetzt fertig sortiert

[Bearbeiten] Implementierung in diversen Programmiersprachen

[Bearbeiten] Java

public class SelectionSorter {

  private int[] a;

  // Konstruiert einen SelectionSorter
  public SelectionSorter(int[] anArray) {
    a = anArray;
  }

  // sortiert das array mit dem selection sorter;
  public void sort() {
    for(int i=0 ; i < a.length - 1 ; i++) {
      int minPos = minimumPosition(i);
      swap(minPos, i);
    }
  }

  // findet die kleinste zahl ausgehend vom ende
  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;
  }

  // swap zwei einträge im array
  private void swap(int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }
}

[Bearbeiten] C

//Parameter: Zeiger auf Feld, Index Startelement, Index Endelement
int findMinimum(int *feld, int start, int end)
{
        //Merker für Index des minimalen Elementes
        int minIdx;
        //Erstes Element ist vorerst das minimale Element
        minIdx = start;
 
        for ( int aktIdx = start + 1; aktIdx <= end; aktIdx++)
        {
                //Ist aktuelles Feldelement kleiner als das Bisherige?
                if ( feld[aktIdx] < feld[minIdx] )
                        //Neues Minimum
                        minIdx = aktIdx;
        }
 
        //Rückgabe des Index für minimales Feldelement
        return minIdx;
}
 
//Parameter: Zeiger auf Feld, Index der zu vertauschenden Elemente
void exchange(int *feld, int e1, int e2)
{
        //Merker für Tauschvorgang
        int tmp;
        //Tauschen
        tmp = feld[e1];
        feld[e1] = feld[e2];
        feld[e2] = tmp;
}
 
//Parameter: Zeiger auf Feld, Anzahl der Elemente
void selectionsort(int *feld, int anzahl)
{
        //Merker für Index des minimalen Elementes
        int minIdx;
 
        //Schleife zum Durchlaufen des Feldes
        for (int i = 0; i < anzahl; i++)
        {
                minIdx = findMinimum(feld, i, anzahl-1);
                exchange(feld, i, minIdx);
        }
}

[Bearbeiten] C#

static void SelectionSort(List<int> feld)
        {
            for (int i = 0; i < feld.Count; i++)
            {
                int min = i;
                for (int j = i + 1; j < feld.Count; j++)
                    if (feld[j] < feld[min])
                        min = j;
 
                int tmp = feld[min];
                feld[min] = feld[i];
                feld[i] = tmp;
            }
        }

[Bearbeiten] Oberon

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;

[Bearbeiten] Pascal

{ MinSort, als eine Variante von SelectionSort }
{ Uebergabe: Zu sortierendes Array, das an den Stellen 1 bis n mit natuerlichen Zahlen belegt ist }
Procedure MinSort(Var Feld: Array Of LongInt);
Var
  i, j     : LongInt;  { Zaehlvariablen }
  Temp, Min: LongInt;  { Zwischenspeicher, Minimum }
Begin
  For i := 0 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 MinSort }

[Bearbeiten] Visual Basic

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

[Bearbeiten] PHP

function selectionSort($array){
   for($a = 0; $a < count($array); $a++){
      $min = $a;
      for($b = $a; $b < count($array); $b++){
         if ($array[$b] < $array[$min]){$min=$b;}
      }                   
      $tmp = $array[$min];
      $array[$min] = $array[$a];
      $array[$a] = $tmp;
   }
   return $array;
}
 
 
//Zur Kontrolle
print_r(selectionSort(array(F,A,B,E,D,C,H,G)));

[Bearbeiten] Python

def selectionsort(seq):
    for k in range(len(seq) - 1):
        j = i = k
        for i in range(k, len(seq)):
            if seq[i] < seq[j]:
                j = i
        seq[j], seq[k] = seq[k], seq[j]
    return seq

[Bearbeiten] Ruby

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

[Bearbeiten] Haskell


sSort :: (Ord a) => [a] -> [a]
sSort [] = []
sSort xs = minimum xs : sSort (delete (minimum xs) xs)
{- delete löscht das erste Auftreten eines Elements, dadurch wird er stabil und erlaubt doppelte Elemente -}

[Bearbeiten] Smalltalk

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)

[Bearbeiten] Ada

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;

[Bearbeiten] Eiffel

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

[Bearbeiten] Scheme

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

[Bearbeiten] Komplexität

Um ein Array mit n Einträgen mittels SelectionSort zu sortieren, muss n-1 Mal das Minimum bestimmt und ebenso oft getauscht werden.

Bei der ersten Bestimmung des Minimums sind n-1 Vergleiche notwendig, bei der zweiten n-2 Vergleiche usw.

Mit der gaußschen Summenformel erhält man die Anzahl der notwendigen Vergleiche:

$(n-1)+(n-2)+...+3+2+1 =\frac{(n-1)\cdot n}{2}=\frac{n^2}{2}-\frac{n}{2}$

Man beachte, dass die exakte Schrittzahl dadurch, dass das erste Element $(n - 1)$ ist, nicht genau der Darstellung der Gaußformel $n+(n-1)+...+2+1 =\frac{n\cdot(n+1)}{2}$ entspricht.

SelectionSort liegt somit in der Komplexitätsklasse O(n²).

Da zum Ermitteln des Minimums jedoch immer der komplette noch nicht sortierte Teil des Arrays durchlaufen werden muss, liegt SelectionSort sogar in jedem Fall in dieser Komplexitätsklasse.

[Bearbeiten] Varianten

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.

[Bearbeiten] Perl

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"

[Bearbeiten] Python

# Zu Gunsten der Eleganz wurde teilweise auf Effizienz verzichtet.
def minmaxpos(list):
    if len(list) < 1:
        raise IndexError('Die Liste muss mindestens ein Element enthalten!')
    min, max = len(list) - 1, len(list) - 1
    for p in xrange(0, len(list) - 1, 2):
        if list[p] <= list[p + 1]:
            kleiner, groeszer = p, p + 1
        else:
            kleiner, groeszer = p + 1, p
        if list[kleiner] < list[min]:
            min = kleiner
        if list[groeszer] > list[max]:
            max = groeszer
    return min, max

def maxpos(list):
    max = 0
    for p in xrange(1, len(list)):
        if list[p] > list[max]:
            max = p
    return max

def minmaxsort(list):
    if len(list) <= 1:
        return
    unter, ober = 0, len(list) - 1
    if len(list) % 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(list)
        list[ober], list[max] = list[max], list[ober]
        ober -= 1
    while unter < ober:
        min, max = minmaxpos(list[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 max mit dem ehemaligen min getauscht werden
        list[min], list[unter] = list[unter], list[min]
        list[max], list[ober] = list[ober], list[max]
        unter, ober = unter + 1, ober - 1# Grenzen einengen

[Bearbeiten] Weblinks

VisuSort Framework - Visualisierung diverser Sortieralgorithmen (Windows)
Selectionsort Java Applet
http://www.inf.ethz.ch/~staerk/algorithms/SortAnimation.html Java Beispiele
http://www.sortieralgorithmen.de/selectsort/index.html
Erklärung und Code in C++

Kategorie: Sortieralgorithmus

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Selectionsort

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis

[Bearbeiten] Prinzip

[Bearbeiten] Beispiel

[Bearbeiten] Implementierung in diversen Programmiersprachen

[Bearbeiten] Java

[Bearbeiten] C

[Bearbeiten] C#

[Bearbeiten] Oberon

[Bearbeiten] Pascal

[Bearbeiten] Visual Basic

[Bearbeiten] PHP

[Bearbeiten] Python

[Bearbeiten] Ruby

[Bearbeiten] Haskell

[Bearbeiten] Smalltalk

[Bearbeiten] Ada

[Bearbeiten] Eiffel

[Bearbeiten] Scheme

[Bearbeiten] Komplexität

[Bearbeiten] Varianten

[Bearbeiten] Perl

[Bearbeiten] Python

[Bearbeiten] Weblinks

Views

Navigation

Mitmachen

Suche

Andere Sprachen