Algorithmen – Suchen und Sortieren

Das lernst du

Verstehen, was ein Algorithmus ist
Lineare und binäre Suche vergleichen
Einen Sortieralgorithmus selbst programmieren

Was ist ein Algorithmus?

Ein Algorithmus ist eine genaue Schritt-für-Schritt-Anleitung, die ein Problem löst – wie ein Kochrezept, nur für Computer. Für dasselbe Problem gibt es oft mehrere Algorithmen, und manche sind viel schneller als andere.

Suchen: Seite für Seite …

Die einfachste Suche schaut sich jedes Element der Reihe nach an. Das heißt lineare Suche:

def lineare_suche(liste, ziel):
    for i in range(len(liste)):
        if liste[i] == ziel:
            return i
    return -1


print(lineare_suche([7, 3, 9, 4], 9))

Bei einer Million Einträgen braucht sie im schlimmsten Fall eine Million Vergleiche.

… oder wie im Wörterbuch

Wenn die Liste sortiert ist, geht es viel schneller: Schau in die Mitte. Ist der gesuchte Wert größer, kann er nur in der rechten Hälfte sein – die linke Hälfte fällt komplett weg. Das ist die binäre Suche. Jeder Schritt halbiert die Liste:

anzahl = 1_000_000
schritte = 0
while anzahl > 1:
    anzahl //= 2
    schritte += 1
print("Eine Million Einträge – höchstens", schritte, "Schritte")

Statt einer Million Vergleiche reichen etwa 20!

Sortieren mit Bubble Sort

Python hat zwar sorted(), aber wie funktioniert Sortieren eigentlich? Der einfachste Algorithmus heißt Bubble Sort: Vergleiche immer zwei Nachbarn und tausche sie, wenn sie falsch herum stehen. Nach jeder Runde ist die größte Zahl ganz hinten „hochgeblubbert“:

zahlen = [5, 1, 4, 2]
for runde in range(len(zahlen)):
    for i in range(len(zahlen) - 1):
        if zahlen[i] > zahlen[i + 1]:
            zahlen[i], zahlen[i + 1] = zahlen[i + 1], zahlen[i]   # tauschen
    print("Nach Runde", runde + 1, ":", zahlen)

Der Trick zum Tauschen – a, b = b, a – funktioniert dank Tupeln in einer einzigen Zeile.

Gut zu wissen: Bubble Sort ist schön einfach, aber langsam. Pythons eigenes sorted() benutzt einen viel klügeren Algorithmus namens Timsort – benannt nach Tim Peters, der ihn 2002 für Python erfunden hat.

Kurz-Check

Wie viele Schritte braucht die binäre Suche höchstens bei 16 Einträgen? Was gibt dieses Programm aus?

n = 16
schritte = 0
while n > 1:
    n //= 2
    schritte += 1
print(schritte)

Deine Aufgabe

Jetzt bist du dran

Programmiere zwei Klassiker selbst – ohne sorted(), .sort() oder .index(). binaere_suche(liste, ziel) sucht in einer sortierten Liste und gibt die Position von ziel zurück (oder -1, wenn es nicht vorkommt). bubble_sort(liste) gibt eine neue, aufsteigend sortierte Liste zurück und lässt die alte unverändert.

def binaere_suche(liste, ziel):
    pass


def bubble_sort(liste):
    pass


print(binaere_suche([2, 5, 8, 12, 16, 23], 12))
print(bubble_sort([5, 1, 4, 2, 8]))

Denkanstoß
Merk dir links und rechts. Schau in die Mitte – ist der Wert dort zu klein, such rechts weiter, sonst links.
Welcher Befehl hilft?
Die Schleife läuft, solange links <= rechts ist. Danach return -1.
Kopiere die Liste zuerst mit list(liste). Vergleiche dann immer zwei Nachbarn und tausche sie, wenn sie falsch herum stehen.

Lückencode – ergänze die ___

                        def binaere_suche(liste, ziel):
    links, rechts = ___
    while ___:
        mitte = ___
        if ___:
            return ___
        if ___:
            links = ___
        else:
            rechts = ___
    return ___


def bubble_sort(liste):
    zahlen = ___
    for runde in ___:
        for i in ___:
            if ___:
                ___
    return ___


print(binaere_suche([2, 5, 8, 12, 16, 23], 12))
print(bubble_sort([5, 1, 4, 2, 8]))

Ohne Hinweise gelöst gibt es einen ⭐ auf deiner Fortschrittsseite.

Lösung anzeigen

Versuch es erst selbst – aus Fehlern lernt man am meisten. Hier ist eine mögliche Lösung:

def binaere_suche(liste, ziel):
    links, rechts = 0, len(liste) - 1
    while links <= rechts:
        mitte = (links + rechts) // 2
        if liste[mitte] == ziel:
            return mitte
        if liste[mitte] < ziel:
            links = mitte + 1
        else:
            rechts = mitte - 1
    return -1


def bubble_sort(liste):
    zahlen = list(liste)
    for runde in range(len(zahlen)):
        for i in range(len(zahlen) - 1 - runde):
            if zahlen[i] > zahlen[i + 1]:
                zahlen[i], zahlen[i + 1] = zahlen[i + 1], zahlen[i]
    return zahlen


print(binaere_suche([2, 5, 8, 12, 16, 23], 12))
print(bubble_sort([5, 1, 4, 2, 8]))