⚙️ Thema 6: Algorithmen

Überblick

In diesem Themenbereich geht es darum, wie Probleme mit klaren Schrittfolgen gelöst werden können. Solche Schrittfolgen nennt man Algorithmen.

Algorithmen begegnen uns nicht nur beim Programmieren, sondern auch im Alltag:

• beim Suchen eines Namens in einer Liste,
• beim Sortieren von Karten,
• beim Navigieren mit einer Karten-App,
• beim Filtern von Suchergebnissen,
• beim Empfehlen von Videos oder Musik,
• beim Planen von Routen,
• beim automatischen Auswerten von Daten.

In der Informatik interessiert nicht nur, ob ein Algorithmus funktioniert. Wichtig ist auch, wie effizient er arbeitet und wie sich sein Verhalten bei kleinen oder großen Datenmengen verändert.

Leitfrage

Wie lassen sich Probleme durch klare Schrittfolgen lösen, und woran erkennt man, ob ein Algorithmus effizient arbeitet?

Was ist ein Algorithmus?

Ein Algorithmus ist eine eindeutige Schrittfolge zur Lösung eines Problems.

Ein Algorithmus beschreibt also nicht nur ungefähr, was passieren soll, sondern legt fest, welche Schritte in welcher Reihenfolge ausgeführt werden.

Beispiel aus dem Alltag:

Suche ein bestimmtes Wort in einem Wörterbuch.

Mögliche Strategie:

1. Öffne das Wörterbuch ungefähr in der Mitte.
2. Vergleiche das gesuchte Wort mit den Wörtern auf der Seite.
3. Entscheide, ob du links oder rechts weitersuchen musst.
4. Wiederhole das Vorgehen, bis du das Wort gefunden hast oder sicher bist, dass es nicht vorkommt.

Merke

Ein Algorithmus ist eine präzise Vorschrift, die Schritt für Schritt zu einer Lösung führen soll.

Eigenschaften von Algorithmen

Algorithmen besitzen typische Eigenschaften.

Eigenschaft	Bedeutung
Eindeutigkeit	Jeder Schritt ist klar beschrieben.
Ausführbarkeit	Jeder Schritt kann tatsächlich durchgeführt werden.
Endlichkeit	Der Algorithmus endet nach endlich vielen Schritten.
Korrektheit	Der Algorithmus liefert für gültige Eingaben das richtige Ergebnis.
Allgemeinheit	Der Algorithmus funktioniert nicht nur für einen Einzelfall, sondern für eine Klasse ähnlicher Probleme.
Effizienz	Der Algorithmus löst das Problem mit möglichst angemessenem Aufwand.

Wichtig

Ein Algorithmus kann korrekt sein, aber trotzdem unpraktisch langsam. Deshalb ist Effizienz ein wichtiger Bestandteil der Bewertung.

Determinismus und Determiniertheit

Zwei Begriffe klingen ähnlich, bedeuten aber nicht genau dasselbe.

Begriff	Bedeutung
Determinismus	Bei jedem Schritt ist eindeutig festgelegt, welcher nächste Schritt folgt.
Determiniertheit	Bei gleicher Eingabe entsteht immer dieselbe Ausgabe.

Ein deterministischer Algorithmus ist Schritt für Schritt eindeutig festgelegt.

Ein determinierter Algorithmus liefert bei gleicher Eingabe immer dasselbe Ergebnis.

Merke

Determinismus beschreibt den Ablauf.
Determiniertheit beschreibt das Ergebnis.

Ein Beispiel für einen nicht vollständig vorhersehbaren Ablauf wäre ein Programm, das Zufallszahlen verwendet. Es kann trotzdem nach festen Regeln programmiert sein, aber die konkrete Ausgabe kann sich unterscheiden.

Effizienz

Effizienz beschreibt, wie viele Ressourcen ein Algorithmus benötigt.

Wichtige Ressourcen sind:

• Zeit,
• Speicherplatz,
• Energie,
• Anzahl der Vergleiche,
• Anzahl der Rechenschritte,
• Anzahl der Zugriffe auf Daten.

In der Schule betrachten wir meistens die Laufzeit bzw. die Anzahl der notwendigen Schritte.

Merksatz

Ein effizienter Algorithmus löst ein Problem nicht nur richtig, sondern auch mit möglichst geringem Aufwand.

Laufzeitverhalten

Das Laufzeitverhalten beschreibt, wie sich der Aufwand eines Algorithmus verändert, wenn die Eingabe größer wird.

Dabei fragt man zum Beispiel:

• Was passiert bei 10 Elementen?
• Was passiert bei 1 000 Elementen?
• Was passiert bei 1 000 000 Elementen?

Ein Algorithmus, der bei kleinen Datenmengen schnell genug ist, kann bei großen Datenmengen plötzlich ungeeignet werden.

Best Case, Worst Case und Average Case

Das Laufzeitverhalten hängt oft davon ab, wie günstig oder ungünstig die Eingabe ist.

Fall	Bedeutung
Best Case	günstigster Fall
Worst Case	ungünstigster Fall
Average Case	durchschnittlich erwarteter Fall

Beispiel: Suche in einer Liste

• Best Case: Das gesuchte Element steht ganz vorne.
• Worst Case: Das gesuchte Element steht ganz hinten oder kommt gar nicht vor.
• Average Case: Das gesuchte Element liegt irgendwo in der Liste.

Merke

Bei der Bewertung von Algorithmen sollte man nicht nur den günstigsten Fall betrachten. Besonders wichtig ist oft der Worst Case, weil er zeigt, wie schlecht es höchstens laufen kann.

Lineare Suche

Die lineare Suche prüft eine Liste Element für Element.

Beispiel:

[4, 9, 12, 18, 23, 31]

Gesucht wird 18.

Ablauf:

1. Prüfe 4 → nicht gesucht.
2. Prüfe 9 → nicht gesucht.
3. Prüfe 12 → nicht gesucht.
4. Prüfe 18 → gefunden.

