Informatik II — Übungslektionen

Heutiges Programm

Verbesserter Insertion Sort

Binärer Insertion Sort

Asymptotische Laufzeit Rekursiver Funktionen

Θ-Notation für rekursive Funktionen

Divide & Conquer Sortieralgorithmen

Merge Sort, Natürlicher Mergesort

Gruppenübung

Timsort

Hausaufgaben

Übung 6: Search and Sort

Verbesserter Insertion Sort

Letztes Mal: Insertion Sort

Sortiere [5, 2, 8, 4, 1]:

Start:

i = 1:

i = 2:

i = 3:

i = 4:

Schleifeninvariante

Vor Iteration i sind Elemente in li[:i] sortiert.

Bei Iteration i, das i-te Element an der korrekten Position in die sortierte Teilliste li[:i] einfügen.

Wiederholen bis das gesamte Array sortiert ist (i = n).

Letztes Mal: Insertion Sort

# Input:  Array A = (A[1], ..., A[n]), n >= 0
# Output: Sortiertes Array A

def insertion_sort(A):
    for i in range(1, len(A)):
        j = i
        while j > 0 and A[j-1] > A[j]:
            A[j], A[j-1] = A[j-1], A[j]
            j = j - 1

Quiz

Anzahl Vergleiche im schlechtesten Fall?

Quiz

Anzahl Vertauschungen im schlechtesten Fall?

Frage: Wie können wir die Anzahl Vergleiche für den schlechtesten Fall verbessern?

Binärer Insertion Sort

Idee: Verwende binäre Suche statt linearer Suche, um die Einfügeposition zu finden.

# Input:  Array A = (A[1], ..., A[n]), n >= 0
# Output: Sortiertes Array A

def binary_insertion_sort(A):
    for i in range(1, len(A)):
        x = A[i]
        p = BinarySearchIndex(A, 0, i-1, x)
        for j in range(i-1, p-1, -1):
            A[j+1] = A[j]
        A[p] = x

Quiz

Anzahl Vergleiche im schlechtesten Fall?

Quiz

Anzahl Kopiervorgänge im schlechtesten Fall?

Asymptotische Laufzeit Rekursiver Funktionen

Übung 1

Geben Sie die Anzahl Aufrufe der Funktion f abhängig von n in der Θ-Notation für den untenstehenden Beispiel an. Kürzen Sie ihr Ergebnis soweit wie möglich. Geben Sie eine kurze Begründung.

Quiz

# pre: n is an integer >= 0
def g(n):
    count = 0
    while n // (2 ** count) >= 1:
        f()
        count += 1

Übung 2

Geben Sie die Anzahl Aufrufe der Funktion f abhängig von n in der Θ-Notation an. Kürzen Sie ihr Ergebnis soweit wie möglich.

Quiz

