## Selection Sort (in-place)

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 restlichen Liste, dann tauschen wir es an die momentane Position. 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: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 `l` 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>
++++

In der _In-place_-Variante haben wir nur eine einzige Liste. Die Elemente vor `position` sind sortiert, die nachher unsortiert. Das nächste Minimum suchen wir also nicht in der ganzen Liste (also ab dem Index `0`), sondern ab einem bestimmten Index. Wir fügen dafür der Funktion einen Parameter `start` hinzu, ab dem nach dem Minimum gesucht wird:


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

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

### 4: Zwei Elemente vertauschen.
Für alle in-place Sortier-Algorithmen benötigen wir die Fähigkeit, zwei Elemente an den Positionen `i` und `j` zu vertauschen. Am einfachsten schreiben wir eine Hilfsfunktion, die das für uns erledigt. Die Funktion benötigt als Parameter die Liste und die zwei Positionen.

++++Python|
<code python>
def swap(l, i, j):
    # Element an Position i zwischenspeichern, weil wir es nachher überschreiben:
    temp = l[i]
    l[i] = l[j]
    l[j] = temp
</code>
++++

++++Hinweis|
Python lässt uns dasselbe noch viel kürzer programmieren, es kommt aber auf dasselbe heraus:
<code python>
def swap(l, i, j):
    l[i], l[j] = l[j], l[i]
</code>
++++

### 5: Selection Sort
Nun ist der Sortieralgorithmus nicht mehr schwierig. Wir benötigen eine Schleife, die über alle Positionen der Liste läuft. An jeder Position `position` suchen wir das kleinste Element _ab der Position_. Wir vertauschen das kleinste Element mit dem Element an `position`.

++++Python|
<code python>

l = [25, 13, 38, 76]

for position in range(len(l)):
    minIndex = find_min(l, position)
    swap(l, position, minIndex)
   
print(l)
</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.