Die lineare Suche funktioniert auch dann, wenn die Liste nicht sortiert ist.

Merke

Lineare Suche ist einfach und zuverlässig, benötigt aber im ungünstigsten Fall viele Vergleiche.

Lineare Suche in Python

def enthaelt_wert(liste, suchwert):
    for element in liste:
        if element == suchwert:
            return True

    return False


zahlen = [4, 9, 12, 18, 23, 31]

print(enthaelt_wert(zahlen, 18))
print(enthaelt_wert(zahlen, 7))

Die Funktion durchläuft die Liste von links nach rechts. Sobald der gesuchte Wert gefunden wurde, gibt sie True zurück. Wird der Wert nicht gefunden, gibt sie am Ende False zurück.

Laufzeit der linearen Suche

Bei n Elementen gilt:

Fall	Aufwand
Best Case	1 Vergleich
Worst Case	n Vergleiche
Average Case	ungefähr n/2 Vergleiche

Wichtig

Die lineare Suche braucht keine sortierte Liste. Das ist ein Vorteil. Bei großen Listen kann sie aber langsam werden.

📝 Übung: Lineare Suche nachvollziehen

Gegeben ist die Liste:

[6, 11, 15, 22, 27, 34, 40]

Gesucht wird 27.

1. Notiere, welche Elemente der Reihe nach geprüft werden.
2. Gib an, nach wie vielen Vergleichen der Wert gefunden wird.
3. Erkläre, was passieren würde, wenn 99 gesucht wird.

Lösung

Geprüft werden:

6, 11, 15, 22, 27

Der Wert wird nach 5 Vergleichen gefunden.

Wenn 99 gesucht wird, muss die ganze Liste durchsucht werden. Danach kann man feststellen, dass der Wert nicht vorkommt.

Binäre Suche

Die binäre Suche ist deutlich effizienter als die lineare Suche, hat aber eine wichtige Voraussetzung:

Voraussetzung

Binäre Suche funktioniert nur korrekt, wenn die Liste sortiert ist.

Die Grundidee:

1. Betrachte das mittlere Element der Liste.
2. Vergleiche den Suchwert mit diesem Element.
3. Ist der Suchwert gleich, wurde er gefunden.
4. Ist der Suchwert kleiner, suche nur links weiter.
5. Ist der Suchwert größer, suche nur rechts weiter.
6. Wiederhole das Vorgehen.

Beispiel:

[2, 5, 8, 12, 16, 23, 38, 45, 56]

Gesucht wird 45.

Ablauf:

1. Mitte: 16
45 ist größer → rechts weitersuchen.

2. Neuer Bereich:

[23, 38, 45, 56]

Mitte ungefähr: 38
45 ist größer → rechts weitersuchen.

3. Neuer Bereich:

[45, 56]

Mitte: 45
gefunden.

Merke

Bei jedem Schritt wird ungefähr die Hälfte der verbleibenden Liste ausgeschlossen.

Abb.: Binäre Suche: Der Suchbereich wird schrittweise halbiert. Bei 1 000 000 000 Elementen sind maximal 30 Vergleiche nötig. Eigene Darstellung.

Binäre Suche in Python

def binaere_suche(sortierte_liste, suchwert):
    links = 0
    rechts = len(sortierte_liste) - 1

    while links <= rechts:
        mitte = (links + rechts) // 2
        aktueller_wert = sortierte_liste[mitte]

        if aktueller_wert == suchwert:
            return True
        elif suchwert < aktueller_wert:
            rechts = mitte - 1
        else:
            links = mitte + 1

    return False


werte = [2, 5, 8, 12, 16, 23, 38, 45, 56]

print(binaere_suche(werte, 45))
print(binaere_suche(werte, 7))

Merksatz

Binäre Suche ist besonders stark bei großen, sortierten Datenmengen.

Lineare und binäre Suche vergleichen

Merkmal	Lineare Suche	Binäre Suche
Voraussetzung	keine Sortierung nötig	Liste muss sortiert sein
Vorgehen	Element für Element prüfen	Suchbereich halbieren
Vorteil	einfach, funktioniert immer	sehr effizient bei großen Listen
Nachteil	langsam bei großen Listen	Sortierung muss vorhanden sein
Worst Case	n Vergleiche	ungefähr log₂(n) Vergleiche

Beispielhafte Größenordnung:

Anzahl Elemente	Lineare Suche im Worst Case	Binäre Suche ungefähr
10	10 Vergleiche	4 Vergleiche
100	100 Vergleiche	7 Vergleiche
1 000	1 000 Vergleiche	10 Vergleiche
1 000 000	1 000 000 Vergleiche	20 Vergleiche

Merke

Der Unterschied zwischen linearer und binärer Suche wird bei großen Datenmengen besonders deutlich.

Lohnt sich Sortieren vor dem Suchen?

Ob sich Sortieren vor dem Suchen lohnt, hängt vom Anwendungsfall ab.

Wenn du nur einmal in einer kleinen unsortierten Liste suchst, ist Sortieren oft unnötiger Zusatzaufwand.

Wenn du aber sehr oft in derselben Liste suchst, kann es sinnvoll sein, die Liste zuerst zu sortieren und danach binär zu suchen.

Denkfrage

Sortieren kostet zuerst Aufwand. Dieser Aufwand kann sich lohnen, wenn danach viele Suchvorgänge schneller werden.

Beispiel:

Eine unsortierte Liste enthält 20 Werte. Du suchst nur einmal.

• Lineare Suche ist einfach und wahrscheinlich ausreichend.
• Sortieren wäre zusätzlicher Aufwand.

Eine Liste enthält 100 000 Werte. Du musst täglich viele Suchanfragen durchführen.

• Einmaliges Sortieren kann sinnvoll sein.
• Danach kann jede Suche mit binärer Suche deutlich schneller erfolgen.

Wichtig

Effizienz hängt vom Kontext ab. Ein Algorithmus ist nicht immer „besser“, sondern nur für bestimmte Bedingungen besser geeignet.

Sortieren

Ein Sortieralgorithmus bringt Elemente in eine bestimmte Reihenfolge.

Beispiele:

• Zahlen aufsteigend sortieren,
• Namen alphabetisch sortieren,
• Dateien nach Datum sortieren,
• Produkte nach Preis sortieren,
• Nachrichten nach Uhrzeit sortieren.

Sortieren ist in der Informatik sehr wichtig, weil viele andere Verfahren dadurch schneller oder einfacher werden.

Merke

Sortieren braucht ein Sortierkriterium. Ohne erkennbares Kriterium sind Daten zwar vielleicht irgendwie angeordnet, aber informatisch nicht sinnvoll sortiert.

Selection Sort

Selection Sort bedeutet „Sortieren durch Auswählen“.

Die Grundidee:

1. Suche im unsortierten Bereich das kleinste Element.
2. Tausche es mit dem ersten Element des unsortierten Bereichs.
3. Der sortierte Bereich wächst um ein Element.
4. Wiederhole das Vorgehen, bis die Liste sortiert ist.

Beispiel:

[6, 2, 9, 4]

Erster Durchlauf:

• kleinstes Element suchen: 2
• 2 mit dem ersten Element 6 tauschen
• Ergebnis:

[2, 6, 9, 4]

Zweiter Durchlauf:

• unsortierter Bereich: [6, 9, 4]
• kleinstes Element: 4
• 4 mit 6 tauschen
• Ergebnis:

[2, 4, 9, 6]

Dritter Durchlauf:

• unsortierter Bereich: [9, 6]
• kleinstes Element: 6
• 6 mit 9 tauschen
• Ergebnis:

[2, 4, 6, 9]

Merke

Bei Selection Sort wird in jedem Durchlauf das kleinste Element des unsortierten Bereichs ausgewählt und an die nächste richtige Position gebracht.

Abb.: Selection Sort: Das kleinste Element der unsortierten Folge wird gesucht und mit dem ersten Element der unsortierten Folge getauscht. Eigene Darstellung.

Vertiefung: Insertion Sort

Insertion Sort bedeutet „Sortieren durch Einfügen“.

Die Grundidee ähnelt dem Sortieren von Spielkarten auf der Hand:

1. Ein Teil der Liste gilt bereits als sortiert.
2. Das nächste Element aus dem unsortierten Bereich wird genommen.
3. Dieses Element wird an der passenden Stelle in den sortierten Bereich eingefügt.
4. Der sortierte Bereich wächst Schritt für Schritt.

Beispiel:

[5, 2, 8, 1]

Man betrachtet zunächst 5 als sortierten Bereich.

Dann wird 2 passend eingefügt:

[2, 5, 8, 1]

Dann wird 8 eingefügt. Es bleibt hinter 5:

[2, 5, 8, 1]

Dann wird 1 ganz vorne eingefügt:

[1, 2, 5, 8]

Merke

Bei Insertion Sort wird jedes neue Element in einen bereits sortierten Bereich passend eingefügt.

Abb.: Insertion Sort: Das erste Element der unsortierten Folge wird gewählt und passend in die sortierte Folge eingefügt. Eigene Darstellung.

Bubble Sort

Bubble Sort ist ein einfacher Sortieralgorithmus. Er vergleicht immer benachbarte Elemente und vertauscht sie, wenn sie in der falschen Reihenfolge stehen.

Beispiel:

[5, 2, 8, 1]

Erster Durchlauf:

• Vergleiche 5 und 2 → vertauschen: [2, 5, 8, 1]
• Vergleiche 5 und 8 → nichts tun: [2, 5, 8, 1]
• Vergleiche 8 und 1 → vertauschen: [2, 5, 1, 8]

Nach einem vollständigen Durchlauf steht das größte Element am Ende.

Merke

Bei Bubble Sort „wandern“ große Werte Schritt für Schritt nach rechts.

Abb.: Bubble Sort: Benachbarte Elemente werden verglichen und bei falscher Reihenfolge vertauscht. Dadurch wandern große Elemente schrittweise nach hinten. Eigene Darstellung.

Bubble Sort in Python

def bubble_sort(liste):
    n = len(liste)

    for durchlauf in range(n):
        for i in range(0, n - 1 - durchlauf):
            if liste[i] > liste[i + 1]:
                liste[i], liste[i + 1] = liste[i + 1], liste[i]

    return liste


werte = [5, 2, 8, 1]
print(bubble_sort(werte))

Bubble Sort ist leicht verständlich, aber bei großen Listen meist nicht effizient.

Bubble Sort mit Abbruch

Eine optimierte Variante merkt sich, ob in einem Durchlauf überhaupt vertauscht wurde. Wenn nichts vertauscht wurde, ist die Liste bereits sortiert.

def bubble_sort_mit_abbruch(liste):
    n = len(liste)

    for durchlauf in range(n):
        getauscht = False

        for i in range(0, n - 1 - durchlauf):
            if liste[i] > liste[i + 1]:
                liste[i], liste[i + 1] = liste[i + 1], liste[i]
                getauscht = True

        if not getauscht:
            break

    return liste


werte = [1, 2, 3, 4, 5]
print(bubble_sort_mit_abbruch(werte))

Merksatz

Der Abbruch spart Zeit, wenn die Liste bereits sortiert ist oder früh sortiert wird.

Code-Tracing bei Sortieralgorithmen

Beim Code-Tracing wird ein Programm Schritt für Schritt nachvollzogen. Dabei notiert man, wie sich Variablen und Listen verändern.

Beispiel:

werte = [4, 1, 3]

for i in range(len(werte) - 1):
    if werte[i] > werte[i + 1]:
        werte[i], werte[i + 1] = werte[i + 1], werte[i]

Ablauf:

