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 Θ(n2), damit ist es für größere Datenmengen nicht geeignet.

Selectionsort lässt sich als Sortiernetz implementieren.

Idee

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] auf­tritt, 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:

  1. für i=0 bis n-2 wiederhole
    1. für j=i+1 bis n-1 wiederhole
      1. wenn a[j] < a[i]
        1. vertausche a[i] mit a[j]

 

Programm

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

Sortiernetz

Das in Bild 1 dargestellte Sortiernetz realisiert das Verfahren Selectionsort.

 

Bild 1: Sortiernetz Selectionsort für n = 6 

Bild 1: Sortiernetz Selectionsort für n = 6

 

Analyse

Die Anzahl der Vergleiche, die Selectionsort zum Sortieren einer Datenfolge der Länge n benötigt, beträgt

n-1 + n-2 + ... + 1   =   
n·(n-1)
2
     ∈  Θ(n2).

 

Weiter mit:   [Odd-even Transposition Sort]   oder   [up]

 

H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Created: 20.09.2004   Updated: 07.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden