Q1 / Suchen und Sortieren

Einfaches Sortieren

Lösung geprüft

Die Aufgabe der heutigen Stunde ist das einfache Sortieren! Fünf Teilaufgaben rund um Selection Sort, Insertion Sort und Bubble Sort. Der Großteil davon ist Handarbeit – Arrays Schritt für Schritt aufschreiben. Das nervt beim Machen, ist aber genau das, was in der Klausur verlangt wird.

Aufgabe 1 – Sortierkriterien

Nach Titel (alphabetisch aufsteigend): Focus, Spiegel, Stern.
Nach Auflage (aufsteigend): Focus (252 035), Stern (369 547), Spiegel (649 235).

Was eine strenge schwache Ordnung ist

Klingt komplizierter als es ist. Ein Sortierkriterium taugt nur dann zum Sortieren, wenn es drei Eigenschaften hat:

Für die Auflage gilt genau dasselbe, nur mit Zahlen statt Buchstaben. Deshalb kann man nach beiden Kriterien sortieren.

„Schwach" heißt dabei: es darf Elemente geben, die gleichwertig sind – zwei Magazine mit derselben Auflage wären weder kleiner noch größer. Das Verfahren muss damit klarkommen und darf sich nicht aufhängen. Hier kommt der Fall nicht vor, alle drei Werte sind verschieden.

Ein Gegenbeispiel macht es klarer: „ist interessanter als" wäre kein gültiges Sortierkriterium. Es ist nicht transitiv, weil es von der Person abhängt, und man kann es nicht eindeutig entscheiden. Damit kann kein Sortieralgorithmus etwas anfangen.

Aufgabe 2 – Die Zahlenreihe 8, 3, 1, 7

Schon an diesem winzigen Beispiel sieht man den Charakter der drei Verfahren: Selection sucht das Minimum und tauscht einmal pro Durchlauf. Insertion baut vorne einen sortierten Bereich auf. Bubble tauscht immer nur Nachbarn und schiebt das Größte nach hinten.

Aufgabe 3 – Alle drei auf 6, 3, 8, 11, 12, 4, 2, 1

Selection Sort

Suche das kleinste Element im unsortierten Rest und tausche es an den Anfang dieses Rests. Der Strich zeigt, wo der sortierte Teil endet.

Start:        6  3  8 11 12  4  2  1
i=0: min=1     1 | 3  8 11 12  4  2  6      (getauscht: 6 und 1)
i=1: min=2     1  2 | 8 11 12  4  3  6      (getauscht: 3 und 2)
i=2: min=3     1  2  3 | 11 12  4  8  6     (getauscht: 8 und 3)
i=3: min=4     1  2  3  4 | 12 11  8  6     (getauscht: 11 und 4)
i=4: min=6     1  2  3  4  6 | 11  8 12     (getauscht: 12 und 6)
i=5: min=8     1  2  3  4  6  8 | 11 12     (getauscht: 11 und 8)
i=6: min=11    1  2  3  4  6  8 11 | 12     (kein Tausch noetig)
fertig:        1  2  3  4  6  8 11 12

Insertion Sort

Nimm das nächste Element und schiebe es im vorderen, schon sortierten Bereich an die richtige Stelle.

Start:        6 | 3  8 11 12  4  2  1
i=1: merke=3   3  6 | 8 11 12  4  2  1      (6 nach rechts geschoben)
i=2: merke=8   3  6  8 | 11 12  4  2  1     (bleibt, 8 > 6)
i=3: merke=11  3  6  8 11 | 12  4  2  1     (bleibt)
i=4: merke=12  3  6  8 11 12 |  4  2  1     (bleibt)
i=5: merke=4   3  4  6  8 11 12 |  2  1     (12,11,8,6 geschoben)
i=6: merke=2   2  3  4  6  8 11 12 |  1     (alles geschoben)
i=7: merke=1   1  2  3  4  6  8 11 12       (alles geschoben)

Bubble Sort

Vergleiche immer zwei Nachbarn und tausche sie, wenn sie falsch herum stehen. Nach jedem Durchlauf steht das größte Element hinten fest.