i	Vergleich	Tausch?	Liste danach
0	4 > 1	ja	[1, 4, 3]
1	4 > 3	ja	[1, 3, 4]

Merke

Code-Tracing zeigt, wie ein Algorithmus tatsächlich arbeitet. Das ist besonders hilfreich bei Schleifen, Bedingungen und Listenveränderungen.

📝 Übung: Code-Tracing

Gegeben ist der Code:

zahlen = [7, 3, 5]

for i in range(len(zahlen) - 1):
    if zahlen[i] > zahlen[i + 1]:
        zahlen[i], zahlen[i + 1] = zahlen[i + 1], zahlen[i]

print(zahlen)

1. Notiere für jeden Schleifendurchlauf den Wert von i.
2. Notiere, welche zwei Werte verglichen werden.
3. Notiere, ob getauscht wird.
4. Gib die Liste nach jedem Durchlauf an.

Lösung

Start:

[7, 3, 5]

i	Vergleich	Tausch?	Liste danach
0	7 > 3	ja	[3, 7, 5]
1	7 > 5	ja	[3, 5, 7]

Ausgabe:

[3, 5, 7]

Vertiefung: Rekursion

Rekursion bedeutet, dass eine Funktion sich selbst aufruft.

Ein rekursiver Algorithmus braucht immer:

• einen Rekursionsanker, also einen Fall, in dem die Rekursion endet,
• einen Rekursionsschritt, bei dem das Problem verkleinert und erneut bearbeitet wird.

Ein einfaches Beispiel ist die Summe aller Zahlen von n bis 1.

def summe_bis(n):
    if n <= 0:
        return 0
    else:
        return n + summe_bis(n - 1)

Für summe_bis(4) entsteht gedanklich:

4 + 3 + 2 + 1

Wichtig

Ohne Rekursionsanker würde sich eine Funktion immer weiter selbst aufrufen. Dann entsteht eine endlose Rekursion.

Quicksort

Quicksort ist ein schneller Sortieralgorithmus, der rekursiv arbeitet. Er folgt dem Prinzip Teile und herrsche.

Die Grundidee:

1. Wähle ein Element als Vergleichswert. Dieses Element nennt man Pivot.
2. Teile die übrigen Elemente auf:
   • kleinere Werte links,
   • größere Werte rechts.
3. Sortiere die linke und rechte Teilliste wieder auf dieselbe Weise.
4. Setze die Teile zusammen.

Beispiel:

[8, 3, 10, 1, 6]

Wähle 8 als Pivot.

Kleinere Werte:

[3, 1, 6]

Größere Werte:

[10]

Dann werden die Teillisten weiter sortiert.

Merke

Quicksort zerlegt ein großes Sortierproblem in kleinere Sortierprobleme.

Abb.: Quicksort: Auffällige Pivot-Elemente teilen die Liste in kleinere und größere Werte. Die entstehenden Teillisten werden erneut mit Pivot-Elementen aufgeteilt und schließlich zur sortierten Liste zusammengesetzt. Eigene Darstellung.

Quicksort in Python

def quicksort(liste):
    if len(liste) <= 1:
        return liste

    pivot = liste[0]
    kleiner = []
    groesser = []

    for element in liste[1:]:
        if element <= pivot:
            kleiner.append(element)
        else:
            groesser.append(element)

    return quicksort(kleiner) + [pivot] + quicksort(groesser)


werte = [8, 3, 10, 1, 6]
print(quicksort(werte))

Quicksort ist in der Praxis oft sehr schnell. Der ungünstige Fall kann aber auftreten, wenn das Pivot-Element schlecht gewählt wird.

Sortieralgorithmen vergleichen

Algorithmus	Grundidee	Vorteil	Grenze
Selection Sort	kleinstes Element suchen und nach vorne tauschen	leicht verständlich	viele Vergleiche
Insertion Sort	Elemente in sortierten Bereich einfügen	gut bei fast sortierten Daten	bei großen unsortierten Listen langsam
Bubble Sort	benachbarte Elemente vergleichen und tauschen	sehr gut sichtbar und nachvollziehbar	bei großen Listen ineffizient
Quicksort	Pivot wählen und rekursiv aufteilen	im Durchschnitt sehr effizient	im Worst Case quadratisch

Wichtig

Ein Algorithmus kann didaktisch gut geeignet sein, obwohl er praktisch nicht der effizienteste ist. Bubble Sort ist leicht zu verstehen, wird aber für große Datenmengen selten bevorzugt.

Komplexitätsklassen

Bei Algorithmen interessiert nicht nur, wie viele Schritte sie bei einer bestimmten Liste brauchen. Wichtiger ist oft die Frage:

Wie wächst der Aufwand, wenn die Datenmenge größer wird?

Dafür verwendet man sogenannte Komplexitätsklassen. Sie beschreiben das Wachstum des Aufwands in Abhängigkeit von der Problemgröße n.

Typische Komplexitätsklassen sind:

Schreibweise	Bezeichnung	Bedeutung
O(1)	konstant	Der Aufwand bleibt ungefähr gleich, egal wie groß n ist.
O(log n)	logarithmisch	Der Aufwand wächst sehr langsam.
O(n)	linear	Der Aufwand wächst ungefähr proportional zur Datenmenge.
O(n log n)	linearithmisch / quasilinear	Der Aufwand wächst schneller als linear, aber deutlich langsamer als quadratisch.
O(n²)	quadratisch	Der Aufwand wächst stark, weil häufig verschachtelte Vergleiche nötig sind.
O(2ⁿ)	exponentiell	Der Aufwand wächst extrem stark mit jedem zusätzlichen Element.
O(n!)	faktoriell	Der Aufwand wächst noch stärker; typisch bei vollständigem Durchprobieren vieler Anordnungen.

Merke

Komplexitätsklassen beschreiben nicht die exakte Laufzeit in Sekunden, sondern das Wachstum des Aufwands bei größer werdenden Datenmengen.

