eidp-klausuraufgaben/loops/sort

Sortierte Datenstrukturen

selection_sort

Selection Sort basiert auf dem Konzept durch jedes Element in einer Liste zu gehen um dann das kleineste Element in den übrigen zu suchen und mit dem aktuellen Element zu tauschen.

• Wichtig ist dass dabei die übergebene Liste nicht verändert wird und eine neue sortierte erstellt wird
  • Manuell erstellen mit loop oder deepcopy

Beispiel:

arr[] = 64 25 12 22 11

// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64

// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64 

Hilfe 1: Pseudocode

for e_i in xs
    kleinstes_e = e_i
    for e_j in xs mit: j = i + 1
        if kleinstes_e > e_j
            kleinstes_e = e_j
    vertausche e_i und kleinstes_e

binary_search

Hierbei handelt es sich um einen Algorithmus welcher die Position von einem Wert in einem sortierten Array schnell findet.

Beispiele:

binary_search([1, 2, 3, 4, 5], 4) # 3, was der index von 4 ist
binary_search(["a", "b", "c", "d"], "b") # 1, was der index von "b" ist

• Dazu definieren wir eine linke Grenze left mit dem Anfangswert 0 und eine rechte Grenze right mit dem Anfangswert len(xs) - 1, damit können wir unser gesuchtes Element immer weiter eingrenzen.
• Jetzt wissen wir durch die Sortierung dass left <= right sein muss.
• Also gehen wir jetzt durch unsere Liste und berechnen die Mitte middle von left und right aus und vergleichen diese mit unserem gesuchten Wert.
  • Ist middle kleiner als unser Wert dann können wir left = middle + 1 setzen
  • Ist middle größer als unser Wert dann können wir right = middle - 1 setzen
  • Sonst haben wir unseren Wert, nämlich middle, gefunden und können diesen zurückgeben
• Wenn der Wert nicht existiert wird None zurückgegeben
• Für leere Listen soll auch None zurückgegeben werden

Hilfe 1: Pseudocode

linker_index = 0
rechter_index = länge - 1
solange linker_index <= rechter_index dann
    mitte = (linker_index + rechter_index) / 2
    Wenn Liste[mitte] < gesuchter Wert dann
        linker_index = mitte + 1
    Wenn Liste[mitte] > gesuchter Wert dann
        rechter_index = mitte - 1
    Sonst
        return Liste[mitte]
return Nichts

Hier gehts zur Lösung