Start:         6  3  8 11 12  4  2  1
Durchlauf 1:   3  6  8 11  4  2  1 | 12     (12 ist ganz hinten angekommen)
Durchlauf 2:   3  6  8  4  2  1 | 11 12
Durchlauf 3:   3  6  4  2  1 |  8 11 12
Durchlauf 4:   3  4  2  1 |  6  8 11 12
Durchlauf 5:   3  2  1 |  4  6  8 11 12
Durchlauf 6:   2  1 |  3  4  6  8 11 12
Durchlauf 7:   1 |  2  3  4  6  8 11 12
fertig:        1  2  3  4  6  8 11 12

Bubble Sort braucht hier sieben Durchläufe – und in jedem Durchlauf laufen viele Vergleiche. Es ist das langsamste der drei und wird trotzdem immer als Erstes erklärt, weil man es am leichtesten versteht.

Aufgabe 4 a) – Selection Sort in Java

Das Struktogramm aus der Aufgabe sieht als Ablauf so aus:

flowchart TD
    A["links = 0"] --> B{"links < Länge von a?"}
    B -- nein --> Z["fertig, a ist sortiert"]
    B -- ja --> C["min = links"]
    C --> D["i = links + 1"]
    D --> E{"i < Länge von a?"}
    E -- ja --> F{"a[i] < a[min]?"}
    F -- WAHR --> G["min = i"]
    F -- FALSCH --> H["i = i + 1"]
    G --> H
    H --> E
    E -- nein --> I["vertausche a[min] und a[links]"]
    I --> J["links = links + 1"]
    J --> B

Zwei ineinander geschachtelte Schleifen: die äußere schiebt links Feld für Feld nach rechts, die innere sucht im Rest das Minimum. Getauscht wird erst, wenn die innere Schleife durch ist.

/**
 *
 * Selection Sort, Insertion Sort und Bubble Sort
 *
 * @version 1.0 vom 14.09.2025
 * @meininfokurs.cmrg.site
 */

public class Sortierer {

    private int[] a = {6, 3, 8, 11, 12, 4, 2, 1};

    // Aufgabe 5 b): tauscht zwei Eintraege im Array
    public void vertausche(int[] pArray, int pPos1, int pPos2) {
        int merke = pArray[pPos1];
        pArray[pPos1] = pArray[pPos2];
        pArray[pPos2] = merke;
    }

    // Aufgabe 4 a): Selection Sort, genau nach dem Struktogramm
    public void selectionSort(int[] a) {
        int links = 0;
        int min;

        while (links < a.length) {
            min = links;
            for (int i = links + 1; i < a.length; i++) {
                if (a[i] < a[min]) {
                    min = i;
                }
            }
            vertausche(a, min, links);
            links = links + 1;
        }
    }

    // Insertion Sort - die Vorlage aus Aufgabe 4 b)
    public void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int merke = a[i];
            int j = i;
            while (j > 0 && a[j - 1] > merke) {
                a[j] = a[j - 1];
                j = j - 1;
            }
            a[j] = merke;
        }
    }

    // Bubble Sort
    public void bubbleSort(int[] a) {
        for (int durchlauf = 0; durchlauf < a.length - 1; durchlauf++) {
            for (int i = 0; i < a.length - 1 - durchlauf; i++) {
                if (a[i] > a[i + 1]) {
                    vertausche(a, i, i + 1);
                }
            }
        }
    }

    public void ausgabe(int[] a) {
        String zeile = "";
        for (int i = 0; i < a.length; i++) {
            zeile += a[i] + " ";
        }
        System.out.println(zeile);
    }

    public static void main(String[] args) {
        Sortierer s = new Sortierer();
        int[] zahlen = {6, 3, 8, 11, 12, 4, 2, 1};

        System.out.print("Vorher:  ");
        s.ausgabe(zahlen);

        s.selectionSort(zahlen);

        System.out.print("Nachher: ");
        s.ausgabe(zahlen);
    } // end of main

} // end of class Sortierer