Abb.: Übersicht über typische Komplexitätsklassen der O-Notation. Die Achse „relativer Aufwand“ ist normiert; die Grafik zeigt daher das Wachstumsverhalten, nicht konkrete Sekundenwerte. Eigene Darstellung.

Beispiele für Komplexitätsklassen

Konstanter Aufwand: O(1)

Der Aufwand bleibt ungefähr gleich, egal wie groß die Datenmenge ist.

Beispiel:

erstes_element = liste[0]

Der Zugriff auf ein bestimmtes Listenelement über seinen Index benötigt nicht mehr Schritte, nur weil die Liste größer wird.

Logarithmischer Aufwand: O(log n)

Der Aufwand wächst sehr langsam.

Beispiel:

Binäre Suche

Bei jedem Schritt wird der Suchbereich halbiert.

1 000 Elemente      → ungefähr 10 Vergleiche
1 000 000 Elemente  → ungefähr 20 Vergleiche

Merke

O(log n) ist sehr effizient, weil bei jedem Schritt ein großer Teil des Problems ausgeschlossen wird.

Linearer Aufwand: O(n)

Der Aufwand wächst ungefähr proportional zur Anzahl der Elemente.

Beispiel:

Lineare Suche

Im schlechtesten Fall wird jedes Element einmal geprüft.

10 Elemente     → bis zu 10 Vergleiche
100 Elemente    → bis zu 100 Vergleiche
10 000 Elemente → bis zu 10 000 Vergleiche

Linearithmischer Aufwand: O(n log n)

Der Aufwand wächst etwas schneller als linear, aber deutlich langsamer als quadratisch.

Typische Beispiele:

• Quicksort im Durchschnitt,
• Mergesort,
• Heapsort.

Bei solchen Verfahren wird die Datenmenge oft sinnvoll in Teilprobleme zerlegt, die anschließend effizient bearbeitet werden.

Quadratischer Aufwand: O(n²)

Der Aufwand wächst stark, weil häufig viele Elemente mit vielen anderen Elementen verglichen werden.

Typische Beispiele:

• Selection Sort,
• Bubble Sort,
• Insertion Sort im durchschnittlichen und schlechten Fall.

10 Elemente     → ungefähr 100 als Größenordnung
100 Elemente    → ungefähr 10 000 als Größenordnung
10 000 Elemente → ungefähr 100 000 000 als Größenordnung

Wichtig

Quadratische Algorithmen können bei kleinen Datenmengen völlig ausreichend sein, werden aber bei großen Datenmengen schnell problematisch.

Komplexität von Such- und Sortierverfahren

Verfahren	Best Case	Average Case	Worst Case	Kurzbegründung
Lineare Suche	O(1)	O(n)	O(n)	Im besten Fall steht das Element vorne, sonst muss viel geprüft werden.
Binäre Suche	O(1)	O(log n)	O(log n)	Der Suchbereich wird immer halbiert.
Selection Sort	O(n²)	O(n²)	O(n²)	Das kleinste Element muss wiederholt im Restbereich gesucht werden.
Bubble Sort	O(n) mit Abbruch	O(n²)	O(n²)	Bei bereits sortierter Liste kann früh abgebrochen werden; sonst viele Vergleiche.
Insertion Sort	O(n)	O(n²)	O(n²)	Bei fast sortierten Daten günstig, sonst viele Verschiebungen.
Quicksort	O(n log n)	O(n log n)	O(n²)	Gute Pivot-Aufteilung ist effizient; schlechte Pivot-Wahl führt zu ungünstiger Rekursion.

Strategie

Wenn du Komplexitätsklassen erklärst, nenne immer auch den Kontext:

• Geht es um Suchen oder Sortieren?
• Ist die Liste sortiert oder unsortiert?
• Wird einmal gesucht oder sehr oft?
• Geht es um kleine oder große Datenmengen?
• Wird der Best Case, Worst Case oder Average Case betrachtet?

Quicksort und O(n log n)

Quicksort arbeitet im Durchschnitt sehr effizient, weil die Liste durch das Pivot-Element in kleinere Teillisten aufgeteilt wird.

Wenn das Pivot-Element die Liste ungefähr halbiert, entstehen ungefähr log₂(n) Rekursionsebenen. Auf jeder Ebene müssen die Elemente mit dem Pivot verglichen werden.

Daher ergibt sich im günstigen und durchschnittlichen Fall ungefähr:

n · log₂(n)

also:

O(n log n)

Im ungünstigen Fall wird das Pivot-Element aber sehr schlecht gewählt. Wenn es immer das kleinste oder größte Element ist, entsteht jedes Mal eine fast gleich große Restliste. Dann ähnelt der Aufwand wieder einer quadratischen Struktur:

O(n²)

Merke

Quicksort ist im Durchschnitt sehr schnell, kann aber im schlechtesten Fall deutlich ineffizienter werden.

Vergleich von n log n und n²

Der Unterschied zwischen O(n log n) und O(n²) wird bei großen Datenmengen besonders deutlich. Bei kleinen Datenmengen können konstante Faktoren und Implementierungsdetails den praktischen Vergleich zunächst überlagern.

Beispielhaft:

Problemgröße n	n log₂(n) ungefähr	n²
10	33	100
100	664	10 000
1 000	9 966	1 000 000
10 000	132 877	100 000 000

Wichtig

Bei kleinen Datenmengen wirken Sortierverfahren oft ähnlich schnell. Bei großen Datenmengen entscheiden Komplexitätsklassen darüber, ob ein Verfahren praktisch sinnvoll ist.

Abb.: Detailansicht bei kleinen Datenmengen. Der konstante Faktor bei 4 · n · log₂(n) verdeutlicht, dass konkrete Implementierungen trotz besserer Komplexitätsklasse anfangs mehr Aufwand verursachen können. Eigene Darstellung.

Elementaroperationen beim Sortieren

Beim Sortieren kann man verschiedene Arten von Arbeitsschritten zählen.

