Sortiernetze

Selectionsort

 aufwärts

Selectionsort (Sortieren durch Auswählen) ist ein einfaches Sortier­verfahren. Allerdings hat Selectionsort wie die Verfahren Insertionsort, Bubblesort und Odd-even Trans­position Sort eine Zeit­komplexitä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] 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:
  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
    Element  Θ(n2).

 

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

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 20.09.2004   Updated: 03.03.2017
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik