Sortieren

Question 1

Was bedeutet “Sortieren”?

Answer 1

Einträge in einem Array in eine Reihenfolge bringen, so dass 𝑎[𝑖] ≤ 𝑎[𝑗] für alle 𝑖 < 𝑗.

Question 2

Wie funktioniert der Selection Sort Algorithmus?

Answer 2

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 3

Was sind die Eigenschaften des Sortieralgorithmus Selection Sort?

• In-Place: ?
• Stabil: ?
• Beste: ?
• Mittel: ?
• Schlechteste: ?
• Kommentar: ?

Answer 3

• In-Place: Ja
• Stabil: Nein
• Beste: 1/2N^2
• Mittel: 1/2N^2
• Schlechteste: 1/2N^2
• Kommentar: Nur N Austausche

Question 4

Was sind die Eigenschaften von Insertion Sort?

• In-Place: ?
• Stabil: ?
• Beste: ?
• Mittel: ?
• Schlechteste: ?
• Kommentar: ?

Answer 4

• In-Place: Ja
• Stabil: Ja
• Beste: N
• Mittel: 1/4N^2
• Schlechteste: 1/2N^2
• Kommentar: Nützlich für kleines N oder annähernd sortierte Listen

Question 5

Merge Sort Algorithmus

Was sind die Eigenschaften des Merge Sort Algorithmus?

• In-Place: ?
• Stabil: ?
• Beste: ?
• Mittel: ?
• Schlechteste: ?
• Kommentar: ?

Answer 5

• In-Place: Nein
• Stabil: Ja
• Beste: 1/2N log N
• Mittel: N log N
• Schlechteste: N log N
• Kommentar: N log N Garantie

Question 6

Wie funktioniert der Merge Sort Algorithmus?

Answer 6

• Teile das Array in zwei annähernd gleich große Teile.
• Sortiere beide Teile (rekursiv).
• Vereine (merge) beide Teile.

 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

    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

Was ist Stabilität bei Sortierverfahren?

Answer 7

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

Question 8

Welche Verbesserungen gibt es für Mergesort?

Answer 8

• Verbesserung 1: Wechsel auf Insertion Sort für kleine Teilarrays (ungefähr 10 Werte)
• Verbesserung 2: Wenn der größte Wert der ersten Hälfte kleiner ist als der kleinste der zweiten, kann das Merge unterbleiben.

Question 9

Wie funktioniert der Insertion Sort Algorithmus?

Answer 9

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 10

Finden Sie fur die folgenden Beispiel-Arrays jeweils heraus, wie viele Vergleiche und Vertauschungen die aus der Vorlesung bekannten Algorithmen Selection Sort und Insertion Sort benötigen, um das Array zu
sortieren.

Selection-Sort benötigt Vergleiche
und Austausch-Operationen.
(N − 1) + (N − 2) + … + 1 + 0 ≈ 1/2N^2 Vergleiche und N Austausche.

[8,3,5,1,4]
[2,6,4,6,8]
[9,8,6,2,1]

Answer 10

[8,3,5,1,4]
Selection:
Vergleiche: 10
Vertauschungen: 5
Insertion:
Vergleiche: 9
Vertauschungen: 7

[2,6,4,6,8]
Selection:
Vergleiche: 10
Vertauschungen: 5
Insertion:
Vergleiche: 5
Vertauschungen: 1

[9,8,6,2,1]
Selection:
Vergleiche: 10
Vertauschungen: 5
Insertion:
Vergleiche: 10
Vertauschungen: 10