Wichtige Elementaroperationen sind:

Operation	Bedeutung
Vergleich	Zwei Werte werden verglichen.
Verschiebung	Ein Wert wird an eine andere Stelle verschoben.
Vertauschung	Zwei Werte tauschen ihre Plätze.

Eine Vertauschung ist aufwendiger als eine einfache Verschiebung, weil dafür mehrere Zuweisungen nötig sind.

Beispiel für eine Vertauschung:

zwischenspeicher = liste[i]
liste[i] = liste[i + 1]
liste[i + 1] = zwischenspeicher

In Python kann man das kürzer schreiben:

liste[i], liste[i + 1] = liste[i + 1], liste[i]

Merke

Effizienz kann man nicht nur über die Anzahl der Schleifendurchläufe betrachten. Auch Vergleiche, Verschiebungen und Vertauschungen verursachen Aufwand.

Sortieren mit Karten verstehen

Sortieralgorithmen lassen sich gut mit Karten erklären.

Für Selection Sort:

1. Lege mehrere Zahlenkarten nebeneinander.
2. Suche das kleinste Element im unsortierten Bereich.
3. Tausche es nach vorne.
4. Markiere den sortierten Bereich.
5. Wiederhole das Vorgehen.

Für Insertion Sort:

1. Betrachte die erste Karte als sortierten Bereich.
2. Nimm die nächste Karte.
3. Füge sie an der richtigen Stelle in den sortierten Bereich ein.
4. Wiederhole das Vorgehen.

Für Bubble Sort:

1. Vergleiche immer zwei benachbarte Karten.
2. Vertausche sie, wenn sie falsch liegen.
3. Gehe bis zum Ende der Reihe.
4. Wiederhole den Vorgang, bis keine Vertauschung mehr nötig ist.

Für Quicksort:

1. Wähle eine Karte als Pivot.
2. Lege kleinere Werte links ab.
3. Lege größere Werte rechts ab.
4. Wiederhole das Vorgehen für die Teilgruppen.
5. Setze die sortierten Gruppen wieder zusammen.

Strategie

Wenn du einen Algorithmus mit Karten erklärst, sprich jeden Schritt laut mit: Was wird verglichen? Warum wird getauscht? Welcher Bereich ist bereits erledigt?

Algorithmen bewerten

Beim Vergleichen von Algorithmen helfen Leitfragen:

• Funktioniert der Algorithmus für alle gültigen Eingaben?
• Welche Voraussetzungen braucht er?
• Wie viele Schritte benötigt er ungefähr?
• Wie verhält er sich im Best Case, Worst Case und Average Case?
• Zu welcher Komplexitätsklasse gehört er?
• Ist er leicht zu verstehen?
• Ist er leicht zu programmieren?
• Ist er für große Datenmengen geeignet?
• Muss vorher sortiert oder vorbereitet werden?
• Gibt es einen Zielkonflikt zwischen Effizienz und Verständlichkeit?

Merke

Die Wahl eines Algorithmus hängt vom Problem, von der Datenmenge, von den Voraussetzungen und vom praktischen Einsatz ab.

Effizienz kritisch reflektieren

Effizienz ist nicht nur eine technische Frage.

Wenn Programme mit sehr großen Datenmengen arbeiten, können ineffiziente Algorithmen Folgen haben:

• längere Wartezeiten,
• höhere Serverlast,
• mehr Energieverbrauch,
• höhere Kosten,
• schlechtere Nutzbarkeit,
• langsamere Auswertung wichtiger Daten,
• ökologische Auswirkungen durch höheren Ressourcenverbrauch.

Gleichzeitig ist der effizienteste Algorithmus nicht immer automatisch die beste Wahl.

Manchmal sind andere Kriterien wichtig:

• Verständlichkeit,
• Wartbarkeit,
• Nachvollziehbarkeit,
• Fehleranfälligkeit,
• Fairness,
• Transparenz.

Wichtig

Ein sehr effizienter Algorithmus kann schwer verständlich sein. Ein einfacher Algorithmus kann leichter überprüfbar sein. In der Praxis muss man oft zwischen Effizienz und Nachvollziehbarkeit abwägen.

Typische Missverständnisse

„Wenn ein Algorithmus funktioniert, ist er automatisch gut.“

Nicht unbedingt. Er kann korrekt sein, aber bei großen Datenmengen viel zu langsam werden.

„Binäre Suche ist immer besser als lineare Suche.“

Nicht immer. Binäre Suche braucht eine sortierte Liste. Bei sehr kleinen oder einmaligen Suchvorgängen kann lineare Suche einfacher und ausreichend sein.

„Sortieren lohnt sich immer.“

Nein. Sortieren kostet selbst Aufwand. Es lohnt sich vor allem, wenn danach oft gesucht oder weiterverarbeitet wird.

„Bubble Sort ist schlecht, weil er langsam ist.“

Bubble Sort ist für große Listen ineffizient, aber didaktisch sehr nützlich, weil man daran Vergleiche, Vertauschungen und Schleifen gut versteht.

„Quicksort ist immer schnell.“

Quicksort ist oft schnell, kann aber im ungünstigen Fall langsamer werden, wenn die Aufteilung sehr ungleich ist.

„Komplexitätsklassen geben die genaue Laufzeit in Sekunden an.“

Nein. Komplexitätsklassen beschreiben das Wachstum des Aufwands, nicht die konkrete Laufzeit auf einem bestimmten Computer.

Prüfungsvorbereitung

Die folgenden Aufgaben trainieren dieselben Kompetenzen, verwenden aber andere Kontexte, Daten und Beispiele.

📝 Übung: Algorithmus erklären

Erkläre, warum die folgende Handlung als Algorithmus beschrieben werden kann:

Eine App prüft, ob ein eingegebener Rabattcode in einer Liste gültiger Codes vorkommt.

Gehe dabei auf folgende Punkte ein:

