Sortieralgorithmen in Python: Insertion Sort vs. Merge Sort – Eine praktische Analyse für ECM1414

Sortieralgorithmen in Python: Insertion Sort vs. Merge Sort – Eine praktische Analyse

Sortieralgorithmen sind ein zentrales Thema in der Datenstrukturen und Algorithmen Vorlesung (ECM1414). In diesem Tutorial lernst du, wie du Insertion Sort und Merge Sort in Python implementierst, die Anzahl der Vergleiche zählst und daraus Rückschlüsse auf die Komplexität ziehst. Wir nutzen aktuelle Beispiele aus der Welt der KI und des Gamings, um die Konzepte greifbar zu machen.

Warum Sortieralgorithmen wichtig sind

Stell dir vor, du entwickelst eine KI für ein Echtzeit-Strategiespiel wie StarCraft II. Die KI muss Einheiten nach Priorität sortieren – das geschieht mit Sortieralgorithmen. Oder denk an eine Finanz-App, die Aktienkurse sortiert. Die Wahl des Algorithmus entscheidet über Geschwindigkeit und Effizienz. Genau das untersuchen wir hier.

Grundlagen der Implementierung

Wir beginnen mit der lessThan-Funktion, die einen globalen Zähler für Vergleiche erhöht. Das ist essenziell für die Komplexitätsanalyse.

comparisons = 0

def lessThan(x, y):
    global comparisons
    comparisons += 1
    return x < y

Insertion Sort (Lineare Insertion)

Insertion Sort funktioniert wie das Sortieren von Spielkarten: Man nimmt eine Karte nach der anderen und fügt sie an die richtige Stelle ein.

def insert(item, sorted_list):
    i = 0
    while i < len(sorted_list) and lessThan(sorted_list[i], item):
        i += 1
    sorted_list.insert(i, item)

def insertSort(lst):
    sorted_list = []
    for item in lst:
        insert(item, sorted_list)
    return sorted_list

Im besten Fall (bereits sortierte Liste) macht Insertion Sort nur n Vergleiche. Im schlechtesten Fall (umgekehrt sortiert) sind es etwa n²/2 Vergleiche. Das ist vergleichbar mit dem Best-Case und Worst-Case Szenario.

Merge Sort (Rekursives Mergesort)

Merge Sort teilt die Liste rekursiv in zwei Hälften, sortiert diese und fügt sie zusammen. Das ist wie bei einem Turnierbaum: Zuerst werden die Spiele (Teillisten) ausgetragen, dann die Ergebnisse gemischt.

def split(lst, left, right):
    mid = len(lst) // 2
    left.extend(lst[:mid])
    right.extend(lst[mid:])

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if lessThan(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def mergeSort(lst):
    if len(lst) <= 1:
        return lst
    left, right = [], []
    split(lst, left, right)
    left = mergeSort(left)
    right = mergeSort(right)
    return merge(left, right)

Merge Sort hat immer eine Komplexität von O(n log n) – unabhängig von der Eingabe. Das ist ideal für große Datenmengen, wie sie in Big Data Anwendungen vorkommen.

Vergleich der Komplexität

Mit der listdemo-Funktion generierst du Zufallslisten und zählst die Vergleiche:

import random

def randomList(n):
    return [random.randint(-10*n, 10*n) for _ in range(n)]

def listdemo(n):
    global comparisons
    lst = randomList(n)
    print("Unsorted:", lst[:10], "...")
    comparisons = 0
    sorted_insert = insertSort(lst[:])
    print("Insertion Sort comparisons:", comparisons)
    comparisons = 0
    sorted_merge = mergeSort(lst[:])
    print("Merge Sort comparisons:", comparisons)

Empirische Analyse für n = 200, 400, 600, 800, 1000

Für jedes n generierst du 5 Zufallslisten und notierst die Vergleiche. Zusätzlich testest du sortierte und umgekehrt sortierte Listen. Die Ergebnisse zeigen: Insertion Sort explodiert bei großen n, während Merge Sort stabil bleibt. Hier eine Beispieltabelle (fiktive Werte):

Die Daten bestätigen die Theorie: Insertion Sort hat quadratische Komplexität (a ≈ 0.5), Merge Sort linearithmische (b ≈ 1.0).

Best-Case und Worst-Case

Insertion Sort brilliert bei bereits sortierten Listen (Best-Case: O(n)), während Merge Sort immer O(n log n) benötigt. Das ist wichtig für Anwendungen, bei denen die Daten oft vorsortiert sind, z.B. in Echtzeitsystemen.

Trends und Bezug zur Praxis

In der KI-Entwicklung werden oft große Datensätze sortiert – Merge Sort ist hier die erste Wahl. Im Gaming (z.B. Ranglisten) kann Insertion Sort nützlich sein, wenn nur wenige neue Spieler hinzukommen. Auch in Finanz-Apps werden Sortieralgorithmen genutzt, um Kurse zu ordnen.

Fazit

Die praktische Analyse zeigt: Die theoretische Komplexität spiegelt sich in der Praxis wider. Für ECM1414 lernst du nicht nur Algorithmen, sondern auch, wie du sie bewertest. Nutze diese Erkenntnisse für deine Projekte – ob in der Datenwissenschaft oder Softwareentwicklung.