Das Struktogramm gibt eine solange-Schleife mit links vor, keine for-Schleife. Ich habe mich daran gehalten, weil die Aufgabe „Implementieren Sie den Algorithmus" sagt – mit einer for-Schleife wäre es dasselbe, nur eben nicht mehr 1:1 das Struktogramm.

Auffällig ist, dass vertausche hier immer aufgerufen wird, auch wenn min == links ist und das Element mit sich selbst getauscht wird. Das ist harmlos, nur unnötig. Die Fassung in Aufgabe 5 prüft vorher mit if (minpos > i).

Aufgabe 4 b) – Struktogramm zum Insertion Sort

+--------------------------------------------------+
| insertionSort()                                  |
+--------------------------------------------------+
|   for i = 1 to a.length - 1                      |
|  +---------------------------------------------+ |
|  | int merke = a[i]                            | |
|  +---------------------------------------------+ |
|  | int j = i                                   | |
|  +---------------------------------------------+ |
|  |   solange j > 0 UND a[j-1] > merke          | |
|  |  +----------------------------------------+ | |
|  |  | a[j] = a[j-1]                          | | |
|  |  +----------------------------------------+ | |
|  |  | j = j - 1                              | | |
|  |  +----------------------------------------+ | |
|  +---------------------------------------------+ |
|  | a[j] = merke                                | |
|  +---------------------------------------------+ |
+--------------------------------------------------+

Die Struktur eins zu eins aus dem Code: eine Zählschleife außen, darin zwei Zuweisungen, dann eine kopfgesteuerte Schleife, und nach der Schleife noch eine Zuweisung. Wichtig ist, dass a[j] = merke außerhalb der inneren Schleife steht – sonst würde man den gemerkten Wert bei jedem Verschieben wieder ablegen.

Die Bedingung j > 0 UND a[j-1] > merke hat ihre Reihenfolge nicht zufällig. Java prüft von links nach rechts und hört auf, sobald das Ergebnis feststeht. Wäre j > 0 hinten, würde bei j = 0 zuerst a[-1] gelesen – und das gibt eine ArrayIndexOutOfBoundsException.

Aufgabe 5 a) – sortiere() Schritt für Schritt

Die Methode sortiere(int[] a) ist ein Selection Sort mit zwei verschachtelten for-Schleifen. Auf dem Array 8, 15, 3, 12, 9, 7 passiert Folgendes:

Bei i = 2 sieht man, wofür das if (minpos > i) gut ist: die 8 steht schon richtig, minpos bleibt bei 2, und der Tausch wird übersprungen. Ohne die Abfrage würde das Element sinnlos mit sich selbst getauscht.

Aufgabe 5 b) – vertausche auf Papier

public void vertausche(int[] pArray, int pPos1, int pPos2) {
    int merke = pArray[pPos1];
    pArray[pPos1] = pArray[pPos2];
    pArray[pPos2] = merke;
}

Drei Zeilen, und die Hilfsvariable merke ist der ganze Trick. Ohne sie geht es nicht:

pArray[pPos1] = pArray[pPos2];   // der alte Wert von pPos1 ist jetzt weg
pArray[pPos2] = pArray[pPos1];   // schreibt denselben Wert nochmal zurueck

Danach stehen an beiden Stellen derselbe Wert und der andere ist unwiderruflich überschrieben. Man braucht also erst einen Zwischenspeicher, bevor man die erste Stelle überschreibt. Das ist derselbe Gedanke wie beim Getränkeglas: um zwei Gläser zu tauschen, braucht man ein drittes leeres.

Und noch etwas Wichtiges: die Methode bekommt das Array als Parameter und verändert es trotzdem dauerhaft. Bei Arrays wird nämlich nicht der Inhalt kopiert, sondern nur die Adresse übergeben – die Methode arbeitet also auf demselben Array wie der Aufrufer. Bei einem einfachen int wäre das anders, da bekäme die Methode eine Kopie.

Die drei Verfahren im Vergleich

Alle drei sind O(n²) und damit für große Datenmengen ungeeignet. Bei 10 000 Elementen sind das 100 Millionen Vergleiche. Deshalb kommt später Quicksort – der schafft dasselbe in O(n · log n).