1. Eingabe
2. Verarbeitung
3. Ausgabe
4. Eindeutigkeit der Schritte
5. Endlichkeit

Lösungshinweis

Die Eingabe ist der Rabattcode. Die Verarbeitung besteht darin, den Code mit gespeicherten gültigen Codes zu vergleichen. Die Ausgabe ist zum Beispiel gültig oder ungültig.

Die Schritte müssen eindeutig sein, damit klar ist, welcher Code wann geprüft wird. Der Algorithmus ist endlich, wenn die Liste nach einer bestimmten Anzahl von Vergleichen vollständig geprüft wurde.

📝 Übung: Lineare Suche implementieren

Schreibe eine Funktion finde_artikel(liste, artikelnummer), die überprüft, ob eine Artikelnummer in einer Liste vorkommt.

Die Funktion soll True zurückgeben, wenn die Nummer gefunden wurde, sonst False.

Lösung

def finde_artikel(liste, artikelnummer):
    for nummer in liste:
        if nummer == artikelnummer:
            return True

    return False


artikel = [104, 118, 203, 260, 315]

print(finde_artikel(artikel, 203))
print(finde_artikel(artikel, 999))

📝 Übung: Binäre Suche gedanklich durchführen

Gegeben ist die sortierte Liste:

[3, 7, 12, 18, 25, 31, 44, 58, 63]

Gesucht wird 44.

1. Bestimme das mittlere Element.
2. Entscheide, ob links oder rechts weitergesucht wird.
3. Wiederhole den Vorgang, bis der Wert gefunden ist.
4. Notiere alle verglichenen Werte.

Lösung

Startliste:

[3, 7, 12, 18, 25, 31, 44, 58, 63]

Mitte: 25
44 ist größer, also rechts weitersuchen.

Neuer Bereich:

[31, 44, 58, 63]

Mitte ungefähr: 44
gefunden.

Verglichene Werte:

25, 44

📝 Übung: Sortieren oder nicht?

Eine App verwaltet 30 gespeicherte Lieblingssongs. Eine andere App verwaltet 2 Millionen Datensätze.

1. Erkläre, warum lineare Suche bei 30 Songs oft ausreicht.
2. Erkläre, warum bei 2 Millionen Datensätzen andere Strategien sinnvoll werden.
3. Begründe, wann Sortieren vor dem Suchen sinnvoll sein kann.

Lösungshinweis

Bei 30 Songs ist der Aufwand gering. Selbst wenn alle Einträge geprüft werden, ist das meistens unproblematisch.

Bei 2 Millionen Datensätzen kann lineare Suche sehr viele Vergleiche benötigen. Wenn oft gesucht wird, lohnt sich eine sortierte Struktur oder ein anderer effizienter Zugriff.

Sortieren lohnt sich besonders, wenn dieselbe Datenmenge häufig durchsucht wird.

📝 Übung: Selection Sort nachvollziehen

Sortiere die Liste gedanklich mit Selection Sort:

[7, 2, 6, 4]

Notiere nach jedem Durchlauf den Zustand der Liste.

Lösung

Start:

[7, 2, 6, 4]

Erster Durchlauf: kleinstes Element ist 2, Tausch mit 7.

[2, 7, 6, 4]

Zweiter Durchlauf: kleinstes Element im Restbereich ist 4, Tausch mit 7.

[2, 4, 6, 7]

Dritter Durchlauf: 6 ist bereits an der richtigen Stelle.

[2, 4, 6, 7]

📝 Übung: Vertiefung – Insertion Sort nachvollziehen

Sortiere die Liste gedanklich mit Insertion Sort:

[5, 3, 8, 2]

Beschreibe, wie der sortierte Bereich Schritt für Schritt wächst.

Lösung

Start:

[5, 3, 8, 2]

5 gilt als sortierter Bereich.

3 wird vor 5 eingefügt:

[3, 5, 8, 2]

8 bleibt hinter 5:

[3, 5, 8, 2]

2 wird ganz vorne eingefügt:

[2, 3, 5, 8]

📝 Übung: Bubble Sort nachvollziehen

Sortiere die Liste gedanklich mit Bubble Sort:

[6, 2, 9, 4]

Notiere nach jedem vollständigen Durchlauf den Zustand der Liste.

Lösung

Start:

[6, 2, 9, 4]

Erster Durchlauf:

• 6 und 2 tauschen → [2, 6, 9, 4]
• 6 und 9 bleiben → [2, 6, 9, 4]
• 9 und 4 tauschen → [2, 6, 4, 9]

Zweiter Durchlauf:

• 2 und 6 bleiben → [2, 6, 4, 9]
• 6 und 4 tauschen → [2, 4, 6, 9]

Dritter Durchlauf:

• keine Änderung nötig

Sortierte Liste:

[2, 4, 6, 9]

📝 Übung: Quicksort-Prinzip erklären

Gegeben ist die Liste:

[9, 4, 12, 2, 7]

Wähle 9 als Pivot.

1. Teile die übrigen Werte in kleinere und größere Werte auf.
2. Erkläre, wie die Teillisten weiter sortiert werden.
3. Beschreibe das Prinzip „Teile und herrsche“.

Lösung

Pivot:

9

Kleinere Werte:

[4, 2, 7]

Größere Werte:

[12]

Die Teilliste [4, 2, 7] wird wieder nach demselben Prinzip sortiert. Das Problem wird also in kleinere Teilprobleme zerlegt. Danach werden die sortierten Teile zusammengesetzt.

📝 Übung: Komplexitätsklassen zuordnen

Ordne die folgenden Verfahren einer passenden Komplexitätsklasse zu und begründe kurz:

1. Lineare Suche in einer unsortierten Liste
2. Binäre Suche in einer sortierten Liste
3. Bubble Sort
4. Selection Sort
5. Vertiefung: Insertion Sort im durchschnittlichen Fall
6. Quicksort im durchschnittlichen Fall
7. Quicksort im ungünstigen Fall

Lösung

