Sortiernetze

Selectionsort

Selectionsort (Sortieren durch Auswählen) ist ein einfaches Sortierverfahren. Allerdings hat Selectionsort wie die Verfahren Insertionsort, Bubblesort und Odd-even Transposition Sort eine Zeitkomplexität von Θ(n²), damit ist es für größere Datenmengen nicht geeignet.

Selectionsort lässt sich als Sortiernetz implementieren.

Gegeben sei eine Datenfolge a[0], ..., a[n-1]. Der Grundgedanke von Selectionsort besteht darin, zunächst das Element a[0] mit allen folgenden Elementen a[1], ..., a[n-1] zu vergleichen und, wenn dort ein kleineres Element als a[0] auftritt, dieses mit a[0] zu vertauschen. Auf diese Weise enthält a[0] immer das Minimum der bis dahin untersuchten Elemente.

Anschließend wird a[1] mit allen folgenden Elementen verglichen usw.

Besteht die Folge aus n Elementen, so ist die Folge nach n-1 Durchläufen sortiert.


Algorithmus Selectionsort
Eingabe:	Datenfolge `a`[0], ..., `a`[`n`-1]
Ausgabe:	die sortierte Folge
Methode:	für `i`=0 bis `n`-2 wiederhole für `j`=`i`+1 bis `n`-1 wiederhole wenn `a`[`j`] < `a`[`i`] vertausche `a`[`i`] mit `a`[`j`]

Es folgt die Implementierung als Programm. Die Funktion selectionSort ist in einer Klasse SelectionSorter gekapselt.

Mit der Anweisung

SelectionSorter s=new SelectionSorter();

wird ein Objekt vom Typ SelectionSorter erzeugt. Mit

s.sort(b);

kann anschließend ein Array b sortiert werden.

public class SelectionSorter
{
    private int[] a;
    private int n;

    // übernimmt ein Array und sortiert es mit Selectionsort
    public void sort(int[] a_)
    {
        a=a_;
        n=a.length;
        selectionSort();
    }

    // sortiert das Array mit Selectionsort
    private void selectionSort()
    {
        int i, j;
        for (i=0; i<n-1; i++)
            for (j=i+1; j<n; j++)
                compare(i, j);
    }

    // vergleicht und vertauscht ggf. zwei Einträge im Array
    private void compare(int i, int j)
    {
        if (a[i]>a[j])
            exchange(i, j);
    }

    // vertauscht zwei Einträge im Array
    private void exchange(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

}    // end class SelectionSorter