Sortiernetze

Bubblesort

 aufwärts

Bubblesort ist das einfachste Sortier­verfahren. Allerdings hat es eine Zeit­komplexität von Θ(n2), damit ist es für größere Datenmengen nicht geeignet. Denn bereits bei einigen zig-tausend Daten ist Bubblesort 1000-mal langsamer als ein schnelles Sortier­verfahren wie etwa Mergesort oder Heapsort.

Bubblesort lässt sich als Sortiernetz implementieren.

Idee

Der Algorithmus Bubblesort durchläuft Element für Element die zu sortierende Datenfolge. Wird dabei ein Element erreicht, das kleiner als das vorherige Element ist, so wird es mit diesem vertauscht. Dadurch ist das aktuelle Element immer das Maximum aller bisher durch­laufenen Elemente. Ist die Folge zu Ende durchlaufen, steht das größte Element der Folge an letzter Position.

Im nächsten Durchlauf wird das zweitgrößte Element an die vorletzte Position befördert, und so weiter. Besteht die Folge aus n Elementen, so ist die Folge nach n-1 Durchläufen sortiert.

Sortiernetz

Den eben skizzierten Ablauf gibt das in Bild 1 dargestellte Sortiernetz Bubblesort wieder. Mit der ersten Diagonalen von Vergleichern wird das größte Element an das Ende der Folge befördert. Mit der zweiten Diagonalen wird das zweitgrößte Element an die vorletzte Position befördert usw.

Bild 1: Sortiernetz Bubblesort für n = 6
Bild 1: Sortiernetz Bubblesort für n = 6

Analyse

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

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

Programm

Es folgt die Implementierung als Programm. Die Funktion bubbleSort ist in einer Klasse BubbleSorter gekapselt.

Mit der Anweisung

BubbleSorter s=new BubbleSorter();

wird ein Objekt vom Typ BubbleSorter erzeugt. Mit

s.sort(b);

kann anschließend ein Array b sortiert werden.

 

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

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

    // sortiert das Array mit Bubblesort
    private void bubbleSort()
    {
        int i, j;
        for (i=n; i>1; i--)
            for (j=1; j<i; j++)
                if (a[j-1]>a[j])
                    exchange(j-1, j);
    }

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

}    // end class BubbleSorter

 

Weiter mit:   [Selectionsort]   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