MINT lernen

Bubblesort

Kann man eine Reihung sortieren, indem man immer nur zwei Nachbarn vergleicht?

1

Große Werte steigen auf

Ein Paketdienst sortiert fünf Paketgewichte (in kg) aufsteigend. Bubblesort (Sortieren durch Vertauschen) schaut dabei immer nur auf zwei Nachbarn.

  • Paar prüfen:benachbarte Elemente a[j] und a[j+1] vergleichen; steht das größere links, werden beide getauscht.
  • Durchlauf:einmal von links nach rechts alle Nachbarpaare des unsortierten Teils prüfen.
  • Aufsteigen:das größte Element wird bei jedem Tausch mitgenommen und landet am rechten Ende — wie eine Blase, die nach oben steigt.
Durchlauf 1 für gewicht = 5, 3, 8, 1, 4
jPaarTausch?gewicht danach
05 | 3ja3 5 8 1 4
15 | 8nein3 5 8 1 4
28 | 1ja3 5 1 8 4
38 | 4ja3 5 1 4 8
  • Nach Durchlauf k:die k größten Elemente stehen rechts an ihrem endgültigen Platz; der unsortierte Teil ist um k kürzer.
  • Ende:nach \(n-1\) Durchläufen ist die Reihung sortiert — das letzte übrige Element ist dann automatisch das kleinste.
2

Aufwand und vorzeitiger Abbruch

public static void bubbleSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {          // Durchlauf i
        for (int j = 0; j < a.length - 1 - i; j++) {  // nur der unsortierte Teil
            if (a[j] > a[j + 1]) {
                int hilf = a[j];                       // Nachbarn tauschen
                a[j] = a[j + 1];
                a[j + 1] = hilf;
            }
        }
    }
}
  • Grenze - 1 - i:- 1, weil a[j + 1] sonst über das Ende hinausgreift; - i, weil die i größten Elemente schon fest stehen.
  • Stabil:getauscht wird nur bei >. Gleiche Werte überholen sich nie und behalten ihre Reihenfolge.
Herleitung:
\(V=(n-1)+(n-2)+\dots+2+1\)
Durchläufe
Durchlauf 1 vergleicht \(n-1\) Paare, jeder weitere Durchlauf eines weniger.
\(2V=(n-1)\cdot n\)
doppelt
Die Summe vorwärts und rückwärts untereinander schreiben: \(n-1\) Spalten, jede ergibt \(n\).
\(V=\dfrac{n(n-1)}{2}\)
Ergebnis
Für die fünf Paketgewichte: \(\frac{5\cdot4}{2}=10\) Vergleiche — egal, wie die Werte liegen.
  • Verschwendung:ist die Reihung früher sortiert, vergleicht die Grundversion trotzdem weiter.
  • Flag getauscht:merkt sich, ob im Durchlauf getauscht wurde. Ein Durchlauf ohne Tausch beweist: alles sortiert — Abbruch.
public static void bubbleSortMitAbbruch(int[] a) {
    boolean getauscht = true;
    for (int i = 0; i < a.length - 1 && getauscht; i++) {
        getauscht = false;                             // neuer Durchlauf
        for (int j = 0; j < a.length - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int hilf = a[j];
                a[j] = a[j + 1];
                a[j + 1] = hilf;
                getauscht = true;                      // es gab einen Tausch
            }
        }
    }
}

Decke die Durchläufe mit ▶ oder „Nächster Durchlauf“ nacheinander auf. Klicke eine Zahl an, um ihre Spur durch alle Durchläufe zu verfolgen, und vergleiche einen Durchlauf über seine Nummer links mit dem Zustand davor. Schalte dann den Abbruch ein und probiere „fast sortiert“.

Durchläufe übereinander

Halte fest: Jeder Durchlauf bringt mindestens das größte noch unsortierte Element an seinen Platz. Kleine Werte wandern dagegen pro Durchlauf höchstens einen Platz nach links.

Merke

Bubblesort (Grundversion): \(\dfrac{n(n-1)}{2}\) Vergleiche, stabil, in-place.

3

Allgemeine Hinweise

Grenze der inneren Schleife

Mit j < a.length - i greift a[j + 1] im ersten Durchlauf auf a[a.length] zu — ArrayIndexOutOfBoundsException.

Tausch immer über hilf

a[j] = a[j + 1]; a[j + 1] = a[j]; tauscht nicht, sondern kopiert: danach steht zweimal derselbe Wert in der Reihung.

Der Abbruch hilft nicht immer

Steht ein kleiner Wert ganz hinten, wandert er pro Durchlauf nur einen Platz nach links. Dann braucht auch die Version mit getauscht alle \(n-1\) Durchläufe.

Videos