# pre: n is an integer >= 0
def g(n):
    if n >= 1:
        f()
        g(n // 2)

Übung 3

Geben Sie die Anzahl Aufrufe der Funktion f abhängig von n in der Θ-Notation an. Kürzen Sie ihr Ergebnis soweit wie möglich.

Quiz

# pre: n is an integer >= 0
def g(n):
    if n >= 1:
        for i in range(n):
            f()
        g(n // 2)

Übung 4

Geben Sie die Anzahl Aufrufe der Funktion f abhängig von n in der Θ-Notation an. Kürzen Sie ihr Ergebnis soweit wie möglich.

Quiz

# pre: n is an integer >= 0
def g(n):
    if n >= 1:
        for i in range(n):
            f()
        g(n // 2)
        g(n // 2)

Rekursive Snippets: Verifikation

Überprüfe die Analysen empirisch.

import math

def count_uebung1(n):
    count, c = 0, 0
    while n // (2 ** c) >= 1:
        count += 1
        c += 1
    return count

def count_uebung2(n):
    if n >= 1:
        return 1 + count_uebung2(n // 2)
    return 0

def count_uebung3(n):
    if n >= 1:
        return n + count_uebung3(n // 2)
    return 0

def count_uebung4(n):
    if n >= 1:
        return n + 2 * count_uebung4(n // 2)
    return 0

print(f"{'n':>6} | {'Ü1':>4} {'logn':>5} | {'Ü2':>4} {'logn':>5} | {'Ü3':>6} {'2n':>6} | {'Ü4':>8} {'nlogn':>8}")
print("-" * 72)
for n in [16, 64, 256, 1024, 4096]:
    logn = int(math.log2(n)) + 1
    print(f"{n:>6} | {count_uebung1(n):>4} {logn:>5} | {count_uebung2(n):>4} {logn:>5} | {count_uebung3(n):>6} {2*n:>6} | {count_uebung4(n):>8} {n*logn:>8}")

import math

def count_uebung1(n):
    count, c = 0, 0
    while n // (2 ** c) >= 1:
        count += 1
        c += 1
    return count

def count_uebung2(n):
    if n >= 1:
        return 1 + count_uebung2(n // 2)
    return 0

def count_uebung3(n):
    if n >= 1:
        return n + count_uebung3(n // 2)
    return 0

def count_uebung4(n):
    if n >= 1:
        return n + 2 * count_uebung4(n // 2)
    return 0

print(f"{'n':>6} | {'Ü1':>4} {'logn':>5} | {'Ü2':>4} {'logn':>5} | {'Ü3':>6} {'2n':>6} | {'Ü4':>8} {'nlogn':>8}")
print("-" * 72)
for n in [16, 64, 256, 1024, 4096]:
    logn = int(math.log2(n)) + 1
    print(f"{n:>6} | {count_uebung1(n):>4} {logn:>5} | {count_uebung2(n):>4} {logn:>5} | {count_uebung3(n):>6} {2*n:>6} | {count_uebung4(n):>8} {n*logn:>8}")

Divide & Conquer Sortieralgorithmen

Merge

Zwei sortierte Arrays werden zu einem sortierten Array zusammengeführt.

Eingabe: zwei sortierte Arrays

Vergleiche jeweils die kleinsten Elemente und nimm das kleinere:

1 < 2 → nimm 1 (a1) | 4 > 2 → nimm 2 (a2) | 4 > 3 → nimm 3 (a2)

4 < 10 → nimm 4 (a1) | 7 < 10 → nimm 7 (a1) | 9 < 10 → nimm 9 (a1)

16 > 10 → nimm 10 (a2) | 16 > 11 → nimm 11 (a2) | 16 > 12 → nimm 12 (a2)

Rest: nimm 16 (a1)

Ergebnis:

Algorithmus `merge`

def merge(a1, a2):
    b, i, j = [], 0, 0
    while i < len(a1) and j < len(a2):
        if a1[i] < a2[j]:
            b.append(a1[i])
            i += 1
        else:
            b.append(a2[j])
            j += 1
    b += a1[i:]
    b += a2[j:]
    return b

# Beispiel
a1 = [1, 4, 7, 9, 16]
a2 = [2, 3, 10, 11, 12]
print("a1:   ", a1)
print("a2:   ", a2)
print("merge:", merge(a1, a2))

def merge(a1, a2):
    b, i, j = [], 0, 0
    while i < len(a1) and j < len(a2):
        if a1[i] < a2[j]:
            b.append(a1[i])
            i += 1
        else:
            b.append(a2[j])
            j += 1
    b += a1[i:]
    b += a2[j:]
    return b

# Beispiel
a1 = [1, 4, 7, 9, 16]
a2 = [2, 3, 10, 11, 12]
print("a1:   ", a1)
print("a2:   ", a2)
print("merge:", merge(a1, a2))

Algorithmus `merge_sort`

def merge(a1, a2):
    b, i, j = [], 0, 0
    while i < len(a1) and j < len(a2):
        if a1[i] < a2[j]:
            b.append(a1[i])
            i += 1
        else:
            b.append(a2[j])
            j += 1
    b += a1[i:]
    b += a2[j:]
    return b

def merge_sort(a):
    if len(a) <= 1:
        return a
    else:
        sorted_a1 = merge_sort(a[:len(a) // 2])
        sorted_a2 = merge_sort(a[len(a) // 2:])
        return merge(sorted_a1, sorted_a2)

# Beispiel
data = [5, 6, 2, 4, 8, 3, 9, 7, 1]
print("Input: ", data)
print("Sorted:", merge_sort(data))

def merge(a1, a2):
    b, i, j = [], 0, 0
    while i < len(a1) and j < len(a2):
        if a1[i] < a2[j]:
            b.append(a1[i])
            i += 1
        else:
            b.append(a2[j])
            j += 1
    b += a1[i:]
    b += a2[j:]
    return b

def merge_sort(a):
    if len(a) <= 1:
        return a
    else:
        sorted_a1 = merge_sort(a[:len(a) // 2])
        sorted_a2 = merge_sort(a[len(a) // 2:])
        return merge(sorted_a1, sorted_a2)

# Beispiel
data = [5, 6, 2, 4, 8, 3, 9, 7, 1]
print("Input: ", data)
print("Sorted:", merge_sort(data))

Natürlicher 2-Wege Mergesort

Idee: Nutze bereits existierende sortierte Teilfolgen (Runs) statt immer in der Mitte zu teilen.

Runs identifizieren (aufsteigende Teilfolgen):

Pass 1: Benachbarte Run-Paare mergen

Pass 2: Weiter mergen

Pass 3: Fertig!

Algorithmus `NaturalMergesort`(A)

Input: Array A der Länge n > 0, Output: Array A sortiert

def merge_inplace(A, l, m, r):
    left = A[l:m+1]
    right = A[m+1:r+1]
    i = j = 0
    k = l
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            A[k] = left[i]; i += 1
        else:
            A[k] = right[j]; j += 1
        k += 1
    while i < len(left):
        A[k] = left[i]; i += 1; k += 1
    while j < len(right):
        A[k] = right[j]; j += 1; k += 1

def NaturalMergesort(A):
    l = -1
    while l != 0:
        r = 0
        while r < len(A) - 1:
            l = r
            m = l
            while m < len(A) - 1 and A[m+1] >= A[m]:
                m = m + 1
            if m < len(A) - 1:
                r = m + 1
                while r < len(A) - 1 and A[r+1] >= A[r]:
                    r = r + 1
                merge_inplace(A, l, m, r)
            else:
                r = len(A) - 1
            r += 1
        print(f"  Pass: {A}")

data = [5, 6, 2, 4, 8, 3, 9, 7, 1]
print(f"Input:  {data}")
NaturalMergesort(data)
print(f"Output: {data}")

def merge_inplace(A, l, m, r):
    left = A[l:m+1]
    right = A[m+1:r+1]
    i = j = 0
    k = l
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            A[k] = left[i]; i += 1
        else:
            A[k] = right[j]; j += 1
        k += 1
    while i < len(left):
        A[k] = left[i]; i += 1; k += 1
    while j < len(right):
        A[k] = right[j]; j += 1; k += 1

def NaturalMergesort(A):
    l = -1
    while l != 0:
        r = 0
        while r < len(A) - 1:
            l = r
            m = l
            while m < len(A) - 1 and A[m+1] >= A[m]:
                m = m + 1
            if m < len(A) - 1:
                r = m + 1
                while r < len(A) - 1 and A[r+1] >= A[r]:
                    r = r + 1
                merge_inplace(A, l, m, r)
            else:
                r = len(A) - 1
            r += 1
        print(f"  Pass: {A}")

data = [5, 6, 2, 4, 8, 3, 9, 7, 1]
print(f"Input:  {data}")
NaturalMergesort(data)
print(f"Output: {data}")

Gruppenübung

Gruppenübung: Timsort

https://expert.ethz.ch/enrolled/SS26/mavt2/codeExamples

Timsort, eine Kombination aus Insertion Sort und Merge Sort, ist der Standard-Sortieralgorithmus in Python. Mehr dazu in der Aufgabenbeschreibung auf Code Expert.

Timsort: Überblick

Timsort kombiniert die Stärken von Insertion Sort (schnell für kleine/fast-sortierte Daten) und Merge Sort (garantiert O(n log n)):

Teile das Array in kleine Blöcke (Runs)
Sortiere jeden Run mit Insertion Sort
Merge die Runs mit einem optimierten Merge-Verfahren

Hausaufgaben

Übung 6: Search and Sort

Eierwerfen
Vergleich von Sortieralgorithmen
Verbesserter Insertion Sort
Invarianten der Suchalgorithmen

Abgabedatum: Montag 06.04.2026, 20:00 CET

KEINE HARDCODIERUNG

Übungslektion 7 — Suchen und Sortieren

Heutiges Programm

Letztes Mal: Insertion Sort

Letztes Mal: Insertion Sort

Binärer Insertion Sort

Übung 1

Übung 2

Übung 3

Übung 4

Rekursive Snippets: Verifikation

Merge

Algorithmus `merge`

Algorithmus `merge_sort`

Natürlicher 2-Wege Mergesort

Algorithmus `NaturalMergesort`(A)

Gruppenübung: Timsort

Übung 6: Search and Sort

Fragen oder Anregungen?

Heutiges Programm

Letztes Mal: Insertion Sort

Letztes Mal: Insertion Sort

Binärer Insertion Sort

Übung 1

Übung 2

Übung 3

Übung 4

Rekursive Snippets: Verifikation

Merge

Algorithmus merge

Algorithmus merge_sort

Natürlicher 2-Wege Mergesort

Algorithmus NaturalMergesort(A)

Gruppenübung: Timsort

Übung 6: Search and Sort

Fragen oder Anregungen?

Algorithmus `merge`

Algorithmus `merge_sort`

Algorithmus `NaturalMergesort`(A)