Sortieralgorithmen und Vergleichsfunktionen: Bubblesort, Selectionsort, Insertionsort und eigene Sortierkriterien

https://bildung.social/@oerinformatik/

https://oer-informatik.de/sortieralgorithmen

Sortieralgorithmen, Bubblesort, Selectionsort, Insertionsort, Vergleichsfunktion, Comparator, Stabilität, Laufzeitkomplexität, Pseudocode, Prüfungsvorbereitung

tl/dr; (ca. 23 min Lesezeit): „Der Sortieralgorithmus muss selbst erstellt werden“ – dieser Satz taucht in Aufgaben immer wieder auf. Der Artikel zeigt die drei einfachen Verfahren Bubblesort, Selectionsort und Insertionsort mit Pseudocode und Schreibtischtest, erklärt, wie Du Objekte, zweidimensionale Arrays und gefilterte Daten auf- oder absteigend sortierst, und wie eine Vergleichsfunktion das Sortierkriterium austauschbar macht. Dazu kommen Bausteine rund ums Sortieren (Wertebereich prüfen, in freie Felder einfügen, Stellen mit DIV und MOD herauslösen), Stabilität, Laufzeit, typische Fehler und ein Vorgehen für Aufgaben [AI-Assisted]. (Zuletzt geändert am 27.10.2026)

Dieser Artikel ist Teil einer Artikelreihe über Algorithmen und Programmentwurf: Algorithmen mit Pseudocode dokumentieren / Übersicht der Programmentwurfsmethoden / Prozedurale Algorithmen mit Arrays / Objektorientierte Algorithmen / Sortieralgorithmen und Vergleichsfunktionen / Übungsaufgaben zu Sortieralgorithmen

Schon fit in diesem Thema? Nutze die Kann-Liste und die Leitfragen unter dem Artikel als Checkliste, ob Du die relevanten Kompetenzen bereits hast.

Dieser Artikel baut auf der Kann-Liste des Artikels Prozedurale Algorithmen mit Arrays auf.

Als Algorithmik-Grundlagen kann ich nach Durchlesen des Artikels…

… einen Sortieralgorithmus (z. B. Bubblesort) für ein Array von Zahlen oder Objekten auf- und absteigend in Pseudocode, als Struktogramm oder Programmablaufplan erstellen und das gewählte Verfahren benennen.
… zwei Elemente mit einer Hilfsvariablen tauschen und die Schleifengrenzen so wählen, dass kein Zugriff hinter das Array-Ende erfolgt.
… einen vorgegebenen Sortieralgorithmus mit einem Schreibtischtest Durchlauf für Durchlauf nachvollziehen und unvollständigen Sortiercode ergänzen.
… Objekte nach einem Attribut oder einem berechneten Wert sortieren und dabei immer ganze Objekte bzw. ganze Zeilen eines zweidimensionalen Arrays tauschen.
… Daten in einer Funktion zuerst filtern und anschließend sortieren und ein neues Element an der richtigen Stelle in ein sortiertes Array einfügen.
… eine Vergleichsfunktion erstellen, die einen negativen Wert, 0 oder einen positiven Wert liefert, und sie in einem Sortieralgorithmus als Parameter verwenden.
… vor dem Einfügen prüfen, ob ein Wert in einem erlaubten Bereich liegt (Bedingung mit UND), einen Wert in das erste freie Feld eines Arrays einfügen und eine einzelne Stelle einer Kennzahl mit Ganzzahldivision (DIV) und Modulo (MOD) ermitteln.

Darüber hinaus kann ich als Algorithmik-Expertenwissen…

… Bubblesort, Selectionsort und Insertionsort nach Vorgehen, Stabilität und Aufwand unterscheiden und die Anzahl der Vergleiche abschätzen.
… mehrstufige Vergleichsfunktionen (erst nach Kategorie, dann nach Preis) und eine umgekehrte Sortierrichtung über die Vergleichsfunktion umsetzen.
… beurteilen, wann eine Sortierung besser in der Datenbank (ORDER BY) oder über eine Bibliotheksfunktion erfolgt als mit einem eigenen Algorithmus.

Sortieren ist eine der ältesten Aufgaben der Informatik – und in der Praxis fast immer schon erledigt: Datenbanken sortieren mit ORDER BY, Programmiersprachen bringen fertige Sortierfunktionen mit. Trotzdem verlangen Aufgaben in der Anwendungsentwicklung regelmäßig, dass Du einen Sortieralgorithmus selbst formulierst. Der Grund: An einem Sortieralgorithmus zeigt sich, ob Du geschachtelte Schleifen, Indexgrenzen, Vergleiche und das Tauschen von Werten sicher beherrschst. Häufig ist die Sortierung nur ein Teil einer größeren Funktion: Erst werden passende Datensätze ausgewählt, dann sortiert zurückgegeben.

Gute Nachricht vorweg: Du musst kein schnelles Verfahren kennen. Ein sauber formulierter Bubblesort reicht fast immer aus. Wichtiger ist, dass Du ihn an die Aufgabe anpassen kannst – absteigend, über Objekte, über Zeilen eines zweidimensionalen Arrays oder mit einer austauschbaren Vergleichsfunktion.

Die Schreibweise in diesem Artikel

Vorausgewählt ist das deutsche Pseudo-Pascal aus dem Artikel Prozedurale Algorithmen mit Arrays: := für die Zuweisung, = und <> für Vergleiche, zähle i von a bis b für eine Zählschleife (beide Grenzen eingeschlossen), Indizes beginnen bei 0, laenge(werte) liefert die Anzahl der Elemente. Für dieses Thema kommen drei Dinge hinzu:

Ergänzungen der Pseudocode-Schreibweise für Sortieralgorithmen
Element	Schreibweise
Getter eines Objekts	`artikel[j].getPreis()`
Liste mit Zugriffsmethoden	`liste.get(i)`, `liste.set(i, element)`, `liste.size()`
Funktion als Parameter	`Prozedur sortiere(werte: Artikel[], vergleiche: Function<Artikel>)`
Aufruf der übergebenen Funktion	`vergleiche(a, b)`

Aufgaben verwenden oft eine Java-nahe Schreibweise (for (i = 0; i < kurse.length - 1; i++)). Beides ist gleichwertig. Übernimm die Namen, Typen und Methoden, die die Aufgabe vorgibt.

Die Codebeispiele kannst Du in vier Notationen anzeigen. Die Notationen sind im Artikel Algorithmen mit Pseudocode dokumentieren beschrieben.

Das Werkzeug aller Verfahren: vergleichen und tauschen

Jedes der hier vorgestellten Verfahren besteht aus zwei Grundoperationen: Es vergleicht zwei Elemente und tauscht sie, wenn sie in der falschen Reihenfolge stehen.

Beim Tauschen brauchst Du eine Hilfsvariable (Ringtausch). Ohne sie geht ein Wert verloren:

// falsch: nach der ersten Zeile steht in beiden Feldern derselbe Wert
werte[j] = werte[j + 1]
werte[j + 1] = werte[j]

// richtig: Ringtausch über die Hilfsvariable hilf
int hilf = werte[j]
werte[j] = werte[j + 1]
werte[j + 1] = hilf

// falsch: nach der ersten Zeile steht in beiden Feldern derselbe Wert
werte[j] := werte[j + 1]
werte[j + 1] := werte[j]

// richtig: Ringtausch über die Hilfsvariable hilf
hilf: integer := werte[j]
werte[j] := werte[j + 1]
werte[j + 1] := hilf

// falsch: nach der ersten Zeile steht in beiden Feldern derselbe Wert
werte[j] := werte[j + 1]
werte[j + 1] := werte[j]

// richtig: Ringtausch über die Hilfsvariable hilf
hilf: integer := werte[j]
werte[j] := werte[j + 1]
werte[j + 1] := hilf

Die Hilfsvariable hat denselben Typ wie die Elemente. Sortierst Du Objekte, ist hilf eine Objektvariable (hilf: Artikel); bei einer Zeile eines zweidimensionalen Arrays tauschst Du jede Spalte einzeln oder die ganze Zeile auf einmal (siehe unten).

Beim Vergleichen entscheidet der Operator über die Sortierrichtung:

wenn werte[j] > werte[j + 1] tauscht, wenn das linke Element größer ist – das Ergebnis ist aufsteigend sortiert (kleinster Wert vorne).
wenn werte[j] < werte[j + 1] tauscht, wenn das linke Element kleiner ist – das Ergebnis ist absteigend sortiert (größter Wert vorne).

Mehr musst Du für eine absteigende Sortierung nicht ändern.

Bubblesort: benachbarte Elemente tauschen

Die Idee

Bubblesort (Sortieren durch Vertauschen, bubble sort) läuft das Array von vorne nach hinten durch und vergleicht jeweils zwei benachbarte Elemente. Gehört das linke Element hinter das rechte, werden beide getauscht. Nach dem ersten Durchlauf ist das größte Element ganz hinten angekommen – es ist wie eine Luftblase nach oben „geblubbert“. Im zweiten Durchlauf landet das zweitgrößte Element auf dem vorletzten Platz und so weiter.

Ein Beispiel mit werte = [7, 3, 9, 2, 5]:

Bubblesort für [7, 3, 9, 2, 5] – je Durchlauf ein Element weniger
Durchlauf	Vergleiche (getauscht in Klammern)	Array danach	sortiert ab Index
1	7/3 (getauscht), 7/9, 9/2 (getauscht), 9/5 (getauscht)	`[3, 7, 2, 5, 9]`	4
2	3/7, 7/2 (getauscht), 7/5 (getauscht)	`[3, 2, 5, 7, 9]`	3
3	3/2 (getauscht), 3/5	`[2, 3, 5, 7, 9]`	2
4	2/3	`[2, 3, 5, 7, 9]`	0

Bei fünf Elementen sind höchstens vier Durchläufe nötig: Stehen die vier größten Elemente an ihrem Platz, ist auch das kleinste richtig einsortiert. Jeder Durchlauf kann um ein Element früher enden, weil hinten bereits sortiert ist.

Der Algorithmus

bubblesort(int werte[]) {
    int n = length(werte)
    for (int i = 0 … n-2) {                    // n - 1 Durchläufe
        for (int j = 0 … n-2-i) {              // hinten sind i Elemente fertig
            if (werte[j] > werte[j + 1]) {
                int hilf = werte[j]
                werte[j] = werte[j + 1]
                werte[j + 1] = hilf
            }
        }
    }
}

PROCEDURE bubblesort(werte: array of integer)
    n: integer := length(werte)
    for i := 0 to n - 2 do                     // n - 1 Durchläufe
        for j := 0 to n - 2 - i do             // hinten sind i Elemente fertig
            if (werte[j] > werte[j + 1]) then
                hilf: integer := werte[j]
                werte[j] := werte[j + 1]
                werte[j + 1] := hilf
            end if
        end for
    end for
END bubblesort

Prozedur bubblesort(werte: integer[])
    n: integer := laenge(werte)
    zähle i von 0 bis n - 2                    // n - 1 Durchläufe
        zähle j von 0 bis n - 2 - i            // hinten sind i Elemente fertig
            wenn werte[j] > werte[j + 1] dann
                hilf: integer := werte[j]
                werte[j] := werte[j + 1]
                werte[j + 1] := hilf
            Ende wenn
        Ende zähle
    Ende zähle
Ende bubblesort

In Java-naher Schreibweise sieht derselbe Algorithmus so aus:

for (int i = 0; i < werte.length - 1; i++) {
    for (int j = 0; j < werte.length - 1 - i; j++) {
        if (werte[j] > werte[j + 1]) {
            int hilf = werte[j];
            werte[j] = werte[j + 1];
            werte[j + 1] = hilf;
        }
    }
}

Die Schleifengrenzen – die häufigste Fehlerquelle

Die innere Schleife greift auf werte[j + 1] zu. Der größte erlaubte Wert für j ist deshalb n - 2, damit j + 1 höchstens der letzte Index n - 1 ist. Läuft j bis n - 1, greift der Algorithmus im ersten Durchlauf auf ein Element hinter dem Array zu – in Java ist das eine ArrayIndexOutOfBoundsException.

Achte bei den Grenzen genau auf die Schreibweise:

Gleiche Grenze, unterschiedliche Schreibweisen
Schreibweise	Bedeutung
`zähle j von 0 bis n - 2 - i`	obere Grenze eingeschlossen
`for (j = 0; j < n - 1 - i; j++)`	obere Grenze ausgeschlossen – gleichwertig zur Zeile darüber
`für j = 0 bis n - i - 1` mit Zugriff auf `j + 1`	im ersten Durchlauf (`i = 0`) ein Element zu weit

Das - i in der inneren Schleife ist eine Optimierung: Hinten stehen nach i Durchläufen bereits i fertige Elemente. Lässt Du es weg, ist der Algorithmus immer noch richtig, vergleicht aber unnötig oft.

Optimierung: früher aufhören, wenn nichts mehr getauscht wird

Im Beispiel oben ist das Array schon nach dem dritten Durchlauf sortiert; der vierte vergleicht nur noch. Merkt sich der Algorithmus in einer Variablen getauscht, ob im aktuellen Durchlauf überhaupt getauscht wurde, kann er aufhören, sobald ein Durchlauf ohne Tausch bleibt. Ein bereits sortiertes Array ist dann nach einem einzigen Durchlauf erledigt.

bubblesortMitAbbruch(int werte[]) {
    int ende = length(werte) - 1            // letzter Index, der noch verglichen wird
    repeat {
        boolean getauscht = false
        for (int j = 0 … ende-1) {
            if (werte[j] > werte[j + 1]) {
                int hilf = werte[j]
                werte[j] = werte[j + 1]
                werte[j + 1] = hilf
                getauscht = true
            }
        }
        ende = ende - 1
    } until (!getauscht)
}

PROCEDURE bubblesortMitAbbruch(werte: array of integer)
    ende: integer := length(werte) - 1      // letzter Index, der noch verglichen wird
    repeat
        getauscht: boolean := false
        for j := 0 to ende - 1 do
            if (werte[j] > werte[j + 1]) then
                hilf: integer := werte[j]
                werte[j] := werte[j + 1]
                werte[j + 1] := hilf
                getauscht := true
            end if
        end for
        ende := ende - 1
    until (NOT getauscht)
END bubblesortMitAbbruch

Prozedur bubblesortMitAbbruch(werte: integer[])
    ende: integer := laenge(werte) - 1      // letzter Index, der noch verglichen wird
    wiederhole
        getauscht: boolean := false
        zähle j von 0 bis ende - 1
            wenn werte[j] > werte[j + 1] dann
                hilf: integer := werte[j]
                werte[j] := werte[j + 1]
                werte[j + 1] := hilf
                getauscht := true
            Ende wenn
        Ende zähle
        ende := ende - 1
    solange getauscht
Ende bubblesortMitAbbruch

Als Struktogramm nach DIN 66261 mit fußgesteuerter Schleife:

Struktogramm: Bubblesort mit Abbruch, wenn in einem Durchlauf nicht mehr getauscht wurde (mit KI erstellt)

Die fußgesteuerte Schleife passt hier gut, weil mindestens ein Durchlauf immer nötig ist. Mit einer kopfgesteuerten solange-Schleife setzt Du getauscht := true vor die Schleife.

Selectionsort: das Extremum nach vorne holen

Selectionsort (Sortieren durch Auswählen, selection sort) geht anders vor: Er sucht im noch unsortierten Teil das kleinste Element und tauscht es an die erste unsortierte Position. Das Suchen kennst Du aus dem Grundmuster „Minimum und Maximum samt Position“ im Artikel Prozedurale Algorithmen mit Arrays.

Selectionsort für [7, 3, 9, 2, 5]
i	kleinstes Element im Bereich i … 4 (Index)	Array nach dem Tausch
0	2 (Index 3)	`[2, 3, 9, 7, 5]`
1	3 (Index 1, kein Tausch nötig)	`[2, 3, 9, 7, 5]`
2	5 (Index 4)	`[2, 3, 5, 7, 9]`
3	7 (Index 3, kein Tausch nötig)	`[2, 3, 5, 7, 9]`

selectionsort(int werte[]) {
    int n = length(werte)
    for (int i = 0 … n-2) {
        int posMin = i
        for (int j = i+1 … n-1) {
            if (werte[j] < werte[posMin]) {
                posMin = j
            }
        }
        if (posMin != i) {
            int hilf = werte[i]
            werte[i] = werte[posMin]
            werte[posMin] = hilf
        }
    }
}

PROCEDURE selectionsort(werte: array of integer)
    n: integer := length(werte)
    for i := 0 to n - 2 do
        posMin: integer := i
        for j := i + 1 to n - 1 do
            if (werte[j] < werte[posMin]) then
                posMin := j
            end if
        end for
        if (posMin <> i) then
            hilf: integer := werte[i]
            werte[i] := werte[posMin]
            werte[posMin] := hilf
        end if
    end for
END selectionsort

Prozedur selectionsort(werte: integer[])
    n: integer := laenge(werte)
    zähle i von 0 bis n - 2
        posMin: integer := i
        zähle j von i + 1 bis n - 1
            wenn werte[j] < werte[posMin] dann
                posMin := j
            Ende wenn
        Ende zähle
        wenn posMin <> i dann
            hilf: integer := werte[i]
            werte[i] := werte[posMin]
            werte[posMin] := hilf
        Ende wenn
    Ende zähle
Ende selectionsort

Für eine absteigende Sortierung suchst Du das Maximum (werte[j] > werte[posMax]). Selectionsort vergleicht genauso oft wie Bubblesort, tauscht aber höchstens n - 1-mal. Das lohnt sich, wenn Tauschen teuer ist, etwa bei großen Datensätzen, die tatsächlich kopiert werden müssen.

Insertionsort: einordnen wie Spielkarten

Insertionsort (Sortieren durch Einfügen, insertion sort) arbeitet so, wie viele Menschen Spielkarten auf der Hand sortieren: Der vordere Teil ist bereits sortiert. Das nächste Element wird herausgenommen, alle größeren Elemente des sortierten Teils rücken eine Position nach hinten, und das Element wird in die frei gewordene Lücke eingesetzt.

Insertionsort für [7, 3, 9, 2, 5]
i	herausgenommen	Array danach (sortierter Teil fett)
1	3	3, 7, 9, 2, 5
2	9	3, 7, 9, 2, 5
3	2	2, 3, 7, 9, 5
4	5	2, 3, 5, 7, 9

insertionsort(int werte[]) {
    for (int i = 1 … length(werte)-1) {
        int neu = werte[i]
        int j = i - 1
        while (j >= 0 && werte[j] > neu) {
            werte[j + 1] = werte[j]          // größeres Element rückt nach hinten
            j = j - 1
        }
        werte[j + 1] = neu                   // Lücke füllen
    }
}

PROCEDURE insertionsort(werte: array of integer)
    for i := 1 to length(werte) - 1 do
        neu: integer := werte[i]
        j: integer := i - 1
        while (j >= 0 AND werte[j] > neu) do
            werte[j + 1] := werte[j]          // größeres Element rückt nach hinten
            j := j - 1
        end while
        werte[j + 1] := neu                   // Lücke füllen
    end for
END insertionsort

Prozedur insertionsort(werte: integer[])
    zähle i von 1 bis laenge(werte) - 1
        neu: integer := werte[i]
        j: integer := i - 1
        solange j >= 0 und werte[j] > neu
            werte[j + 1] := werte[j]          // größeres Element rückt nach hinten
            j := j - 1
        Ende solange
        werte[j + 1] := neu                   // Lücke füllen
    Ende zähle
Ende insertionsort

Auch hier ist die Reihenfolge der Teilbedingungen wichtig: Zuerst wird j >= 0 geprüft, erst dann auf werte[j] zugegriffen (Kurzschlussauswertung).

Sortiert einfügen: neue Elemente gleich an die richtige Stelle

Das Prinzip von Insertionsort brauchst Du immer dann, wenn eine Liste schon sortiert ist und ein neues Element hinzukommt – ein Sessionplan, eine Warteliste, eine Ergebnisliste, die beim Durchlaufen der Daten aufgebaut wird. Statt am Ende neu zu sortieren, suchst Du die Einfügeposition und verschiebst die Elemente dahinter um eins nach hinten. Ist das Array nur teilweise gefüllt, merkst Du Dir die Anzahl der belegten Plätze in einer eigenen Variablen:

// liste ist in den Positionen 0 … anzahl - 1 aufsteigend nach Preis sortiert
int einfuegen(Flug liste[], int anzahl, Flug neu) {
    if (anzahl == length(liste)) {
        return -1                                    // kein Platz mehr
    }
    int pos = 0
    while (pos < anzahl && liste[pos].getPreis() <= neu.getPreis()) {
        pos = pos + 1
    }
    int k = anzahl
    while (k > pos) {                                // von hinten nach vorne verschieben
        liste[k] = liste[k - 1]
        k = k - 1
    }
    liste[pos] = neu
    return anzahl + 1
}

// liste ist in den Positionen 0 … anzahl - 1 aufsteigend nach Preis sortiert
FUNCTION einfuegen(liste: array of Flug, anzahl: integer, neu: Flug) : integer
    if (anzahl = length(liste)) then
        RETURN -1                                    // kein Platz mehr
    end if
    pos: integer := 0
    while (pos < anzahl AND liste[pos].getPreis() <= neu.getPreis()) do
        pos := pos + 1
    end while
    k: integer := anzahl
    while (k > pos) do                               // von hinten nach vorne verschieben
        liste[k] := liste[k - 1]
        k := k - 1
    end while
    liste[pos] := neu
    RETURN anzahl + 1
END einfuegen

// liste ist in den Positionen 0 … anzahl - 1 aufsteigend nach Preis sortiert
Funktion einfuegen(liste: Flug[], anzahl: integer, neu: Flug): integer
    wenn anzahl = laenge(liste) dann
        Rückgabe -1                                  // kein Platz mehr
    Ende wenn
    pos: integer := 0
    solange pos < anzahl und liste[pos].getPreis() <= neu.getPreis()
        pos := pos + 1
    Ende solange
    k: integer := anzahl
    solange k > pos                                  // von hinten nach vorne verschieben
        liste[k] := liste[k - 1]
        k := k - 1
    Ende solange
    liste[pos] := neu
    Rückgabe anzahl + 1
Ende einfuegen

Zwei Details entscheiden darüber, ob das Einfügen korrekt arbeitet:

Verschoben wird von hinten nach vorne. Wer vorne anfängt (liste[pos + 1] := liste[pos]), überschreibt das nächste Element, bevor es verschoben wurde, und kopiert ein einziges Element bis ans Ende.
<= statt < bei der Positionssuche setzt das neue Element hinter alle Elemente mit gleichem Preis. Gleichwertige Elemente bleiben dann in der Reihenfolge ihres Eintreffens (siehe Stabilität).

Wird jedes Element der Eingabe so in eine zunächst leere Ergebnisliste einsortiert, ist das nichts anderes als Insertionsort mit getrennter Ein- und Ausgabe.

Welches Verfahren nehme ich?

Die drei einfachen Sortierverfahren im Vergleich
Merkmal	Bubblesort	Selectionsort	Insertionsort
Idee	benachbarte Elemente tauschen	Extremum suchen und nach vorne tauschen	Element in den sortierten Teil einfügen
Vergleiche (n Elemente, ungünstigster Fall)	n · (n − 1) / 2	immer n · (n − 1) / 2	n · (n − 1) / 2
bereits sortierte Eingabe	n − 1 Vergleiche (mit Abbruch)	n · (n − 1) / 2 Vergleiche	n − 1 Vergleiche
Tauschvorgänge	viele	höchstens n − 1	viele Verschiebungen
stabil	ja (mit `>` bzw. `<`)	nein (in der üblichen Form)	ja (mit `>` in der Bedingung)
in Aufgaben	Standardlösung, leicht fehlerfrei aufzuschreiben	gut, wenn das Extremum-Muster sitzt	ideal für „sortiert einfügen“

Steht in der Aufgabe „Sortieralgorithmus eigener Wahl“, nimm das Verfahren, das Du am sichersten aufschreiben kannst, und nenne es ausdrücklich (z. B. „Bubblesort“), wenn danach gefragt ist. Ist ein Verfahren beschrieben („Vergleich der ersten beiden Elemente, ggf. tauschen …“), setze genau dieses um.

Objekte sortieren

Meist sortierst Du keine Zahlen, sondern Objekte nach einem ihrer Attribute: Flüge nach Preis, Räume nach Belegung, Artikel nach Lagerbestand. An die Stelle des Werts tritt der Getter, getauscht wird das ganze Objekt:

sortiereNachPreis(Flug fluege[]) {
    int n = length(fluege)
    for (int i = 0 … n-2) {
        for (int j = 0 … n-2-i) {
            if (fluege[j].getPreis() > fluege[j + 1].getPreis()) {
                Flug hilf = fluege[j]                // hilf: Flug
                fluege[j] = fluege[j + 1]
                fluege[j + 1] = hilf
            }
        }
    }
}

PROCEDURE sortiereNachPreis(fluege: array of Flug)
    n: integer := length(fluege)
    for i := 0 to n - 2 do
        for j := 0 to n - 2 - i do
            if (fluege[j].getPreis() > fluege[j + 1].getPreis()) then
                hilf: Flug := fluege[j]              // hilf: Flug
                fluege[j] := fluege[j + 1]
                fluege[j + 1] := hilf
            end if
        end for
    end for
END sortiereNachPreis

Prozedur sortiereNachPreis(fluege: Flug[])
    n: integer := laenge(fluege)
    zähle i von 0 bis n - 2
        zähle j von 0 bis n - 2 - i
            wenn fluege[j].getPreis() > fluege[j + 1].getPreis() dann
                hilf: Flug := fluege[j]              // hilf: Flug
                fluege[j] := fluege[j + 1]
                fluege[j + 1] := hilf
            Ende wenn
        Ende zähle
    Ende zähle
Ende sortiereNachPreis

Ein typischer Fehler ist, nur das Attribut zu tauschen (fluege[j].setPreis(…)) – dann stehen die Preise sortiert, gehören aber zu den falschen Flügen.

Häufig ist das Kriterium kein Attribut, sondern ein berechneter Wert, etwa die Fehlmenge eines Artikels (getMindestbestand() - getLagerbestand()) oder der Anteil belegter Plätze. Berechne ihn für beide Seiten des Vergleichs gleich – am übersichtlichsten in zwei Hilfsvariablen vor dem wenn.

Zweidimensionale Arrays sortieren: ganze Zeilen tauschen

Ein zweidimensionales Array, das als Tabelle verwendet wird (jede Zeile ein Datensatz), sortierst Du nach einer Spalte – getauscht werden aber alle Spalten der Zeile. Sonst zerreißt Du die Datensätze.

Oft ist dabei die ursprüngliche Position wichtig. Ein eindimensionales Array, dessen Index eine fachliche Bedeutung hat (Index = Einkommensgruppe, Monat, Raumnummer − 1), verliert diese Information beim Sortieren. Die Lösung: Du legst ein zweidimensionales Array an, schreibst in Spalte 0 den Index und in Spalte 1 den Wert und sortierst die Zeilen.

float[][] sortiereMitIndex(float werte[]) {
    int n = length(werte)
    float [0:n-1, 0:1] tabelle
    for (int i = 0 … n-1) {
        tabelle[i, 0] = i                    // ursprünglicher Index
        tabelle[i, 1] = werte[i]             // Wert
    }
    for (int i = 0 … n-2) {
        for (int j = 0 … n-2-i) {
            if (tabelle[j, 1] > tabelle[j + 1, 1]) {
                for (int s = 0 … 1) {        // jede Spalte der Zeile tauschen
                    float hilf = tabelle[j, s]
                    tabelle[j, s] = tabelle[j + 1, s]
                    tabelle[j + 1, s] = hilf
                }
            }
        }
    }
    return tabelle
}

FUNCTION sortiereMitIndex(werte: array of real) : array of array of real
    n: integer := length(werte)
    tabelle: array [0..n-1, 0..1] of real
    for i := 0 to n - 1 do
        tabelle[i, 0] := i                   // ursprünglicher Index
        tabelle[i, 1] := werte[i]            // Wert
    end for
    for i := 0 to n - 2 do
        for j := 0 to n - 2 - i do
            if (tabelle[j, 1] > tabelle[j + 1, 1]) then
                for s := 0 to 1 do           // jede Spalte der Zeile tauschen
                    hilf: real := tabelle[j, s]
                    tabelle[j, s] := tabelle[j + 1, s]
                    tabelle[j + 1, s] := hilf
                end for
            end if
        end for
    end for
    RETURN tabelle
END sortiereMitIndex

Funktion sortiereMitIndex(werte: double[]): double[][]
    n: integer := laenge(werte)
    tabelle: double[n][2]
    zähle i von 0 bis n - 1
        tabelle[i][0] := i                   // ursprünglicher Index
        tabelle[i][1] := werte[i]            // Wert
    Ende zähle
    zähle i von 0 bis n - 2
        zähle j von 0 bis n - 2 - i
            wenn tabelle[j][1] > tabelle[j + 1][1] dann
                zähle s von 0 bis 1          // jede Spalte der Zeile tauschen
                    hilf: double := tabelle[j][s]
                    tabelle[j][s] := tabelle[j + 1][s]
                    tabelle[j + 1][s] := hilf
                Ende zähle
            Ende wenn
        Ende zähle
    Ende zähle
    Rückgabe tabelle
Ende sortiereMitIndex

Bei zwei Spalten kannst Du statt der inneren Schleife auch zwei Hilfsvariablen verwenden. In vielen Sprachen ist eine Zeile selbst ein Array; dann genügt ein Tausch der Zeilenreferenzen (hilfZeile := tabelle[j]).

Filtern und sortieren in einer Funktion

Typische Aufgaben verlangen beides: Aus einem Array sollen nur bestimmte Datensätze übernommen werden, und das Ergebnis soll sortiert sein. Das Grundgerüst:

Filtern: passende Elemente in ein Ergebnisarray übernehmen.
Sortieren: das Ergebnisarray sortieren (ein Verfahren Deiner Wahl).
Zurückgeben: das Ergebnisarray.

Zuerst zu filtern ist sinnvoll, weil dann weniger Elemente sortiert werden müssen. Gibt es eine Option „alle“ (z. B. Kategorie 0 = unbekannt bzw. alle), steckt sie in der Filterbedingung: (kategorie = 0 oder e.getKategorie() = kategorie).

Für das Ergebnisarray gibt es zwei übliche Wege:

Neues Array mit Zähler: Ein Array fester Länge (so lang wie die Eingabe) und ein Zähler anzahl für die nächste freie Position. Weiß die Aufgabe, dass ein Array „passend lang“ sein soll, zählst Du in einem ersten Durchlauf die Treffer, legst das Array mit dieser Länge an und füllst es im zweiten Durchlauf.
Nicht passende Elemente löschen: Stellt die Aufgabe eine Funktion wie loesche(array, position) bereit, die das Array verkürzt, kannst Du das Eingabearray selbst ausdünnen. Dann ist Vorsicht geboten (siehe nächster Abschnitt).

Sortiertes Einfügen (siehe Insertionsort) verbindet Schritt 1 und 2: Jedes passende Element wird gleich an der richtigen Stelle eingefügt.

Die Falle beim Löschen im Durchlauf

// fehlerhaft
for (int i = 0 … length(treffer)-1) {
    if (treffer[i].getScore() < schwelle) {
        loesche(treffer, i)
    }
}

// fehlerhaft
for i := 0 to length(treffer) - 1 do
    if (treffer[i].getScore() < schwelle) then
        loesche(treffer, i)
    end if
end for

// fehlerhaft
zähle i von 0 bis laenge(treffer) - 1
    wenn treffer[i].getScore() < schwelle dann
        loesche(treffer, i)
    Ende wenn
Ende zähle

Wird treffer[i] gelöscht, rückt das nächste Element auf die Position i nach – und wird übersprungen, weil i trotzdem erhöht wird. Von zwei Treffern unter der Schwelle direkt hintereinander bleibt so der zweite stehen. Außerdem wurde die Obergrenze der Zählschleife vor dem Löschen berechnet; am Ende greift die Schleife auf Positionen zu, die es nicht mehr gibt.

