Selection Sort [KSR Wiki]

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
## Selection Sort

Wir verstehen das Grundprinzip von [[gf_informatik:suchen_und_sortieren:sortieren#aufgabe_2selection_sort|Selection Sort]]: Wir suchen für jede Position (also jeden _Index_) einer Liste das kleinste Element der zu sortierenden Liste, entfernen es (`pop`) und fügend es am Ende der neuen Liste ein (`append`). Hier sind zwei [[https://www.youtube.com/watch?v=xWBP4lzkoyM|Youtube]] [[https://www.youtube.com/watch?v=g-PGLbMth_g|Videos]], die das Prinzip visualisieren.

Aber wie kommen wir vom Algorithmus zum Code? Wie können wir das Sortier-Rezept in Python umsetzen? Die Zutaten sind die folgenden:

  * [[gf_informatik:programmieren_iii#for-schleife|For-Schleife]]: `for i in ...:`
  * [[gf_informatik:programmieren_ii:variablen_verzweigungen_schleifen#logikif-else|Verzweigung]]: `if <bedingung>:`
  * [[gf_informatik:programmieren_ii|While-Schleife]]: `while ...:`
  * [[gf_informatik:funktionen|Funktionen]]
  * [[gf_informatik:programmieren_iii#listen|Listen]]

### 1: Kleinstes Element finden

Für Selection Sort müssen wir das kleinste Element in einer Liste finden. Beginnen wir also damit.

Wie finden wir in einer Liste, zum Beispiel `l = [25, 13, 38, 76]`, das kleinste Element?
  * Wir besuchen jedes Element der Liste - dafür eignet sich eine `for`-Schleife.
  * In einer Variable merken wir uns das bisher kleinste Element.

++++ Python|
<code python>
l = [25, 13, 38, 76]

# Wir starten mit dem ersten Element:
minimum = l[0]
# Jetzt schauen wir jedes weitere Element an, und merken uns, wenn wir ein kleineres finden:
for element in l:
    if element < minimum:
        minimum = element

print("Kleinstes Element: {0}".format(minimum))
</code>
++++

### 2: Den Index des kleinsten Elements finden
Im Selection Sort Algorithmus wollen wir ja Elemente vertauschen - dazu benötigen wir die Position (wir sagen: den Index) des kleinsten Elements, nicht den Wert des Elementes selber.

Statt einer _direkten_ `for`-Schleife über alle _Elemente_ schreiben wir eine _indirekte_ Schleife, die über alle _Positionen_ einer Liste läuft. `range(len(l))` erzeugt eine Liste mit allen Positionen einer Liste von `0` bis `len(l)-1`. Weil wir ja mit dem ersten Element (Index 0) starten, reicht es, wenn wir erst ab dem zweiten Element (Index 1) mit dem Vergleichen beginnen, wir verwenden also `range(1, len(l))`, um uns einen Vergleich zu sparen.

Der Vergleich muss nun mit den `[eckigen Klammern]` auf die Elemente der Liste zugreifen!

Statt dem kleinsten Element merken wir uns dessen Index:

++++ Python|
<code python>
l = [25, 13, 38, 76]

# Wir starten mit dem ersten Element:
minIndex = 0
# Jetzt schauen wir jedes weitere Element an, und merken uns, wenn wir ein kleineres finden:
for index in range(1, len(l)):
    if l[index] < l[minIndex]:
        minIndex = index

print("Index des kleinsten Elements: {0}".format(minIndex))
print("Kleinstes Element: {0}".format(l[minIndex]))
</code>
++++

### 3: Dasselbe als Funktion
Wir können also den Index des kleinsten Elements finden - grossartig. Fürs Sortieren müssen wir das immer wieder tun; am einfachsten geht das, wenn wir unseren Code in eine Funktion verpacken, die wir aufrufen können, wenn wir sie benötigen.

++++Python|
<code python>
def find_min(l):
    # Wir starten mit dem ersten Element:
    minIndex = 0
    # Jetzt schauen wir jedes weitere Element an, und merken uns, wenn wir ein kleineres finden:
    for index in range(1, len(l)):
        if l[index] < l[minIndex]:
            minIndex = index
    return minIndex

l = [25, 13, 38, 76]
minIndex = find_min(l)
print("Index des kleinsten Elements: {0}".format(minIndex))
print("Kleinstes Element: {0}".format(l[minIndex]))
</code>
++++
### 4: Das kleinste Element entfernen.

Wir möchten eine Funktion `pop_min` schreiben, die das kleinste Element aus einer Liste entfernt und zurückgibt. Mit dem Code von oben ist das nicht schwierig:

  - `find_min` ausführen
  - `pop` aufrufen und das Resultat zurückgeben (die Funktion `pop` gibt das Element zurück, das entfernt wurde).

++++Python|
<code python>
def pop_min(l):
    min_index = find_min(l)
    return l.pop(min_index)
</code>
++++
### 5: Eine sortierte Liste erstellen

Nun ist der Sortieralgorithmus nicht mehr schwierig: Solange die zu sortierende Liste nicht leer ist, entfernen wir jeweils das kleinste Element (`pop_min`) und fügen es an die Resultatliste an (`append`).

++++Python|
<code python>

l = [25, 13, 38, 76]
result = []
while len(l) > 0:
    next = pop_min(l)
    result.append(next)
   
print(result)
</code>
++++

Schreibe das als Funktion `selection_sort(l)`!

[[https://www.toptal.com/developers/sorting-algorithms/selection-sort|Hier]] kannst du dem Algorithmus beim Sortieren zuschauen.
### 6: Dasselbe als in-place Algorithmus

Falls die Liste sehr gross ist, möchten wir es vermeiden, eine neue Liste im Speicher anlegen zu müssen. Ein _in-place_-Algorithmus verändert die zu sortierende Liste, ohne weitere Datenstrukturen zu benötigen. Versuch dich im [[gf_informatik:suchen_und_sortieren:selection_sort|In-place Selection Sort]]!