In Vorlesung 4 habt ihr drei klassische Sortier-Algorithmen kennengelernt: Bubble, Selection und Insertion Sort. In Vorlesung 5 kam dann die Sprache, mit der wir sie vergleichen: die Big-O-Notation.
Heute setzt ihr beides um — mit Fokus auf Verstehen, nicht nur Tippen:
Im Kurs ist C unsere gemeinsame Sprache, und alle Musterlösungen sind in C. Das ist die Sprache, in der Algorithmen am wenigsten „verzaubert" sind — kein verstecktes Sortieren im Hintergrund, keine Magie.
Aber: wenn ihr sicher in einer anderen Sprache seid — Arduino C++, Python, JavaScript, Rust — dann macht die Aufgaben dort. Algorithmen sind sprachunabhängig.
Wenn ihr in Klausur oder Bachelorarbeit Algorithmen erklären müsst, fragt niemand nach printf-Syntax. Es geht um das Wieso und Wie schnell.
Bubble, Selection, Insertion auf Papier nachvollziehen — Schritt für Schritt
Alle drei Sortier-Algorithmen aus dem Pseudocode in Code übersetzen
Vergleiche und Vertauschungen mitzählen — der Realitätscheck zur Big-O-Theorie
Laufzeit für n = 100, 1 000, 5 000 messen — und das Wachstum mit den Augen sehen
Aus einem Code-Stück die Komplexitätsklasse erkennen
Ziel: Den Unterschied zwischen den drei Algorithmen spüren — bevor ihr ihn programmiert.
Nehmt diese Karten:
Sortiert sie aufsteigend — drei Mal, einmal mit jedem Algorithmus. Schreibt für jede Methode jeden Schritt auf Papier mit:
| Algorithmus | Vergleiche gesamt | Vertauschungen gesamt | Wie hat es sich „angefühlt"? |
|---|---|---|---|
| Bubble Sort | ______ | ______ | ______ |
| Selection Sort | ______ | ______ | ______ |
| Insertion Sort | ______ | ______ | ______ |
Jeder Durchgang: vergleiche jedes Nachbar-Paar und tausche, falls links > rechts. Nach jedem Durchgang steht das größte Element ganz hinten.
Jeder Durchgang: suche das Minimum im unsortierten Teil — tausche es ans vordere Ende. Maximal n-1 Swaps insgesamt.
Wie Karten sortieren auf der Hand: nimm die nächste Karte, vergleiche von rechts nach links mit den schon sortierten und schiebe größere nach rechts.
| Algorithmus | Vergleiche | Vertauschungen / Shifts | Beobachtung |
|---|---|---|---|
| Bubble Sort | 15 | 10 Swaps | viele Swaps — jede Nachbar-Verletzung kostet einen |
| Selection Sort | 15 | 4 Swaps | gleiche Vergleiche, aber deutlich weniger Swaps (max. n-1) |
| Insertion Sort | 13 | 10 Shifts | etwas weniger Vergleiche; Shifts sind „halbe" Swaps (nur Lesen+Schreiben in eine Richtung) |
Lehre daraus: die Anzahl der Vergleiche ist für alle drei ähnlich (alle O(n²) — 15 ≈ 6²/2). Was sie unterscheidet, ist was sonst noch passiert: viele Swaps (Bubble), wenige große Swaps (Selection), viele kleine Shifts (Insertion). Im Computer kostet das unterschiedlich — daher messen wir das in Aufgabe 5.
Hinweis: Kleine Abweichungen in eurer Zählung sind OK — bei Insertion zählt manche Lehrbücher den letzten „nicht-tauschen"-Vergleich nicht mit. Das Wichtigste ist das Verhältnis zwischen den drei Algorithmen.
Ziel: den ersten Sortier-Algorithmus selbst schreiben — und live zählen, wie viele Vergleiche und Vertauschungen er macht.
vergleiche und swaps.[7, 3, 9, 1, 5, 2] und gib die Zähler am Ende aus.[1, 2, 3, 4, 5, 6] (schon sortiert) und gib die Zähler aus.early-exit beim ersten swap-freien Durchgang. Wir wollen den „rohen" Big-O-Worst-Case sehen.
Aus VL 5: Bubble Sort macht im Worst Case ca. n²/2 Vergleiche. Bei n = 6: ~ 18 Vergleiche.
Passt das zu eurer Messung? Wenn nicht — wo ist der Unterschied?
#include <stdio.h>
// Globale Zähler — einfacher als Pointer-Parameter
int vergleiche = 0;
int swaps = 0;
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
vergleiche = vergleiche + 1;
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
swaps = swaps + 1;
}
}
}
}
int main(void) {
int a[] = {7, 3, 9, 1, 5, 2};
int n = 6;
bubble_sort(a, n);
printf("Sortiert: ");
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
printf("Vergleiche: %d, Swaps: %d\n", vergleiche, swaps);
return 0;
}
Erwartete Zähler für [7,3,9,1,5,2]: 15 Vergleiche, 6 Swaps.
Für sortiertes [1,2,3,4,5,6]: 15 Vergleiche, 0 Swaps — Bubble Sort schaut immer alles an.
Tipp: Globale Variablen sind hier OK für Zähler. Bei größeren Programmen würde man sie kapseln (kommt später).
Ziel: Selection Sort selbst schreiben — und beobachten, warum er weniger Swaps braucht als Bubble.
vergleiche und swaps.[7, 3, 9, 1, 5, 2] und gib die Zähler aus.#include <stdio.h>
int vergleiche = 0;
int swaps = 0;
void selection_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
vergleiche = vergleiche + 1;
if (a[j] < a[min_idx]) {
min_idx = j;
}
}
// Nur tauschen, wenn ein kleineres Element gefunden wurde
if (min_idx != i) {
int t = a[i];
a[i] = a[min_idx];
a[min_idx] = t;
swaps = swaps + 1;
}
}
}
int main(void) {
int a[] = {7, 3, 9, 1, 5, 2};
int n = 6;
selection_sort(a, n);
printf("Sortiert: ");
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
printf("Vergleiche: %d, Swaps: %d\n", vergleiche, swaps);
return 0;
}
Erwartete Zähler für [7,3,9,1,5,2]: 15 Vergleiche, ≤ 5 Swaps (immer max. n-1).
Bubble hatte 6 Swaps — bei größeren Arrays wird der Unterschied dramatisch.
Ziel: Insertion Sort schreiben — und sehen, warum er bei fast-sortierten Daten unschlagbar ist.
[7, 3, 9, 1, 5, 2][1, 2, 3, 4, 5, 6] — Best Case[6, 5, 4, 3, 2, 1] — Worst Case#include <stdio.h>
int vergleiche = 0;
int shifts = 0;
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int wert = a[i];
int j = i - 1;
// Schiebe alle größeren Elemente nach rechts
while (j >= 0 && a[j] > wert) {
vergleiche = vergleiche + 1;
a[j + 1] = a[j];
shifts = shifts + 1;
j = j - 1;
}
// Der letzte Vergleich, der zum Abbruch geführt hat, zählt auch
if (j >= 0) {
vergleiche = vergleiche + 1;
}
a[j + 1] = wert;
}
}
void test(int a[], int n, const char *name) {
vergleiche = 0;
shifts = 0;
insertion_sort(a, n);
printf("[%s] Vergleiche: %d, Shifts: %d\n", name, vergleiche, shifts);
}
int main(void) {
int zufall[6] = {7, 3, 9, 1, 5, 2};
int sortiert[6] = {1, 2, 3, 4, 5, 6};
int umgekehrt[6] = {6, 5, 4, 3, 2, 1};
test(zufall, 6, "zufaellig");
test(sortiert, 6, "sortiert");
test(umgekehrt, 6, "umgekehrt");
return 0;
}
Erwartete Ausgabe (etwa):
[zufaellig] Vergleiche: 10, Shifts: 9 [sortiert] Vergleiche: 5, Shifts: 0 ← O(n) Best Case! [umgekehrt] Vergleiche: 15, Shifts: 15 ← O(n²) Worst Case
Kleine Abweichungen sind OK — der entscheidende Punkt ist das Verhältnis zwischen den drei Fällen.
Ziel: Big-O ist Theorie. Heute macht ihr daraus eine Beobachtung: messt die Laufzeit, seht wie sie wächst.
| n | Bubble | Selection | Insertion | Faktor (n×10) |
|---|---|---|---|---|
| 100 | ______ ms | ______ ms | ______ ms | — |
| 1 000 | ______ ms | ______ ms | ______ ms | erwartet ~ 100× |
| 5 000 | ______ ms | ______ ms | ______ ms | erwartet ~ 25× |
#include <time.h>
clock_t start = clock();
// ... Algorithmus ausführen ...
clock_t ende = clock();
double ms = ((double)(ende - start)) / CLOCKS_PER_SEC * 1000.0;
printf("Dauer: %.2f ms\n", ms);In Python: time.perf_counter() · JavaScript: performance.now() · Arduino: millis() oder micros().
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Maximale Größe — feste Arrays statt malloc
#define MAX_N 5000
// Drei Sortier-Funktionen, jede mit eigenem Array
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
}
}
void selection_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[min_idx]) min_idx = j;
}
int t = a[i];
a[i] = a[min_idx];
a[min_idx] = t;
}
}
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int wert = a[i];
int j = i - 1;
while (j >= 0 && a[j] > wert) {
a[j + 1] = a[j];
j = j - 1;
}
a[j + 1] = wert;
}
}
// Füllt Array mit den gleichen Pseudo-Zufallszahlen
// (jeder Aufruf gibt die selbe Reihenfolge - für fairen Vergleich)
void fuelle_array(int a[], int n) {
srand(42); // gleiche Startzahl = gleiche Reihenfolge
for (int i = 0; i < n; i++) {
a[i] = rand() % 10000;
}
}
int main(void) {
int groessen[3] = {100, 1000, 5000};
int daten[MAX_N];
for (int g = 0; g < 3; g++) {
int n = groessen[g];
printf("n = %d:\n", n);
// Bubble Sort
fuelle_array(daten, n);
clock_t start = clock();
bubble_sort(daten, n);
clock_t ende = clock();
double ms = (double)(ende - start) / CLOCKS_PER_SEC * 1000.0;
printf(" Bubble: %.2f ms\n", ms);
// Selection Sort
fuelle_array(daten, n);
start = clock();
selection_sort(daten, n);
ende = clock();
ms = (double)(ende - start) / CLOCKS_PER_SEC * 1000.0;
printf(" Selection: %.2f ms\n", ms);
// Insertion Sort
fuelle_array(daten, n);
start = clock();
insertion_sort(daten, n);
ende = clock();
ms = (double)(ende - start) / CLOCKS_PER_SEC * 1000.0;
printf(" Insertion: %.2f ms\n", ms);
}
return 0;
}
Beobachtung: Insertion ist typisch ~ 2× schneller als Bubble (weniger Schreibzugriffe). Selection liegt dazwischen. Aber alle drei skalieren mit n² — Faktor 100, wenn n verzehnfacht.
Hinweis: wir nutzen srand(42) mit fester Startzahl, damit alle drei Algorithmen die gleichen Daten sortieren — sonst wäre der Vergleich unfair.
Ziel: Code lesen und ohne Ausführen die Komplexitätsklasse erkennen.
Notiert für jeden Code-Schnipsel die Big-O-Komplexität als Funktion von n. Begründet kurz (1 Satz).
int summe = 0;
for (int i = 0; i < n; i++) {
summe += a[i];
}O( ______ ) — Begründung: _______________________________
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", i + j);
}
}O( ______ ) — Begründung: _______________________________
int x = 1;
while (x < n) {
x = x * 2;
}O( ______ ) — Begründung: _______________________________
for (int i = 0; i < n; i++) {
int x = 1;
while (x < n) {
x = x * 2;
}
}O( ______ ) — Begründung: _______________________________
int gefunden = 0;
for (int i = 0; i < n && !gefunden; i++) {
if (a[i] == zielwert) gefunden = 1;
}O( ______ ) im Worst Case — Begründung: _______________________________
| Schnipsel | Big-O | Begründung |
|---|---|---|
| A | O(n) | eine einfache Schleife über n Elemente |
| B | O(n²) | verschachtelte Schleifen, beide bis n |
| C | O(log n) | x verdoppelt sich — braucht nur log₂(n) Schritte, bis x ≥ n |
| D | O(n · log n) | äußere Schleife O(n), innere Schleife O(log n) → multipliziert |
| E | O(n) | im Worst Case (Zielwert nicht im Array oder ganz am Ende) wird die ganze Schleife durchlaufen — linear |
Hinweis zu E: der Best Case wäre O(1), wenn das Zielelement am Anfang steht. Big-O beschreibt aber per Konvention den Worst Case.
Ziel: Bubble Sort hat im Worst Case O(n²) — aber mit einem kleinen Trick kann er bei sortierten Daten in O(n) fertig sein. Das wird gerne in der Klausur gefragt.
Wenn in einem ganzen Durchgang kein einziger Swap passiert, ist das Array schon sortiert — wir können sofort aufhören. Dazu brauchen wir nur ein Flag (eine 0/1-Variable):
[7, 3, 9, 1, 5, 2] — zufällig[1, 2, 3, 4, 5, 6] — schon sortiert[1, 2, 3, 4, 6, 5] — fast sortiert (nur ein Swap nötig)#include <stdio.h>
int vergleiche = 0;
void bubble_sort_optimiert(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int getauscht = 0; // Flag: gab es Swaps?
for (int j = 0; j < n - 1 - i; j++) {
vergleiche = vergleiche + 1;
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
getauscht = 1;
}
}
if (getauscht == 0) {
// Kein Swap im ganzen Durchgang → sortiert
break;
}
}
}
void test(int a[], int n, const char *name) {
vergleiche = 0;
bubble_sort_optimiert(a, n);
printf("[%s] Vergleiche: %d\n", name, vergleiche);
}
int main(void) {
int zufall[6] = {7, 3, 9, 1, 5, 2};
int sortiert[6] = {1, 2, 3, 4, 5, 6};
int fastsortiert[6] = {1, 2, 3, 4, 6, 5};
test(zufall, 6, "zufaellig");
test(sortiert, 6, "sortiert");
test(fastsortiert, 6, "fast sortiert");
return 0;
}
Erwartete Ausgabe:
[zufaellig] Vergleiche: 14 [sortiert] Vergleiche: 5 ← O(n) Best Case ✓ [fast sortiert] Vergleiche: 9 ← spart viele Vergleiche
Zum Vergleich: der normale Bubble Sort aus Aufgabe 2 macht immer 15 Vergleiche — egal wie sortiert die Daten sind.
Bevor du gehst, beantworte für dich:
→ Diese Reflexion ist freiwillig — aber sie zementiert das Gelernte.
Die Passwörter stehen unten — frei zugänglich. Bitte fair spielen: erst selbst implementieren, dann mit der Musterlösung vergleichen. Eine Lösung, die ihr nur abgeschrieben habt, hilft euch in der Klausur nicht.
| Aufgabe | Thema | Passwort |
|---|---|---|
| Aufgabe 1 | Sortieren von Hand | papier |
| Aufgabe 2 | Bubble Sort | nachbar |
| Aufgabe 3 | Selection Sort | minimum |
| Aufgabe 4 | Insertion Sort | karten |
| Aufgabe 5 | Benchmark | benchmark |
| Aufgabe 6 | Big-O bestimmen | bigo |
| Aufgabe 7 | Bubble Sort optimiert (Bonus) | earlyexit |
Hinweis für Arduino/Python/JavaScript-Lösungen: die Logik der C-Lösung gilt 1:1 — übersetzt nur die Syntax. Eine eigene Musterlösung für jede Sprache gibt es nicht.
© 2026 HTW Berlin · Prof. Dr. Alexandra Mikityuk