Sortieren: iterativ und rekursiv

Lösung geprüft

Die Aufgabe der heutigen Stunde ist Sortieren – iterativ und rekursiv! Erst Sortieren durch Auswählen auf einer Liste, dann Quicksort. Quicksort ist der erste Algorithmus, der nicht mehr O(n²) ist, und das merkt man sofort an den Zahlen.

Die Aufgabenstellung lautet

1 Eine Teilnehmerliste soll nach Nachnamen sortiert werden. Bei gleichen Nachnamen soll der Vorname als weiteres Sortierkriterium berücksichtigt werden.

2 Das Sortieren durch Auswählen arbeitet ähnlich wie das Sortieren durch Einfügen, jedoch wird hier jeweils das beste Element aus der unsortierten Liste entnommen und an die sortierte Liste angehängt. a) Führen Sie den Algorithmus für die gegebene Zahlenliste durch und notieren Sie nach jedem Schritt den Inhalt der beiden Teillisten. b) Rechnerarbeit: Implementieren Sie den Algorithmus in Java. c) Beurteilen Sie die Effizienz des Sortierens durch Auswählen und vergleichen Sie mit dem Sortieren durch Einfügen.

3 Der Quicksortalgorithmus soll auf unterschiedliche Weise veranschaulicht werden. a) Veranschaulichen Sie die Arbeitsweise des Quicksortalgorithmus im Kurs. b) Führen Sie den Quicksortalgorithmus mit den Zahlen 1, 2, 18, 6, 13, 5, 29 durch und dokumentieren Sie jeden Schritt. c) Stellen Sie den Quicksortalgorithmus als Struktogramm dar.

4 Rechnerarbeit Der Quicksortalgorithmus nutzt eine Hilfsmethode int laenge(List<ContentType>), die für eine gegebene lineare Liste die Länge bestimmt und zurückgibt. Implementieren Sie die Methode.

5 Die Effizienz des Quicksortalgorithmus hängt im Wesentlichen von der Wahl des Pivotelements ab. Geben Sie eine Zahlenreihe an, für die der Algorithmus den worst case und den best case in seiner Laufzeit erreicht, wenn als Pivotelement immer das erste Element gewählt wird.

Aufgabe 1 – Die Teilnehmerliste

#	Nachname	Vorname
1	Baum	Kevin
2	Dacher	Mathias
3	Keller	Christin
4	Mehler	Katrin
5	Probst	Ralf
6	Strauss	Andreas
7	Strauss	Katja
8	Traugott	Jörg
9	Weiss	Jennifer

Die einzige Stelle, an der das zweite Kriterium greift, sind die beiden Strauss. Nach dem Nachnamen sind sie gleichwertig – erst der Vorname entscheidet, und Andreas kommt vor Katja.

In Java schreibt man so einen Vergleich verschachtelt:

public boolean istKleiner(Person a, Person b) {
    if (!a.getNachname().equals(b.getNachname())) {
        return a.getNachname().compareTo(b.getNachname()) < 0;
    }
    // Nachnamen gleich -> Vorname entscheidet
    return a.getVorname().compareTo(b.getVorname()) < 0;
}

compareTo gibt bei Strings eine negative Zahl zurück, wenn der erste alphabetisch vorne liegt, 0 bei Gleichheit und eine positive Zahl sonst. Damit kann man Texte genauso vergleichen wie Zahlen.

Das ist übrigens genau die „strenge schwache Ordnung" aus der Sortieraufgabe davor: nach dem Nachnamen allein sind die beiden Strauss gleichwertig, also schwach geordnet. Erst das zweite Kriterium macht die Reihenfolge eindeutig.

Aufgabe 2 – Sortieren durch Auswählen

a) Schritt für Schritt mit 7, 13, 2, 36, 203, 8, 12

Schritt   Originalliste (unsortiert)      Hilfsliste (sortiert)
------------------------------------------------------------------
Start     7, 13, 2, 36, 203, 8, 12        (leer)
1         7, 13, 36, 203, 8, 12           2
2         13, 36, 203, 8, 12              2, 7
3         13, 36, 203, 12                 2, 7, 8
4         13, 36, 203                     2, 7, 8, 12
5         36, 203                         2, 7, 8, 12, 13
6         203                             2, 7, 8, 12, 13, 36
7         (leer)                          2, 7, 8, 12, 13, 36, 203

Nach jedem Schritt wandert genau ein Element von links nach rechts – das jeweils kleinste. Die Hilfsliste ist dabei immer sortiert, die Originalliste bleibt bis zum Schluss durcheinander.

b) Der Algorithmus in Java

SortierenDurchAuswaehlen.java

/* meininfokurs.cmrg.site */

/**
 *
 * Sortieren durch Auswaehlen auf einer linearen Liste,
 * genau nach dem Struktogramm
 *
 * @version 1.0 vom 14.09.2025
 * @meininfokurs.cmrg.site
 */

public void sortiereDurchAuswaehlen() {
    List<Integer> hilfsliste = new List<Integer>();

    while (!liste.isEmpty()) {

        // Hilfsvariable mit dem ersten Element vorbelegen
        liste.toFirst();
        int kleinstes = liste.getContent();
        liste.next();

        // den Rest der Liste durchsuchen
        while (liste.hasAccess()) {
            if (liste.getContent() < kleinstes) {
                kleinstes = liste.getContent();
            }
            liste.next();
        }

        // das kleinste Element aus dem Original entfernen ...
        liste.toFirst();
        while (liste.hasAccess() && liste.getContent() != kleinstes) {
            liste.next();
        }
        liste.remove();

        // ... und hinten an die Hilfsliste anhaengen
        hilfsliste.append(kleinstes);
    }

    liste = hilfsliste;
}

Die äußere Schleife läuft, solange die Originalliste nicht leer ist. In jedem Durchlauf wird sie einmal komplett durchsucht, das Minimum entfernt und hinten an die Hilfsliste gehängt. Am Ende wird die Hilfsliste zur neuen Liste – das ist die letzte Zeile des Struktogramms.

Wichtig ist die Vorbelegung: die Hilfsvariable bekommt das erste Element der Liste, nicht etwa 0. Mit 0 würde der Algorithmus bei negativen Zahlen falsch arbeiten, weil dann nie ein Element kleiner wäre.

c) Auswählen gegen Einfügen

	Durch Auswählen	Durch Einfügen
Aufwand allgemein	O(n²)	O(n²)
Bei schon sortierter Liste	O(n²) – sucht trotzdem jedes Mal alles ab	O(n) – merkt sofort, dass nichts zu verschieben ist
Vergleiche	immer gleich viele, egal wie die Liste aussieht	je nach Vorsortierung deutlich weniger
Elementbewegungen	wenige – pro Durchlauf wandert genau eins	viele Verschiebungen

Beide sind quadratisch und damit für große Datenmengen nicht zu gebrauchen. Der Unterschied liegt im günstigen Fall: Sortieren durch Einfügen profitiert davon, wenn die Daten schon fast sortiert sind, Sortieren durch Auswählen nicht. Auswählen braucht dafür weniger Bewegungen, was zählen kann, wenn das Verschieben teuer ist.

Aufgabe 3 – Quicksort

a) Im Kurs veranschaulichen

Zehn Leute stellen sich nebeneinander auf. Die erste Person nennt ihr Geburtsdatum und tritt einen Schritt vor – das ist das Pivot. Alle Jüngeren gehen nach links, alle Älteren nach rechts. Dann macht jede der beiden Gruppen für sich dasselbe nochmal, bis nur noch Einzelpersonen übrig sind.

Das Schöne daran ist, dass man die Rekursion körperlich sieht: dieselbe Vorschrift wird auf immer kleinere Gruppen angewendet, und am Ende steht alles richtig, ohne dass irgendjemand die ganze Reihe überblickt hätte.

b) Quicksort mit 1, 2, 18, 6, 13, 5, 29

Pivot ist jeweils das erste Element.

quicksort(1, 2, 18, 6, 13, 5, 29)
  Pivot = 1
  kleiner: (leer)          groesser: 2, 18, 6, 13, 5, 29
  -> quicksort(leer) + [1] + quicksort(2, 18, 6, 13, 5, 29)

    quicksort(2, 18, 6, 13, 5, 29)
      Pivot = 2
      kleiner: (leer)      groesser: 18, 6, 13, 5, 29
      -> quicksort(leer) + [2] + quicksort(18, 6, 13, 5, 29)

        quicksort(18, 6, 13, 5, 29)
          Pivot = 18
          kleiner: 6, 13, 5    groesser: 29
          -> quicksort(6, 13, 5) + [18] + quicksort(29)

            quicksort(6, 13, 5)
              Pivot = 6
              kleiner: 5       groesser: 13
              -> quicksort(5) + [6] + quicksort(13)
              -> 5, 6, 13

            quicksort(29) -> 29

          -> 5, 6, 13, 18, 29

      -> 2, 5, 6, 13, 18, 29

Ergebnis: 1, 2, 5, 6, 13, 18, 29