Richtig ist eine Solange-Schleife, die den Index nur dann erhöht, wenn nicht gelöscht wurde – oder ein Durchlauf von hinten nach vorne:

int i = 0
while (i < length(treffer)) {
    if (treffer[i].getScore() < schwelle) {
        loesche(treffer, i)                  // nächstes Element rückt auf Position i
    } else {
        i = i + 1
    }
}

i: integer := 0
while (i < length(treffer)) do
    if (treffer[i].getScore() < schwelle) then
        loesche(treffer, i)                  // nächstes Element rückt auf Position i
    else
        i := i + 1
    end if
end while

i: integer := 0
solange i < laenge(treffer)
    wenn treffer[i].getScore() < schwelle dann
        loesche(treffer, i)                  // nächstes Element rückt auf Position i
    sonst
        i := i + 1
    Ende wenn
Ende solange

Vergleichsfunktionen: das Sortierkriterium austauschbar machen

Das Problem

Bisher steckt das Sortierkriterium fest im Algorithmus: getPreis() und >. Soll dieselbe Liste mal nach Preis, mal nach Datum und mal absteigend sortiert werden, bräuchtest Du für jedes Kriterium einen eigenen, fast gleichen Algorithmus. Die Lösung: Der Vergleich wird in eine eigene Funktion ausgelagert, die dem Sortieralgorithmus als Parameter übergeben wird.

Der Vertrag einer Vergleichsfunktion

Eine Vergleichsfunktion bekommt zwei Objekte desselben Typs und liefert eine ganze Zahl:

Rückgabewerte einer Vergleichsfunktion
Rückgabe	Bedeutung
negativer Wert	`a` gehört vor `b` („a ist kleiner“)
0	`a` und `b` sind gleichwertig
positiver Wert	`a` gehört hinter `b` („a ist größer“)

Das entspricht compareTo und Comparator.compare in Java oder IComparer.Compare in C#. Oft genügen die Werte -1, 0 und 1; erlaubt ist aber jeder negative bzw. positive Wert. Lies die Aufgabe genau: Manchmal ist der Vertrag aus Sicht der Sortierung formuliert („liefert einen Wert > 0, wenn b vor a sortiert werden soll“) – inhaltlich ist das dasselbe.

int vergleicheGewicht(Paket a, Paket b) {
    if (a.getGewicht() < b.getGewicht()) {
        return -1
    } else if (a.getGewicht() > b.getGewicht()) {
        return 1
    } else {
        return 0
    }
}

FUNCTION vergleicheGewicht(a: Paket, b: Paket) : integer
    if (a.getGewicht() < b.getGewicht()) then
        RETURN -1
    else if (a.getGewicht() > b.getGewicht()) then
        RETURN 1
    else
        RETURN 0
    end if
END vergleicheGewicht

Funktion vergleicheGewicht(a: Paket, b: Paket): integer
    wenn a.getGewicht() < b.getGewicht() dann
        Rückgabe -1
    sonst wenn a.getGewicht() > b.getGewicht() dann
        Rückgabe 1
    sonst
        Rückgabe 0
    Ende wenn
Ende vergleicheGewicht

Die Falle mit Kommazahlen

Bei ganzzahligen Attributen ist Rückgabe a.getMenge() - b.getMenge() eine kurze, korrekte Lösung. Bei Kommazahlen (Gehalt, Preis, Gewicht) ist die Differenz aber selbst eine Kommazahl, der Rückgabetyp jedoch integer: Das ist ein Typkonflikt. Wandelst Du die Differenz in eine ganze Zahl um, wird abgeschnitten – zwei Pakete mit 2,4 kg und 2,9 kg ergeben (int)(-0,5) = 0 und gelten als gleich schwer. Vergleiche Kommazahlen deshalb immer mit < und > (in Java auch Double.compare(a, b)).

Eine verwandte Falle bei ganzen Zahlen: Liegen die Werte nahe an der Grenze des Datentyps, kann die Differenz überlaufen. Bei Mengen, Belegungen oder Punkten spielt das keine Rolle, bei beliebigen Kennzahlen ist der Vergleich mit < und > sicherer.

Die Vergleichsfunktion im Sortieralgorithmus

Im Sortieralgorithmus ersetzt der Aufruf der übergebenen Funktion den festen Vergleich. Ist ihr Ergebnis positiv, gehört a hinter b – es wird getauscht:

sortiere(Paket werte[], Function<Paket> vergleiche) {
    int n = length(werte)
    for (int i = 0 … n-2) {
        for (int j = 0 … n-2-i) {
            if (vergleiche(werte[j], werte[j + 1]) > 0) {
                Paket hilf = werte[j]
                werte[j] = werte[j + 1]
                werte[j + 1] = hilf
            }
        }
    }
}

PROCEDURE sortiere(werte: array of Paket, vergleiche: Function<Paket>)
    n: integer := length(werte)
    for i := 0 to n - 2 do
        for j := 0 to n - 2 - i do
            if (vergleiche(werte[j], werte[j + 1]) > 0) then
                hilf: Paket := werte[j]
                werte[j] := werte[j + 1]
                werte[j + 1] := hilf
            end if
        end for
    end for
END sortiere

Prozedur sortiere(werte: Paket[], vergleiche: Function<Paket>)
    n: integer := laenge(werte)
    zähle i von 0 bis n - 2
        zähle j von 0 bis n - 2 - i
            wenn vergleiche(werte[j], werte[j + 1]) > 0 dann
                hilf: Paket := werte[j]
                werte[j] := werte[j + 1]
                werte[j + 1] := hilf
            Ende wenn
        Ende zähle
    Ende zähle
Ende sortiere

Arbeitet der Algorithmus nicht mit einem Array, sondern mit einer Liste, die nur get, set und size anbietet, ändert sich nur der Zugriff:

sortiere(List<Paket> liste, Function<Paket> vergleiche) {
    int n = liste.size()
    for (int i = 0 … n-2) {
        for (int j = 0 … n-2-i) {
            if (vergleiche(liste.get(j), liste.get(j + 1)) > 0) {
                Paket hilf = liste.get(j)
                liste.set(j, liste.get(j + 1))
                liste.set(j + 1, hilf)
            }
        }
    }
}

PROCEDURE sortiere(liste: List<Paket>, vergleiche: Function<Paket>)
    n: integer := liste.size()
    for i := 0 to n - 2 do
        for j := 0 to n - 2 - i do
            if (vergleiche(liste.get(j), liste.get(j + 1)) > 0) then
                hilf: Paket := liste.get(j)
                liste.set(j, liste.get(j + 1))
                liste.set(j + 1, hilf)
            end if
        end for
    end for
END sortiere

Prozedur sortiere(liste: List<Paket>, vergleiche: Function<Paket>)
    n: integer := liste.size()
    zähle i von 0 bis n - 2
        zähle j von 0 bis n - 2 - i
            wenn vergleiche(liste.get(j), liste.get(j + 1)) > 0 dann
                hilf: Paket := liste.get(j)
                liste.set(j, liste.get(j + 1))
                liste.set(j + 1, hilf)
            Ende wenn
        Ende zähle
    Ende zähle
Ende sortiere

Der Aufruf lautet dann z. B. sortiere(sendungen, vergleicheGewicht). Wie man solche Algorithmen mit einem Typparameter T für beliebige Klassen schreibt (List<T>, Function<T>), behandelt der Artikel Generische Klassen und Typparameter.

Absteigend sortieren, ohne den Algorithmus zu ändern

Die Sortierrichtung steckt jetzt allein in der Vergleichsfunktion. Für eine absteigende Sortierung schreibst Du eine zweite Vergleichsfunktion, die die Argumente vertauscht oder das Ergebnis umkehrt:

int vergleicheGewichtAbsteigend(Paket a, Paket b) {
    return vergleicheGewicht(b, a)          // oder: -vergleicheGewicht(a, b)
}

FUNCTION vergleicheGewichtAbsteigend(a: Paket, b: Paket) : integer
    RETURN vergleicheGewicht(b, a)          // oder: -vergleicheGewicht(a, b)
