84 lines
2.6 KiB
Markdown
84 lines
2.6 KiB
Markdown
# [Sortierte Datenstrukturen](src/branch/main/loops/sort/sort.py)
|
|
|
|
## `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
|
|
```
|
|
|
|
<details>
|
|
<summary>Hilfe 1: Pseudocode</summary>
|
|
|
|
```
|
|
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
|
|
```
|
|
|
|
</details>
|
|
|
|
## `binary_search`
|
|
|
|
Hierbei handelt es sich um einen Algorithmus welcher die Position von einem Wert in einem sortierten Array schnell findet.
|
|
|
|
Beispiele:
|
|
```python
|
|
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
|
|
|
|
|
|
<details>
|
|
<summary>Hilfe 1: Pseudocode</summary>
|
|
|
|
```
|
|
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
|
|
```
|
|
|
|
</details>
|
|
|
|
## [Hier gehts zur Lösung](src/branch/main/loops/sort/solution) |