Lernmaterialien

Sort

Bubble Sort

Gern. Ich erkläre dir den Bubble Sort wirklich langsam, Schritt für Schritt.

Was ist Bubble Sort?

Bubble Sort ist ein einfaches Sortierverfahren.

Es sortiert eine Liste von Werten, zum Beispiel Zahlen, in die richtige Reihenfolge, meistens von klein nach groß.

Beispiel:

Aus

[5, 2, 8, 1, 4]

soll werden:

[1, 2, 4, 5, 8]

Der Name Bubble Sort kommt daher, dass bei jedem Durchlauf die größeren Elemente nach rechts “hochsteigen”, fast so, als würden Blasen in Wasser nach oben steigen.

Die Grundidee

Bubble Sort schaut sich immer zwei benachbarte Elemente an:

• Sind sie in der falschen Reihenfolge, dann werden sie vertauscht.

• Sind sie schon richtig, dann bleiben sie so.

Das macht man mehrfach hintereinander, bis alles sortiert ist.

Ganz einfaches Beispiel

Nehmen wir diese Liste:

Array:   [5 2 8 1]
Position: 0 1 2 3

Wir wollen aufsteigend sortieren.

Erster Durchlauf

Wir vergleichen immer zwei Nachbarn.

Position: 0+1 ; 1+2 ; 2+3

Ausgangslage:

[5, 2, 8, 1]

Position: 0+1 Vergleich; falsch => vertauschen

[2, 5, 8, 1]

Position: 1+2 Vergleich; richtig

[2, 5, 8, 1]

Position: 2+3 Vergleich; falsch => vertauschen

[2, 5, 1, 8]

public void sortBubble() {
   double hilf;
   for (int i=0; i<anzahl-1; i++) {
      if (temp[i] > temp[i+1]) {
         hilf = temp[i+1];
         temp[i+1] = temp[i];
         temp[i] = hilf;
      }
   }
}

Zweiter Durchlauf

Ausgangslage:

[2, 5, 1, 8]

Position: 0+1 Vergleich; richtig

[2, 5, 1, 8]

Position: 1+2 Vergleich; falsch => vertauschen

[2, 1, 5, 8]

Position: 2+3 Vergleich; richtig

[2, 1, 5, 8]

Dritter Durchlauf

Ausgangslage:

[2, 1, 5, 8]

Position: 0+1 Vergleich; falsch => vertauschen

[1, 2, 5, 8]

Position: 1+2 Vergleich; richtig

[1, 2, 5, 8]

Position: 2+3 Vergleich; richtig

[1, 2, 5, 8]

Bei jedem kompletten Durchlauf passiert Folgendes:

• die größte noch unsortierte Zahl wandert ganz nach rechts

• danach die zweitgrößte

• dann die drittgrößte

• und so weiter

Deshalb braucht Bubble Sort meistens mehrere Durchläufe.

Wenn das Array n Elemente hat, dann benötigen wir n-1 Durchläufe!

    public void sortBubble() {
        double hilf;
        for (int j=0; j<anzahl-1; j++) {
            for (int i = 0; i < anzahl - 1; i++) {
                if (temp[i] > temp[i + 1]) {
                    hilf = temp[i + 1];
                    temp[i + 1] = temp[i];
                    temp[i] = hilf;
                }
            }
        }
    }

Optimierung

Die innere Schleife muss bei jedem Durchlauf der äußeren Schleife ein Element weniger betrachten.

for (int i = 0; i < anzahl - 1 - j; i++) {

Die äußere Schleife wird solange durchlaufen bis das Array sortiert ist. Es wurde keine einzige Vertauschung vorgenommen.

    public void sortBubble() {
        int j=0;
        double hilf;
        boolean sorted=false;

        while (sorted == false) {
            sorted = true;
            for (int i = 0; i < anzahl - 1 - j; i++) {
                if (temp[i] > temp[i + 1]) {
                    hilf = temp[i + 1];
                    temp[i + 1] = temp[i];
                    temp[i] = hilf;
                    sorted = false;
                }
            }
            j++;
        }
    }

JUnit

Die Methode prüft, ob das Array sortiert ist.

    public boolean isSorted() {
        for (int i=0; i<anzahl-1; i++) {
            if (temp[i] > temp[i+1]) {
                return false;
            }
        }
        return true;
    }

Die Methode verwenden wir im JUnit Test.

    @Test
    public void testBubbleSort() {
        Temperatur t = new Temperatur();
        t.testdaten2();
        t.sortBubble();
        t.ausgeben();
        assertEquals(true, t.isSorted());
    }

Selection Sort

Selection Sort ist ein einfaches Sortierverfahren, bei dem man immer das kleinste Element im unsortierten Teil sucht und es an die richtige Stelle vorne setzt.

Grundidee

Stell dir ein Array vor:

int[] a = {5, 3, 8, 1, 4};

Ablauf:

1. Suche das kleinste Element im ganzen Array.

2. Tausche es mit dem ersten Element.

3. Suche danach das kleinste Element im restlichen Array.

4. Tausche es mit dem zweiten Element.

5. Wiederhole n-1 mal

Schritt für Schritt

Start:

[5, 3, 8, 1, 4]

1. Durchlauf

Kleinstes Element ist 1
Tausch mit erstem Element 5

[1, 3, 8, 5, 4]

2. Durchlauf

Im restlichen Teil [3, 8, 5, 4] ist 3 das kleinste
Tausch mit 3

[1, 3, 8, 5, 4]

3. Durchlauf

Im restlichen Teil [8, 5, 4] ist 4 das kleinste
Tausch mit 8

[1, 3, 4, 5, 8]

4. Durchlauf

Im restlichen Teil [5, 8] ist 5 das kleinste
Tausch mit 5

    public void sortSelection() {
        double min;
        int minPos;

        for (int j=0; j<anzahl-1; j++) {
            min = 9999;
            minPos = -1;
            for (int i = j; i < anzahl; i++) {
                if (temp[i] < min) {
                    min = temp[i];
                    minPos = i;
                }
            }
            temp[minPos] = temp[j];
            temp[j] = min;
        }
    }