END vergleicheGewichtAbsteigend

Funktion vergleicheGewichtAbsteigend(a: Paket, b: Paket): integer
    Rückgabe vergleicheGewicht(b, a)        // oder: -vergleicheGewicht(a, b)
Ende vergleicheGewichtAbsteigend

Mehrstufige Vergleiche

Sollen Elemente zuerst nach einem Kriterium und bei Gleichstand nach einem zweiten sortiert werden (Kategorie alphabetisch, darin Preis absteigend), entscheidet das zweite Kriterium nur, wenn das erste 0 liefert:

int vergleicheKategorieDannPreis(Artikel a, Artikel b) {
    int ergebnis = vergleicheText(a.getKategorie(), b.getKategorie())
    if (ergebnis != 0) {
        return ergebnis                     // Kategorie entscheidet
    }
    return vergleichePreis(b, a)            // gleiche Kategorie: teurer zuerst
}

FUNCTION vergleicheKategorieDannPreis(a: Artikel, b: Artikel) : integer
    ergebnis: integer := vergleicheText(a.getKategorie(), b.getKategorie())
    if (ergebnis <> 0) then
        RETURN ergebnis                     // Kategorie entscheidet
    end if
    RETURN vergleichePreis(b, a)            // gleiche Kategorie: teurer zuerst
END vergleicheKategorieDannPreis

Funktion vergleicheKategorieDannPreis(a: Artikel, b: Artikel): integer
    ergebnis: integer := vergleicheText(a.getKategorie(), b.getKategorie())
    wenn ergebnis <> 0 dann
        Rückgabe ergebnis                   // Kategorie entscheidet
    Ende wenn
    Rückgabe vergleichePreis(b, a)          // gleiche Kategorie: teurer zuerst
Ende vergleicheKategorieDannPreis

Zeichenketten werden dabei nicht mit < verglichen, sondern mit einer vorgegebenen Funktion (compareTo in Java, hier vergleicheText), die denselben Vertrag erfüllt.

Vergleichsfunktionen in echten Programmiersprachen

In Java ist eine Vergleichsfunktion ein Objekt vom Typ Comparator<T>; Lambda-Ausdrücke und Methodenreferenzen machen sie kurz:

List<Artikel> sortiment = shop.getArtikel();
sortiment.sort(Comparator.comparingDouble(Artikel::getPreis));             // aufsteigend
sortiment.sort(Comparator.comparingDouble(Artikel::getPreis).reversed());  // absteigend
sortiment.sort(Comparator.comparing(Artikel::getKategorie)
        .thenComparing(Comparator.comparingDouble(Artikel::getPreis).reversed()));

C# nutzt Comparison<T>-Delegaten (liste.Sort((a, b) => a.Preis.CompareTo(b.Preis))), Python eine Schlüsselfunktion (sorted(artikel, key=lambda a: a.preis, reverse=True)). Das Prinzip ist überall dasselbe: Der Sortieralgorithmus ist fertig, Du lieferst nur das Kriterium.

Stabilität: Was passiert bei Gleichstand?

Ein Sortierverfahren heißt stabil (stable), wenn Elemente mit gleichem Sortierschlüssel nach dem Sortieren in derselben Reihenfolge stehen wie vorher. Das ist nützlich, wenn die Daten schon nach einem anderen Kriterium vorsortiert waren: Eine nach Artikelnummer geordnete Liste, stabil nach Fehlmenge sortiert, ist bei gleicher Fehlmenge weiterhin nach Artikelnummer geordnet.

Bubblesort ist stabil, solange nur bei echtem Größer getauscht wird (> bzw. vergleiche(…) > 0). Mit >= werden gleiche Nachbarn getauscht – das Verfahren sortiert immer noch, ist aber nicht mehr stabil und tauscht unnötig.
Insertionsort ist stabil, wenn ein Element nur an größeren Elementen vorbeirückt (werte[j] > neu).
Selectionsort ist in der üblichen Form nicht stabil: Der Tausch kann ein Element über ein gleichwertiges hinweg nach hinten befördern. Aus [5a, 5b, 3] wird im ersten Schritt [3, 5b, 5a].

Brauchst Du eine feste Reihenfolge bei Gleichstand, ist eine mehrstufige Vergleichsfunktion die sichere Lösung – sie funktioniert unabhängig vom Verfahren.

Laufzeit: Warum Bubblesort im Alltag selten ist

Bubblesort vergleicht im ungünstigsten Fall im ersten Durchlauf n - 1 Paare, im zweiten n - 2 und so weiter:

(n-1) + (n-2) + \ldots + 1 = \frac{n \cdot (n-1)}{2}

Bei 1.000 Elementen sind das 499.500 Vergleiche, bei 10.000 Elementen schon fast 50 Millionen. Die Zahl der Vergleiche wächst mit dem Quadrat der Elementzahl; man spricht von quadratischer Laufzeit oder O(n^2). Selectionsort und Insertionsort liegen in derselben Klasse.

Schnellere Verfahren wie Mergesort oder Quicksort kommen mit ungefähr n \cdot \log_2 n Vergleichen aus – bei 10.000 Elementen rund 133.000 statt 50 Millionen. Die Sortierfunktionen der Standardbibliotheken nutzen solche Verfahren oder Mischformen: Java sortiert Objekte mit einem stabilen Mergesort-Abkömmling (TimSort), Python ebenfalls stabil, C# mit Array.Sort nicht stabil (Introsort), mit LINQ OrderBy dagegen stabil. Mehr zur Abschätzung von Laufzeiten findest Du im Artikel Laufzeitkomplexität von Algorithmen.

Für die Praxis heißt das:

Daten aus der Datenbank sortierst Du mit ORDER BY in der Abfrage. Die Datenbank kann Indizes nutzen und liefert nur, was gebraucht wird.
Daten im Programm sortierst Du mit der Bibliotheksfunktion und einer Vergleichsfunktion.
Einen eigenen Sortieralgorithmus schreibst Du, wenn die Aufgabe es verlangt, auf sehr einfachen Systemen (z. B. Mikrocontrollern) oder um das Prinzip zu verstehen.

Rund ums Sortieren: Werte prüfen, einfügen und zerlegen

Programme, die Listen verwalten – etwa eine Warteschlange von Störungsmeldungen in der Systemverwaltung –, sortieren nicht nur. Bevor ein Wert in ein Array kommt, wird er geprüft; er wird in ein freies Feld geschrieben, und manchmal muss eine einzelne Stelle einer Kennzahl herausgelöst werden, um danach zu sortieren oder zu filtern. Diese kleinen Bausteine kommen in Aufgaben oft zusammen mit einem Bubblesort vor.

Einen Wertebereich mit UND prüfen

Eine Ticketnummer soll sechsstellig sein und nur die Ziffern 1 bis 9 enthalten. Die kleinste erlaubte Zahl ist dann 111111, die größte 999999. Beide Grenzen müssen gleichzeitig eingehalten werden, deshalb werden die Teilbedingungen mit UND verknüpft:

if ((nummer >= 111111) && (nummer <= 999999)) {
    // Nummer darf eingefügt werden
}

if ((nummer >= 111111) AND (nummer <= 999999)) then
    // Nummer darf eingefügt werden
end if

wenn (nummer >= 111111) und (nummer <= 999999) dann
    // Nummer darf eingefügt werden
Ende wenn

In Java- oder C#-naher Schreibweise: if ((nummer >= 111111) && (nummer <= 999999)) { … }. Ein ODER (||) wäre hier falsch: Jede Zahl ist größer als 111111 oder kleiner als 999999 – die Bedingung wäre immer wahr. Beachte: Die Bereichsprüfung stellt nur sicher, dass die Zahl zwischen den Grenzen liegt; ob wirklich keine 0 enthalten ist (z. B. 120111), prüfst Du Stelle für Stelle mit DIV und MOD (siehe unten).

In das erste freie Feld einfügen

Ein Array mit fester Größe kennzeichnet freie Felder oft mit 0. Ein neuer Wert soll in das freie Feld mit dem kleinsten Index. Du läufst das Array durch, bis Du ein freies Feld findest, und hörst dann auf – sonst würde der Wert in alle freien Felder geschrieben.