1. Lineare Suche: O(n), weil im schlechtesten Fall jedes Element geprüft wird.
2. Binäre Suche: O(log n), weil der Suchbereich in jedem Schritt halbiert wird.
3. Bubble Sort: O(n²), weil viele benachbarte Vergleiche und Vertauschungen nötig sind.
4. Selection Sort: O(n²), weil wiederholt das kleinste Element im unsortierten Bereich gesucht wird.
5. Vertiefung: Insertion Sort liegt im Durchschnitt bei O(n²), weil häufig viele Verschiebungen nötig sind.
6. Quicksort im Durchschnitt: O(n log n), weil die Liste meist sinnvoll aufgeteilt wird.
7. Quicksort im ungünstigen Fall: O(n²), wenn das Pivot-Element die Liste sehr schlecht aufteilt.

📝 Übung: Wachstum vergleichen

Erkläre, warum ein Algorithmus mit O(n log n) bei großen Datenmengen meist deutlich besser geeignet ist als ein Algorithmus mit O(n²).

Lösungshinweis

Bei O(n²) wächst der Aufwand quadratisch. Verdoppelt sich die Datenmenge, kann sich der Aufwand ungefähr vervierfachen.

Bei O(n log n) wächst der Aufwand deutlich langsamer. Deshalb sind Verfahren wie Quicksort im durchschnittlichen Fall für große Datenmengen meist wesentlich geeigneter als einfache quadratische Sortierverfahren.

Ich kann …

Nach der Wiederholung dieses Themenbereichs solltest du Folgendes können:

• Ich kann erklären, was ein Algorithmus ist.
• Ich kann grundlegende Eigenschaften von Algorithmen nennen und beschreiben.
• Ich kann Determinismus und Determiniertheit unterscheiden.
• Ich kann erklären, was Effizienz bei Algorithmen bedeutet.
• Ich kann das Laufzeitverhalten eines Algorithmus beschreiben.
• Ich kann Best Case, Worst Case und Average Case unterscheiden.
• Ich kann die lineare Suche erklären und an einem Beispiel durchführen.
• Ich kann die binäre Suche erklären und ihre Voraussetzung nennen.
• Ich kann lineare und binäre Suche vergleichen.
• Ich kann beurteilen, wann Sortieren vor dem Suchen sinnvoll ist.
• Ich kann einfache Suchalgorithmen in Python lesen und schreiben.
• Ich kann Selection Sort Schritt für Schritt erklären.
• Ich kann Bubble Sort Schritt für Schritt erklären.
• Ich kann Quicksort als rekursives Teile-und-herrsche-Verfahren beschreiben.
• Ich kann einfache Sortieralgorithmen mit Karten oder Listen demonstrieren.
• Ich kann Code-Tracing bei Schleifen, Bedingungen und Listen durchführen.
• Ich kann Komplexitätsklassen wie O(log n), O(n), O(n log n) und O(n²) unterscheiden.
• Ich kann typische Laufzeitklassen von Such- und Sortierverfahren zuordnen.
• Ich kann begründen, warum O(n log n) bei großen Datenmengen meist günstiger ist als O(n²).
• Ich kann Algorithmen hinsichtlich Verständlichkeit, Korrektheit und Effizienz bewerten.
• Ich kann erklären, warum der passende Algorithmus vom konkreten Anwendungsfall abhängt.
• Ich kann gesellschaftliche, wirtschaftliche und ökologische Folgen ineffizienter Algorithmen reflektieren.

Mini-Check

Beantworte zum Abschluss kurz:

1. Welche Eigenschaften sollte ein Algorithmus besitzen?
2. Was ist der Unterschied zwischen Determinismus und Determiniertheit?
3. Wie funktioniert lineare Suche grundsätzlich?
4. Welche Voraussetzung braucht binäre Suche?
5. Warum ist binäre Suche bei großen sortierten Listen effizienter als lineare Suche?
6. Was bedeuten best case, average case und worst case?
7. Wie funktioniert Bubble Sort grundsätzlich?
8. Wie funktioniert Quicksort grundsätzlich?
9. Warum kann die Wahl des Pivot-Elements bei Quicksort wichtig sein?
10. Welche Komplexitätsklasse passt typischerweise zu Bubble Sort im schlechten Fall?
11. Welche Komplexitätsklasse passt typischerweise zu einem guten Quicksort-Verlauf?
12. Wann kann es sinnvoll sein, vor dem Suchen zuerst zu sortieren?
13. Warum ist Effizienz auch gesellschaftlich oder ökologisch relevant?

Kurzlösungen

1. Er sollte eindeutig, ausführbar, endlich und nachvollziehbar sein und Eingaben zu Ausgaben verarbeiten.
2. Determinismus betrifft die Eindeutigkeit jedes nächsten Schritts; Determiniertheit bedeutet, dass bei gleicher Eingabe dasselbe Ergebnis entsteht.
3. Die Liste wird Element für Element durchsucht, bis der Wert gefunden wird oder die Liste endet.
4. Die Liste muss sortiert sein.
5. Der Suchbereich wird in jedem Schritt ungefähr halbiert.
6. Best case: günstigster Fall; average case: durchschnittlicher Fall; worst case: ungünstigster Fall.
7. Benachbarte Elemente werden verglichen und bei falscher Reihenfolge vertauscht; große Elemente wandern schrittweise nach hinten.
8. Ein Pivot wird gewählt, die Liste wird in kleinere und größere Elemente geteilt und diese Teile werden weiter sortiert.
9. Ein ungünstiges Pivot kann sehr ungleich große Teilprobleme erzeugen und die Laufzeit verschlechtern.
10. O(n²).
11. O(n log n).
12. Bei vielen Suchanfragen auf derselben Datenmenge, besonders wenn die Datenmenge groß ist.
13. Langsame oder verschwenderische Algorithmen kosten Zeit, Energie und Ressourcen und können digitale Systeme unzuverlässig machen.