🃏
Vorlesung 4
Sortieren I —
Karten auf dem Tisch
Fortgeschrittene Algorithmen und Programmierung
Prof. Dr. Alexandra Mikityuk
HTW Berlin
Drei Wege, Chaos in Ordnung zu bringen
Lernziele
- Verstehen, warum Sortieren in fast jedem Programm auftaucht
- Drei Sortier-Algorithmen Schritt für Schritt nachvollziehen können:
- Bubble Sort — Nachbarn vergleichen
- Selection Sort — immer das Kleinste zuerst
- Insertion Sort — wie Karten in der Hand
- Die Idee jeder Methode in eigenen Worten erklären können
- Erste Intuition entwickeln, welcher Algorithmus wann sinnvoll ist
🔮 Vorschau: In Vorlesung 5 bekommen alle drei Algorithmen ein "Etikett" mit ihrer Geschwindigkeit — die Big-O-Notation.
Themen heute
Teil 1
- Warum sortieren?
- Das Sortierproblem
Teil 2
- Bubble Sort
- Selection Sort
- Insertion Sort
Teil 3
- Drei im Vergleich
- Wo sortieren wir wirklich?
- Quiz
Warum sortieren?
Sortieren ist die meistgenutzte Operation in der Informatik. Du nutzt sie ständig:
📞
Telefonbuch
Namen alphabetisch — sonst stundenlanges Suchen.
🏆
Highscore-Liste
Spieler nach Punkten sortiert — von hoch zu niedrig.
📁
Dateien im Ordner
Nach Datum, Größe oder Name.
📧
E-Mails
Neueste oben — automatisch sortiert nach Datum.
🛒
Online-Shop
"Sortieren nach Preis" — ein Algorithmus arbeitet.
🔎
Schnelles Suchen
In sortierten Daten findet man Dinge viel schneller.
Das Sortierproblem
Eingabe
unsortiert
⬇️
Ausgabe
sortiert (aufsteigend)
🎯 Ziel: Elemente so umordnen, dass arr[0] ≤ arr[1] ≤ … ≤ arr[n-1]. Es gibt viele Wege dahin — schauen wir uns drei an.
Stell dir vor: eine Hand voll Karten
Du bekommst 5 Karten ungeordnet auf den Tisch. Du sollst sie aufsteigend sortieren.
Wie würdest du das machen? Es gibt viele Wege. Wir schauen uns drei berühmte an, die alle Computer (und Menschen!) verwenden.
💡 Wichtig: Alle drei Algorithmen funktionieren — sie geben am Ende dasselbe Ergebnis. Sie unterscheiden sich nur in der Strategie.
Bevor wir sortieren — wie testen wir's?
Eine Hand mit 5 Karten ist klar — aber für ein echtes Test-Array mit 100, 1.000 oder einer Million Zahlen brauchen wir Zufallszahlen.
In C übernimmt das die Funktion rand() aus <stdlib.h>.
#include <stdlib.h>
#include <time.h>
#define N 100
int main() {
int arr[N];
srand(time(NULL));
for (int i = 0; i < N; i++) {
arr[i] = rand() % 1000;
}
}
Drei neue Bausteine:
#define für Konstanten ·
rand() für Zufallszahlen ·
srand(time(NULL)) damit jeder Programm-Lauf andere Werte produziert.
💡 Kernidee: Sortier-Algorithmen testet man mit vielen verschiedenen Eingaben — sortiert, fast sortiert, umgekehrt sortiert, zufällig. Nur dann sieht man, ob ein Algorithmus wirklich funktioniert.
Bubble Sort — die Idee
🫧 Vergleiche immer Nachbarn — und tausche, wenn falsch herum.
Wir gehen von links nach rechts und vergleichen jede Karte mit ihrem rechten Nachbarn.
Ist die linke größer? → tauschen. Sonst: weiter.
So "blubbern" die größten Zahlen nach rechts wie Luftblasen im Wasser. Daher der Name.
🫧 Bubble = Blase. Nach jedem Durchgang ist die größte verbleibende Zahl ganz rechts angekommen.
Bubble Sort — Durchgang 1
Start: [5, 1, 4, 2, 3]
Vergleich
5
1
4
2
3
5 > 1 → tauschen!
Vergleich
1
5
4
2
3
5 > 4 → tauschen!
Vergleich
1
4
5
2
3
5 > 2 → tauschen!
Vergleich
1
4
2
5
3
5 > 3 → tauschen!
Ergebnis
1
4
2
3
5
Größte (5) blubbert nach rechts ✓
Bubble Sort — Durchgänge 2 und 3
Durchgang 2 — die rechte 5 ist fertig, also nur noch bis Position 3 vergleichen:
Ende
1
2
3
4
5
4 blubbert hoch ✓
Durchgang 3 — schon fast fertig:
Ende
1
2
3
4
5
Komplett sortiert!
Faustregel: Bei n Karten brauchst du höchstens n − 1 Durchgänge.
Bubble Sort — in C
void bubble_sort(int arr[], int n) {
for (int durchgang = 0; durchgang < n - 1; durchgang++) {
for (int i = 0; i < n - 1 - durchgang; i++) {
if (arr[i] > arr[i+1]) {
int tmp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = tmp;
}
}
}
}
💡 Beobachtung: Zwei verschachtelte Schleifen. Die äußere zählt Durchgänge, die innere wandert von links nach rechts und tauscht Nachbarn.
Selection Sort — die Idee
🔎 Suche immer das kleinste Element und tausche es nach vorne.
Wir gehen das Array durch, finden die kleinste Zahl, und legen sie an die erste Position. Dann suchen wir die zweitkleinste und legen sie auf Position 2. Und so weiter.
🎯 Selection = Auswahl. Wir wählen jedesmal das passende Element aus und packen es an seinen Platz.
Selection Sort — Schritt für Schritt
Start: [5, 1, 4, 2, 3]
Schritt 1
5
1
4
2
3
Min = 1 → tausche mit Position 0
Schritt 2
1
5
4
2
3
Min im Rest = 2 → tausche mit Position 1
Schritt 3
1
2
4
5
3
Min im Rest = 3 → tausche mit Position 2
Schritt 4
1
2
3
5
4
Min im Rest = 4 → tausche mit Position 3
Selection Sort — in C
void selection_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_pos = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_pos]) {
min_pos = j;
}
}
int tmp = arr[i];
arr[i] = arr[min_pos];
arr[min_pos] = tmp;
}
}
💡 Unterschied zu Bubble Sort: Selection Sort tauscht nur einmal pro Durchgang. Bubble Sort tauscht oft mehrmals — dafür sind seine Tausche kürzer (nur Nachbarn).
Insertion Sort — die Idee
🃏 Wie Karten beim Spielen einsortieren.
Stell dir Skat oder Doppelkopf vor: du nimmst eine Karte nach der anderen auf. Jede neue Karte schiebst du in deiner Hand an die richtige Stelle.
Genau das macht Insertion Sort. Links wächst der sortierte Bereich, rechts liegen noch unsortierte Karten.
🃏 Insertion = Einfügen. Wir nehmen jede Zahl und fügen sie an der richtigen Stelle in den schon sortierten Teil ein.
Wie findet Insertion Sort die richtige Stelle? — Vergleich für Vergleich
Kein magisches „Wir wissen schon, wo sie hinkommt". Der Algorithmus geht von rechts nach links durch den sortierten Teil und vergleicht jede Karte mit der neuen.
Beispiel: wir nehmen die Karte 4 aus [1, 5, 4, 2, 3]
Ausgangslage
Sortiert:
1
5
Hand:
4
Rest:
2
3
Vergleich 1
4
↔
5
5 > 4 → 5 ist zu groß, muss nach rechts rutschen
→ Schiebe 5
Sortiert:
1
_
5
Hand:
4
Vergleich 2
4
↔
1
1 ≤ 4 → Platz gefunden! 4 kommt direkt rechts von 1
→ Einfügen
Sortiert:
1
4
5
Rest:
2
3
Das Muster: für jede neue Karte wandern wir von rechts nach links durch den sortierten Teil. Jede Karte, die größer ist, wird eine Position nach rechts geschoben. Sobald wir auf eine kleinere oder gleiche Karte stoßen — Stop, hier einfügen.
Wichtig: wir prüfen nicht alle sortierten Karten. Sobald die richtige Stelle gefunden ist, brechen wir ab. Bei einer schon-fast-sortierten Liste passiert das sehr früh — deshalb ist Insertion Sort auf fast-sortierten Daten so schnell.
Insertion Sort — Schritt für Schritt
Start: [5, 1, 4, 2, 3] — die erste Karte (5) gilt als bereits sortiert.
Nimm 1
5
1
4
2
3
1 vor 5 einfügen
Nimm 4
1
5
4
2
3
4 zwischen 1 und 5 einfügen
Nimm 2
1
4
5
2
3
2 zwischen 1 und 4 einfügen
Nimm 3
1
2
4
5
3
3 zwischen 2 und 4 einfügen
Insertion Sort — in C
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int karte = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > karte) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = karte;
}
}
💡 Beobachtung: Die innere Schleife läuft nicht immer komplett — bei einer fast-sortierten Liste hört sie sehr früh auf. Deshalb ist Insertion Sort auf fast sortierten Daten sehr schnell.
Drei Algorithmen — drei Strategien
| Algorithmus | Idee in einem Satz | Stark, wenn … |
|---|
| Bubble Sort | Tausche falsch geordnete Nachbarn, bis nichts mehr zu tauschen ist. | … kein Vorteil — eher zum Lernen gedacht. |
| Selection Sort | Suche das Minimum, lege es nach vorn, wiederhole. | … Tauschen teuer ist — er tauscht nur n-mal. |
| Insertion Sort | Füge jede neue Karte an die richtige Stelle in der Hand ein. | … die Daten fast schon sortiert sind — extrem schnell. |
Wichtig: Alle drei brauchen bei ungeordneten Daten ungefähr n × n Operationen. Wie viel das wirklich ist, schauen wir uns in Vorlesung 5 an.
Sortieren in Bewegung
Sortier-Algorithmen sehen visuell jeweils anders aus — als animierte Balken erkennt man die Strategie sofort.
Live-Visualisierungen findet ihr z.B. auf visualgo.net oder sorting.at.
🫧 Bubble Sort
Wirkt wie Wellen — kleine Tausch-Bewegungen wandern sichtbar nach rechts. Größte Werte „blubbern" hoch.
🔎 Selection Sort
Klare Sektion-Trennung: links wächst der sortierte Bereich Stück für Stück, rechts bleibt's chaotisch.
🃏 Insertion Sort
Sanftes Einsortieren — neue Werte rutschen jeweils an ihren passenden Platz im linken Bereich.
Lab-Tipp: Im Lab könnt ihr nach jedem Schritt das Array mit printf ausgeben — und seht auf der Konsole, wie sich die Werte bewegen. Selber Effekt wie animierte Balken, nur in Text.
Wie viele Vergleiche brauchen sie?
Zählen wir grob, wie oft jeder Algorithmus zwei Zahlen vergleicht — bei einem komplett unsortierten Array mit n Elementen:
| Algorithmus | Bei n = 5 | Bei n = 100 | Bei n = 1.000 |
|---|
| Bubble Sort | ~ 10 | ~ 5.000 | ~ 500.000 |
| Selection Sort | ~ 10 | ~ 5.000 | ~ 500.000 |
| Insertion Sort | ~ 10 | ~ 5.000 | ~ 500.000 |
🔮 Aha: alle drei wachsen mit n × n = n². Verdoppelst du die Datenmenge, vervierfacht sich der Aufwand. Diese Beobachtung wird in Vorlesung 5 zum berühmten O(n²).
Wo nutzt man diese Algorithmen wirklich?
🎓 Lernen & Lehre
Diese drei sind die "Hello World" der Algorithmen — jede:r Informatik-Student lernt sie zuerst.
🃏 Insertion Sort lebt!
Bei kleinen oder fast sortierten Listen ist Insertion Sort wirklich schnell. Viele große Sortier-Bibliotheken benutzen ihn intern (z. B. innerhalb von Quicksort).
📚 Bibliotheks-Sortierer
In der Praxis: qsort() in C, sorted() in Python — dahinter stecken klügere Verfahren wie Merge Sort und Quick Sort (Vorlesung 6).
Take-away: Diese drei Algorithmen sind das Fundament. Sie helfen uns zu verstehen, was später bei den schnellen Algorithmen passiert.
Bonus: Stabilität — kommt es auf die Reihenfolge an?
Stell dir vor: du hast Studierende mit gleichem Nachnamen "Müller", aber unterschiedlichen Vornamen. Wenn du nach Nachname sortierst, was passiert mit der Reihenfolge der Müllers?
✅ Stabil
Gleiche Werte behalten ihre ursprüngliche Reihenfolge.
Bubble Sort & Insertion Sort sind stabil.
⚠️ Nicht stabil
Gleiche Werte können vertauscht werden.
Selection Sort ist nicht stabil.
Warum wichtig? Wenn du erst nach Vorname und dann nach Nachname sortierst, willst du, dass die Vornamen-Reihenfolge bei gleichem Nachnamen erhalten bleibt. Das geht nur mit einem stabilen Algorithmus.
Übung im Kopf — sortier selbst
👉 Mini-Aufgabe
Hier sind 6 Karten:
[ 7 3 9 1 5 4 ]
Sortiere sie auf zwei verschiedene Weisen — auf Papier, ohne Computer:
- Mit Bubble Sort — schreibe nach jedem Tausch das neue Array auf
- Mit Insertion Sort — schreibe nach jeder Einfügung das Array auf
Warum das wichtig ist: Wenn du den Algorithmus auf Papier ausführen kannst, kannst du ihn in jeder Programmiersprache schreiben. Der Code ist nur die Übersetzung — die Idee ist allgemein.
Im Lab: ihr macht genau das — erst auf Papier durchspielen, dann im Code umsetzen. Erst nachvollziehen, dann tippen.
🧠 Quiz 1
Welcher Algorithmus passt zu dieser Beschreibung:
"Karten in der Hand einsortieren — eine nach der anderen"?
A) Bubble Sort
B) Selection Sort
C) Insertion Sort
D) Merge Sort
🧠 Quiz 2
Welche Aussage über Bubble Sort ist richtig?
A) Er findet immer zuerst das größte Element.
B) Er vergleicht immer Nachbarn und tauscht bei falscher Reihenfolge.
C) Er ist auf großen Datenmengen extrem schnell.
D) Er fügt jede Zahl an der richtigen Stelle ein.
Tipp: Der Name "Bubble" beschreibt, wie sich Werte bewegen.
Zusammenfassung
- Sortieren bringt Ordnung ins Chaos — und macht Suchen schneller.
- Bubble Sort: Nachbarn vergleichen und tauschen — Größtes blubbert nach rechts.
- Selection Sort: immer das Minimum suchen und nach vorn legen.
- Insertion Sort: jede Karte an die richtige Stelle in der "Hand" einfügen.
- Alle drei wachsen mit n × n — ein Etikett dafür kommt in der nächsten Vorlesung.
📚 Nächste Woche: Wir geben jedem Algorithmus ein "Geschwindigkeits-Etikett" — die Big-O-Notation. Damit können wir Algorithmen mathematisch sauber vergleichen.
Wichtig für später
- ✅ Die drei Algorithmen in eigenen Worten erklären können
- ✅ Schritt für Schritt auf Papier ausführen können
- ✅ Die Idee hinter jedem Namen verstehen (Bubble / Selection / Insertion)
- ✅ Stabilität erkennen können
- ✅ Wissen, dass alle drei mit n² wachsen
Prof. Dr. Alexandra Mikityuk
HTW Berlin
Im Lab heute: alle drei selbst implementieren!
© 2026 Prof. Dr. Alexandra Mikityuk | HTW Berlin