boolean einfuegen(int liste[], int neu) {
    int i = 0
    while (i < length(liste) && liste[i] != 0) {
        i = i + 1
    }
    if (i < length(liste)) {
        liste[i] = neu
        return true
    } else {
        return false               // Array ist voll
    }
}

FUNCTION einfuegen(liste: array of integer, neu: integer) : boolean
    i: integer := 0
    while (i < length(liste) AND liste[i] <> 0) do
        i := i + 1
    end while
    if (i < length(liste)) then
        liste[i] := neu
        RETURN true
    else
        RETURN false               // Array ist voll
    end if
END einfuegen

Funktion einfuegen(liste: integer[], neu: integer): boolean
    i: integer := 0
    solange i < laenge(liste) und liste[i] <> 0
        i := i + 1
    Ende solange
    wenn i < laenge(liste) dann
        liste[i] := neu
        Rückgabe true
    sonst
        Rückgabe false             // Array ist voll
    Ende wenn
Ende einfuegen

Zwei Fehler sind hier typisch:

Grenze mit <=: for (int i = 0; i <= anzahl; i++) mit anzahl = 20 greift im letzten Durchlauf auf liste[20] zu – das Array hat aber nur die Indizes 0 bis 19. Solange ein freies Feld gefunden wird, fällt das nicht auf; ist das Array voll, bricht das Programm mit einer IndexOutOfRangeException (C#) bzw. ArrayIndexOutOfBoundsException (Java) ab. Richtig ist i < anzahl (oder i <= anzahl - 1).
Abbruch durch Manipulieren der Zählvariablen: i = 99; innerhalb einer Zählschleife beendet die Schleife zwar, ist aber schwer lesbar und bricht, sobald jemand das Array vergrößert. Besser ist eine Solange-Schleife mit Abbruchbedingung wie oben oder break in der Zählschleife.

Und noch ein Unterschied zum sortierten Einfügen aus dem Abschnitt zu Insertionsort: Dort ist das Array lückenlos gefüllt und sortiert; hier gibt es Lücken, und die Reihenfolge spielt keine Rolle. Soll die Liste danach sortiert sein, sortierst Du anschließend – die freien Felder (0) wandern bei aufsteigender Sortierung nach vorne. Willst Du sie hinten haben, behandelt die Vergleichsfunktion 0 als „größer als alles“.

Eine Stelle mit DIV und MOD herauslösen

Aus einer Ticketnummer wie 482731 sollen die Teile gelesen werden: die ersten beiden Stellen (Standort 48), die dritte Stelle (Priorität 2) und die letzten drei (laufende Nummer 731). Dafür brauchst Du keine Zeichenketten, sondern zwei Rechenoperationen:

a div b – Ganzzahldivision, der Rest wird abgeschnitten (123 div 10 = 12). In Java und C# ist das /, wenn beide Werte ganzzahlig sind.
a mod b – Rest der Division (Modulo, 123 mod 10 = 3). In Java und C# ist das %.

Die Regel: Mit DIV schneidest Du rechts Stellen ab, mit MOD behältst Du die rechten Stellen.

Teile einer sechsstelligen Nummer mit DIV und MOD bestimmen
Gesucht	Rechnung	Ergebnis für 482731
ersten zwei Stellen (Standort)	`nummer div 10000`	48
dritte Stelle (Priorität)	`(nummer div 1000) mod 10`	482 mod 10 = 2
letzte drei Stellen (laufende Nummer)	`nummer mod 1000`	731

So kannst Du anschließend Tickets nach Priorität sortieren: Die Vergleichsfunktion vergleicht (a div 1000) mod 10 mit (b div 1000) mod 10. Wie Du mit derselben Technik Prüfziffern berechnest, zeigt der Artikel Zeichenketten und Prüfziffern.

Werte für den nächsten Durchlauf übernehmen

Überwachungsskripte laufen in einer Endlosschleife: Sie lesen einen Zählerstand, warten, lesen erneut und berechnen die Differenz. Damit im nächsten Durchlauf wieder die richtige Differenz entsteht, wird der Endwert zum neuen Startwert:

int start = leseZaehler()
repeat {
    warte(1 s)
    int ende = leseZaehler()
    zeige(ende - start)
    start = ende                  // Endwert wird Startwert für den nächsten Durchlauf
} until (beendet)

start: integer := leseZaehler()
repeat
    warte(1 s)
    ende: integer := leseZaehler()
    zeige(ende - start)
    start := ende                 // Endwert wird Startwert für den nächsten Durchlauf
until (beendet)

start: integer := leseZaehler()
wiederhole
    warte(1 s)
    ende: integer := leseZaehler()
    zeige(ende - start)
    start := ende                 // Endwert wird Startwert für den nächsten Durchlauf
solange nicht beendet

Das ist dasselbe Prinzip wie beim Tausch mit Hilfsvariable: Die Reihenfolge der Zuweisungen entscheidet. Würdest Du start := ende vor der Berechnung schreiben, wäre die Differenz immer 0.

Typische Fehler

Indexgrenze überschritten: innere Schleife bis n - 1 mit Zugriff auf j + 1.
Tausch ohne Hilfsvariable: Beide Felder enthalten danach denselben Wert.
Nur einen Durchlauf programmiert: Danach steht nur das größte Element sicher am Ende.
Falsche Richtung: > statt < – aufsteigend statt absteigend. Lies die Aufgabe („nach Score absteigend“) und prüfe mit einem Beispiel.
Nur das Attribut oder nur eine Spalte getauscht: Datensätze werden auseinandergerissen.
Index als Information verloren: Ein Array, dessen Index etwas bedeutet, wird sortiert, ohne den Index mitzuführen.
Löschen in der Zählschleife: Elemente werden übersprungen, die Obergrenze stimmt nicht mehr.
Vergleichsfunktion mit Kommadifferenz: Rückgabe a.getPreis() - b.getPreis() als integer.
Vergleichsfunktion nicht benutzt: Im Sortieralgorithmus steht weiter getPreis(), obwohl eine Funktion übergeben wurde.
Beim sortierten Einfügen von vorne verschoben: Ein Element wird bis ans Ende kopiert.
Zählschleife mit <= bis zur Länge: i <= anzahl greift auf ein Feld hinter dem Array zu, sobald kein früherer Abbruch greift.
Bereichsprüfung mit ODER: (x >= min) oder (x <= max) ist immer wahr – beide Grenzen gehören mit UND verknüpft.

Schritt für Schritt zur Lösung

Vorgaben klären: Signatur, Rückgabetyp, vorhandene Funktionen (Getter, laenge, loesche, Vergleichsfunktion), Sortierkriterium und -richtung.
Verfahren festlegen und nennen: Bubblesort, wenn nichts vorgegeben ist; ein beschriebenes Verfahren genau umsetzen.
Erst filtern, dann sortieren (oder sortiert einfügen).
Schleifen schreiben: äußere Schleife n - 1 Durchläufe, innere bis n - 2 - i, Zugriff auf j und j + 1.
Vergleich formulieren: Getter oder Vergleichsfunktion, Operator passend zur Richtung.
Tausch mit Hilfsvariable – ganze Objekte bzw. ganze Zeilen.
Schreibtischtest mit dem Beispiel der Aufgabe: Stimmt das Ergebnis mit der Beispielausgabe überein?

In Aufgaben wird meist nach Teilschritten bewertet: Schleifenköpfe, Vergleich, Tausch, Rückgabe. Ein klar gegliederter Bubblesort mit einem kleinen Fehler bei der Grenze ist deshalb schon weitgehend richtig.

Leitfragen

Wie arbeitet Bubblesort, und warum braucht er bei n Elementen höchstens n − 1 Durchläufe?

Bubblesort vergleicht beim Durchlaufen jeweils zwei benachbarte Elemente und tauscht sie, wenn sie in der falschen Reihenfolge stehen; nach jedem Durchlauf ist das größte noch unsortierte Element hinten angekommen. Nach n − 1 Durchläufen stehen die n − 1 größten Elemente an ihrem Platz, damit ist auch das kleinste richtig einsortiert – siehe Abschnitt „Die Idee“ und Abschnitt „Der Algorithmus“.

Warum darf die innere Schleife von Bubblesort nur bis n - 2 - i laufen, und wie sieht dieselbe Grenze in Java-Schreibweise aus?

Die innere Schleife greift auf werte[j + 1] zu, deshalb darf j höchstens n - 2 sein, sonst greift der Algorithmus hinter das Array-Ende (in Java eine ArrayIndexOutOfBoundsException); das - i spart die bereits sortierten Elemente hinten aus. In Java-Schreibweise mit ausgeschlossener Obergrenze lautet dieselbe Grenze j < werte.length - 1 - i – siehe Abschnitt „Die Schleifengrenzen – die häufigste Fehlerquelle“.

Wie tauschst Du zwei Elemente, zwei Objekte oder zwei Zeilen eines zweidimensionalen Arrays, ohne Daten zu verlieren?

Du tauschst mit einer Hilfsvariablen desselben Typs (Ringtausch): hilf := werte[j], werte[j] := werte[j + 1], werte[j + 1] := hilf. Bei Objekten ist hilf eine Objektvariable und Du tauschst das ganze Objekt, nicht nur das Attribut; bei einem zweidimensionalen Array tauschst Du jede Spalte der Zeile einzeln oder die ganze Zeilenreferenz – siehe Abschnitt „Das Werkzeug aller Verfahren: vergleichen und tauschen“ und Abschnitt „Zweidimensionale Arrays sortieren: ganze Zeilen tauschen“.

Was musst Du ändern, um absteigend statt aufsteigend zu sortieren – im festen Algorithmus und mit einer Vergleichsfunktion?

Im festen Algorithmus änderst Du nur den Vergleichsoperator: > sortiert aufsteigend, < absteigend (bei Selectionsort suchst Du das Maximum statt des Minimums). Mit einer Vergleichsfunktion bleibt der Algorithmus unverändert; Du schreibst eine zweite Vergleichsfunktion, die die Argumente vertauscht oder das Ergebnis umkehrt, z. B. vergleicheGewicht(b, a) – siehe Abschnitt „Das Werkzeug aller Verfahren: vergleichen und tauschen“ und Abschnitt „Absteigend sortieren, ohne den Algorithmus zu ändern“.

Wie unterscheiden sich Bubblesort, Selectionsort und Insertionsort, und welches Verfahren eignet sich für das Einfügen in eine bereits sortierte Liste?

Bubblesort tauscht benachbarte Elemente, Selectionsort sucht das Extremum im unsortierten Teil und tauscht es nach vorne (höchstens n − 1 Tauschvorgänge, nicht stabil), Insertionsort fügt das nächste Element in den sortierten Teil ein. Für das Einfügen in eine bereits sortierte Liste eignet sich das Prinzip von Insertionsort: Einfügeposition suchen, die Elemente dahinter von hinten nach vorne um eins verschieben und das neue Element einsetzen – siehe Abschnitt „Welches Verfahren nehme ich?“ und Abschnitt „Sortiert einfügen: neue Elemente gleich an die richtige Stelle“.

Warum werden beim Löschen innerhalb einer Zählschleife Elemente übersprungen, und wie vermeidest Du das?

Wird treffer[i] gelöscht, rückt das nächste Element auf Position i nach und wird übersprungen, weil die Zählschleife i trotzdem erhöht; außerdem stimmt die vorher berechnete Obergrenze nicht mehr. Du vermeidest das mit einer Solange-Schleife, die den Index nur erhöht, wenn nicht gelöscht wurde, oder mit einem Durchlauf von hinten nach vorne – siehe Abschnitt „Die Falle beim Löschen im Durchlauf“.

Welche Werte liefert eine Vergleichsfunktion, und warum ist die Differenz zweier Kommazahlen als Rückgabe ungeeignet?

Eine Vergleichsfunktion liefert einen negativen Wert, wenn a vor b gehört, 0 bei Gleichwertigkeit und einen positiven Wert, wenn a hinter b gehört. Die Differenz zweier Kommazahlen ist selbst eine Kommazahl und passt nicht zum Rückgabetyp integer; beim Umwandeln wird abgeschnitten, sodass z. B. 2,4 kg und 2,9 kg als gleich schwer gelten – deshalb vergleichst Du Kommazahlen mit < und > – siehe Abschnitt „Der Vertrag einer Vergleichsfunktion“ und Abschnitt „Die Falle mit Kommazahlen“.

Was bedeutet Stabilität, und wann sortierst Du besser mit ORDER BY oder einer Bibliotheksfunktion?

Ein Sortierverfahren ist stabil, wenn Elemente mit gleichem Sortierschlüssel danach in derselben Reihenfolge stehen wie vorher; Bubblesort (mit echtem >) und Insertionsort sind stabil, Selectionsort in der üblichen Form nicht. Daten aus der Datenbank sortierst Du mit ORDER BY, Daten im Programm mit der Bibliotheksfunktion und einer Vergleichsfunktion, weil die einfachen Verfahren quadratische Laufzeit O(n^2) haben; einen eigenen Algorithmus schreibst Du nur, wenn die Aufgabe es verlangt – siehe Abschnitt „Stabilität: Was passiert bei Gleichstand?“ und Abschnitt „Laufzeit: Warum Bubblesort im Alltag selten ist“.

Wie prüfst Du einen Wertebereich, fügst einen Wert in das erste freie Feld ein und ermittelst eine einzelne Stelle einer Zahl?

Den Bereich prüfst Du mit zwei Teilbedingungen, die mit UND (&&) verknüpft sind, z. B. (x >= 111111) und (x <= 999999). Zum Einfügen läufst Du mit einer Solange-Schleife bis zum ersten freien Feld (z. B. Wert 0), solange der Index kleiner als die Länge ist, und schreibst den Wert nur dort hinein; mit <= bis zur Länge greifst Du bei vollem Array hinter das Array-Ende. Eine Stelle löst Du mit DIV (rechts abschneiden) und MOD (rechte Stellen behalten), z. B. dritte Stelle von 482731: (482731 div 1000) mod 10 = 2 – siehe Abschnitt „Rund ums Sortieren: Werte prüfen, einfügen und zerlegen“.

Links und weitere Informationen

Übungsaufgaben zu Sortieralgorithmen und Vergleichsfunktionen
Prozedurale Algorithmen mit Arrays: suchen, zählen, Extremwerte und Gruppenwechsel
Objektorientierte Algorithmen: Methoden über Objektlisten
Algorithmen mit Pseudocode dokumentieren
Übersicht der Programmentwurfsmethoden (Pseudocode, Struktogramm, PAP, Aktivitätsdiagramm)
Laufzeitkomplexität von Algorithmen
Zeichenketten und Prüfziffern
Zyklomatische Komplexität am Beispiel Bubblesort
als Nachschlagewerk: Java-API: Comparator und Java-API: List.sort
als Nachschlagewerk: DIN 66261:1985-11 „Informationsverarbeitung; Sinnbilder für Struktogramme nach Nassi-Shneiderman“
zur Vertiefung: Sortierverfahren als Animation (VisuAlgo)

Hinweis zur Nachnutzung als Open Educational Resource (OER)

Dieser Artikel und seine Texte, Bilder, Grafiken, Code und sonstiger Inhalt sind - sofern nicht anders angegeben - lizenziert unter CC BY 4.0. Nennung gemäß TULLU-Regel bitte wie folgt: “Sortieralgorithmen und Vergleichsfunktionen: Bubblesort, Selectionsort, Insertionsort und eigene Sortierkriterien” von oer-informatik.de (H. Stein), Lizenz: CC BY 4.0. Der Artikel wurde unter https://oer-informatik.de/sortieralgorithmen veröffentlicht, die Quelltexte sind in weiterverarbeitbarer Form verfügbar im Repository unter https://gitlab.com/oer-informatik/algorithmik/algorithmen. Erstellt mit KI-Assistenz; von mir umfassend redaktionell überarbeitet, geprüft und freigegeben. Stand: 27.10.2026.

[Kommentare zum Artikel lesen, schreiben] / [Artikel teilen] / [gitlab-Issue zum Artikel schreiben]

Sortieralgorithmen und Vergleichsfunktionen: Bubblesort, Selectionsort, Insertionsort und eigene Sortierkriterien