Sortieralgorithmen

Question 1

Selection-Sort

Answer 1

def selectionSort(liste):
    l = len(liste)
    for i in range(l):
        min = i
        for j in range(i+1,l):
            if liste[j] < liste[min]: min = j
            tausche(liste, i, min)

Question 2

Selection-Sort Laufzeit

Answer 2

Best Case: 1/2 N^2
Mittel: 1/2 N^2
Worst Case: 1/2 N^2

Question 3

Insertion Sort Laufzeit

Answer 3

Best Case: N
Mittel: 1/4 N^2
Worst Case: 1/2 N^2

Question 4

Mergesort Laufzeit

Answer 4

Best Case: 1/2 N lg N
Mittel: N lg N
Worst Case: N lg N

Question 5

Quicksort-Laufzeit

Answer 5

Best Case: N lg N
Mittel: 2N ln N
Worst Case: 1/2 N^2

Question 6

Sort Implementierung (Mergesort)

Answer 6

def sortPart(a, lo, hi, aux):
   if hi <= lo: return
   mid = (lo + hi) // 2
   sortPart(a, lo, mid, aux)
   sortPart(a, mid+1, hi, aux)
   merge(a, lo, mid, hi, aux)

def mergeSort(a):
   n = len(a)
   aux = [0] * n
   sortPart(a, 0, n-1, aux)

Question 7

Merge Implementierung

Answer 7

def merge(a, lo, mid, hi, aux):
    aux[lo:hi+1] = a[lo:hi+1]
    i = lo
    j = mid+1
    for k in range(lo, hi+1):
        if i > mid:
            a[k] = aux[j]
            j += 1
        elif j > hi:
            a[k] = aux[i]
            i += 1
        elif aux[j] < aux[i]:
            a[k] = aux[j]
            j += 1
        else:
            a[k] = aux[i]
            i += 1

Question 8

Insertion Sort

Answer 8

def insertionSort(liste):
    l = len(liste)
    for i in range(1,l):
        j = i
        while (j > 0) and (liste[j] < liste[j-1]):
            tausche(liste, j, j-1)
            j -= 1

Question 9

Selection Sort Tausch

Answer 9

Selection Sort benötigt N Austausch Operationen

Question 10

Insertion Sort Tausch

Answer 10

Es werden 1/4 N^2 Austausch Operationen benötigt

Question 11

Definition: Stabil

Answer 11

Ein Sortieralgorithmus ist stabil wenn er die Reihenfolgen von gleichen Elementen während der Sortierung nicht vertauscht.