flowchart TD
    A["1, 2, 18, 6, 13, 5, 29 (Pivot 1)"]
    A -- kleiner --> A0["leer"]
    A -- größer --> B["2, 18, 6, 13, 5, 29 (Pivot 2)"]
    B -- kleiner --> B0["leer"]
    B -- größer --> C["18, 6, 13, 5, 29 (Pivot 18)"]
    C -- kleiner --> D["6, 13, 5 (Pivot 6)"]
    C -- größer --> E["29"]
    D -- kleiner --> F["5"]
    D -- größer --> G["13"]

Wie Quicksort 1, 2, 18, 6, 13, 5, 29 zerlegt

Beachte die ersten beiden Schritte: die 1 und die 2 sind schon die kleinsten Elemente, also bleibt die linke Teilliste jeweils leer. Das ist der ungünstige Fall – der Bereich wird nur um ein Element kleiner statt halbiert. Genau darum geht es in Aufgabe 5.

c) Das Struktogramm

+--------------------------------------------------------------+
| quicksort(liste)                                             |
+--------------------------------------------------------------+
|              laenge(liste) <= 1 ?                            |
|  WAHR                          |          FALSCH             |
+--------------------------------+-----------------------------+
| gib liste zurueck              | Pivot = erstes Element      |
| (Rekursionsanker)              +-----------------------------+
|                                | erzeuge Listen kleiner      |
|                                | und groesser                |
|                                +-----------------------------+
|                                |   fuer jedes weitere        |
|                                |   Element e der liste       |
|                                |  +------------------------+ |
|                                |  |    e < Pivot ?         | |
|                                |  | WAHR      |   FALSCH   | |
|                                |  +-----------+------------+ |
|                                |  | an        | an         | |
|                                |  | kleiner   | groesser   | |
|                                |  | anhaengen | anhaengen  | |
|                                |  +-----------+------------+ |
|                                +-----------------------------+
|                                | gib zurueck:                |
|                                |   quicksort(kleiner)        |
|                                |   + Pivot                   |
|                                |   + quicksort(groesser)     |
+--------------------------------+-----------------------------+

Aufgabe 4 – Die Hilfsmethode laenge

public int laenge(List<ContentType> pListe) {
    int anzahl = 0;
    pListe.toFirst();
    while (pListe.hasAccess()) {
        anzahl++;
        pListe.next();
    }
    return anzahl;
}

Wieder das bekannte Listen-Muster. Eine lineare Liste kennt ihre eigene Länge nämlich nicht – man muss durchzählen. Das ist auch der Grund, warum die Methode überhaupt gebraucht wird: Quicksort muss wissen, wann eine Teilliste höchstens ein Element hat und die Rekursion enden kann.

Und weil man dafür jedes Mal die ganze Liste durchläuft, sollte man laenge() nicht in einer Schleifenbedingung aufrufen – dann zählt man bei jedem Durchlauf neu durch.

Aufgabe 5 – Worst Case und Best Case

Fall	Beispielreihe	Was passiert	Aufwand
Worst Case	1, 2, 3, 4, 5, 6, 7	Das Pivot ist immer das kleinste Element. Die linke Teilliste bleibt leer, die rechte wird nur um eins kürzer. Es braucht n Rekursionsebenen.	O(n²)
Best Case	4, 2, 6, 1, 3, 5, 7	Das Pivot ist immer der mittlere Wert. Beide Teillisten sind gleich groß, die Liste halbiert sich bei jedem Schritt.	O(n · log n)

Das ist die ironische Pointe bei Quicksort mit erstem Pivot: eine bereits sortierte Liste ist der schlechteste Fall. Ausgerechnet die Eingabe, bei der es gar nichts zu tun gäbe, ist die langsamste. Eine absteigend sortierte Liste ist übrigens genauso schlimm, nur bleibt dann die rechte Teilliste leer.

Zur Probe für den Best Case: Pivot 4, links 2, 1, 3 und rechts 6, 5, 7. In der linken Liste ist 2 das Pivot, links davon 1, rechts 3 – wieder perfekt halbiert. Rechts genauso mit der 6.

Wie man das Problem in der Praxis löst

Weil sortierte Daten gar nicht so selten sind, nimmt man das erste Element in echten Programmen nicht als Pivot. Üblich sind:

das mittlere Element – bei sortierten Daten sofort optimal
ein zufälliges Element – der worst case wird unwahrscheinlich
der Median aus erstem, mittlerem und letztem Element

Im Schnitt liegt Quicksort bei O(n · log n) und ist damit deutlich schneller als alles, was wir vorher hatten. Bei 10 000 Elementen sind das rund 130 000 Schritte statt 100 Millionen bei den O(n²)-Verfahren.