Sortieren [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.
## Sortieren



Damit wir die effiziente Binärsuche verwenden können, muss der Suchbereich sortiert sein. Aber wie sortieren wir eine Liste? Wie lange dauert es?

#### Aufgabe C1: Manuell Sortieren

Sortiere eine Anzahl Elemente und dokumentiere den gefundenen *Algorithmus* so, dass eine andere Gruppe ihn nachvollziehen kann.

##### Spielkarten

Sortiere 8 Spielkarten oder Zahlenkarten `[60, 32, 16, 35, 77, 29, 22, 80]` ([[https://flippity.net/ma.php?c=60,%2032,%2016,%2035,%2077,%2061,%2076,%2029,%2022,%2080|Online-Alternative]]).

  * Wie gehts du vor?
  * Wieviele Änderungen machst du?
  * Welche Arten von Veränderungen führst du durch?

##### Kugeln

Du hast 8 Plastikkugeln, die sich nur im Gewicht unterscheiden, und eine [[wpde>Tafelwaage]]. Das Ziel ist, die Kugeln nach Gewicht zu sortieren.

  * Wie gehts du vor?
  * Wieviele Vergleiche sind nötig?


### Sortieralgorithmen

Sortieren ist eines der Grundprobleme der Informatik, und es existieren [[http://www.sorting-algorithms.com/|dutzende von Algorithmen]] mit unterschiedlichen Eigenschaften. Die wichtigsten Eigenschaften sind die folgenden:
  * Laufzeit: wieviele Operationen sind nötig, um eine Liste der Länge `n` zu sortieren?
    * Vergleiche von zwei Elementen
    * Austausch von zwei Elementen
    * Entfernung oder Einfügen eines Elements
  * Stabilität: Bleiben zwei Einträge in der ursprünglichen Reihenfolge, wenn sie denselben Suchschlüssel haben?
  * In-Place: Wird abgesehen von der zu sortierenden Liste nur noch eine konstante Speicherkapazität verwendet, oder wird beispielsweise eine neue Liste aufgebaut, die den Speicherbedarf verdoppelt?
    * Wenn du beim Sortieren nur Elemente vertauschst, statt eine neue Liste anzulegen, hast du einen In-Place-Algorithmus verwendet.

#### Aufgabe C2: Sortierung Prüfen
Schreibe eine Funktion `is_sorted(l)` die genau dann `True` zurückgibt, wenn `l` aufsteigend sortiert ist, sonst `False`.

Wieviele Vergleiche sind nötig, um eine Liste der Länge $n$ zu testen?

++++Hinweise|
  * Wir müssen alle nebeneinander liegenden Paare `a = l[index]` und `b = l[index+1]` durchgehen.
    * Dabei müssen wir aufpassen, dass wir mit `index+1` nicht über das Ende der Liste hinaus lesen.
  * Wenn wir ein Paar finden, für das nicht `a <= b` gilt, so ist die Liste nicht aufsteigend sortiert.
  * Wenn wir kein Paar finden (also alle Paare durchprobiert haben), so ist die Liste sortiert.
++++


<nodisp 1>

++++Lösung|
<code python>
def is_sorted(l):
    for index in range(len(l) - 1):
        a = l[index]
        b = l[index + 1]
        if b < a:
            return False
    return True

print(is_sorted(['Apfelküchlein', 'Caramel', 'Zuckerwatte']))
print(is_sorted(['Zuckerwatte', 'Apfelküchlein', 'Caramel']))
</code>
++++
</nodisp>


#### Aufgabe C3: Selection Sort
Das Ziel von _Selection Sort_ ist, zuerst die kleinste Zahl in der Liste zu finden und diese an der ersten Stelle der sortierten Liste zu platzieren. Danach machen wir weiter mit der zweitkleinsten Zahl usw.

##### Teil 1: Manuell

Arbeite wieder mit den Zahlen-Kärtchen: Lege diese in zufälliger Reihenfolge auf den Tisch. Wende dann den Selectionsort-Algorithmus an, um diese zu sortieren.

Kannst du SelectionSort als _in-place_ Algorithmus anwenden?

##### Teil 2: Python

Hier ist der [[gf_informatik:suchen_und_sortieren:selection_sort_outplace|Lösungsweg für Selection Sort Schritt für Schritt]] zusammengestellt.

Hier dasselbe für [[gf_informatik:suchen_und_sortieren:selection_sort|In-place Selection Sort]].
#### Aufgabe C4: Selection Sort anwenden
Du hast folgende beiden Listen:
<code python>
obstsorten = ["Kirsche", "Apfel", "Banane", "Orange", "Mango", "Pfirsich", "Erdbeere", "Birne", "Himbeere", "Kiwi", "Ananas", "Blaubeere"]
farben = ["gelb", "rot", "gelb", "grün", "blau", "rot", "rot", "rot", "braun", "orange", "orange", "orange"]
</code>
Das Problem: Die Liste //obsorten// ist nicht sortiert. Wäre sie sortiert, so würden die beiden Listen korrespondieren (der erste Eintrag von //obsorten// entspräche dem ersten Eintrag von //farben// etc.)

  - Schreibe eine Funktion ''selection\_sort(li)'', der du eine unsortierte Liste übergeben kannst und die eine sortierte Liste zurückgibt.
  - Schreibe danach eine Funktion ''binary\_search(li, el)'', der du eine sortierte Liste und das gesuchte Element übergeben kannst und die den Index des gesuchten Elements in der Liste zurückgibt. Falls die Funktion nichts findet, soll sie None zurückgeben.
  - Kopiere die beiden Listen in deinen Code.
  - Erweitere deinen Code, sodass du eine Obstsorte festlegen kannst und am Ende eine der folgenden beiden Nachrichten ausgegeben wird. 
    - „Die Obstsorte ... hat die Farbe ...“ oder
    - „Die Obstsorte ... wurde nicht gefunden.“



<nodisp 1>
++++Lösung|
<code python>
obstsorten = ["Apfel", "Banane", "Kirsche", "Orange", "Mango", "Pfirsich", "Erdbeere", "Birne", "Himbeere", "Kiwi", "Ananas", "Blaubeere"]
farben = ["gelb", "rot", "gelb", "grün", "blau", "rot", "rot", "rot", "braun", "orange", "orange", "orange"]

def find_min(l):
    min_index = 0
    for index in range(1, len(l)):
        if l[index] < l[min_index]:
            min_index = index
    return min_index

def pop_min(l):
    min_index = find_min(l)
    return l.pop(min_index)

def selection_sort(l):
    results = []
    while len(l) > 0:
        min_elem = pop_min(l)
        results.append(min_elem)
    return results

def binary_search(li,el):
    left = 0
    right = len(li)-1
    while left <= right:
        middle = (left + right) //2
        if li[middle] == el:
            return middle
        elif li[middle] < el:
            left = middle + 1
        else:
            right = middle - 1
    return None

mein_obst = "Erdbeere"
obstsorten_sortiert = selection_sort(obstsorten)
mein_index = binary_search(obstsorten_sortiert, mein_obst)
if mein_index is None:
	print("Die Obstsorte {} wurde nicht gefunden.".format(mein_obst))
else:
	print("Die Obstsorte {} hat die Farbe {}.".format(mein_obst, farben[mein_index]))
</code>
++++
</nodisp>

#### C5 (Zusatzaufgabe): Insertion Sort

Der Algorithmus wird [[gf_informatik:suchen_und_sortieren:insertion_sort|hier vorgestellt und Schritt für Schritt implementiert]].
#### C6 (Herausforderung): Laufzeit-Analyse

_Selection Sort_ ist **in-place** (es wird kein zusätzlicher Platz benötigt).

Aber wie berechnen wir die Laufzeit des Algorithmus? Wieviele Vergleiche führen wir bei SelectionSort aus, um `n` Elemente zu sortieren?
  * An jeder Position vergleichen wir das Element mit allen folgenden.
    * Für die Position `0` sind das `n-1` Vergleiche
    * Für die Position `1` sind es `n-2`
    * ...
    * Für die Position `n-2` ist es ein Vergleich
    * Für die Position `n-1` sind es null Vergleiche
  * Im Durchschnitt sind es also $\frac{n-1}{2}$ Vergleiche pro Position.
  * Insgesamt führen wir $\frac{n\cdot(n-1)}{2}$ Vergleiche aus.

Es wird jedes Element mit jedem anderen verglichen. Intuitiv scheint es möglich, mit weniger Vergleichen auszukommen. Wenn wir wissen, dass `x > y` und `y > z` ist, so müssten wir eigentlich `x` nicht mehr mit `z` vergleichen. Aber wieviele Vergleiche sind mindestens notwendig? Können wir einen **Divide & Conquer** Ansatz wie bei der Binärsuche verwenden?

#### C7 (Herausforderung): Quicksort

Von der Binärsuche wissen wir, dass wir eine Liste in $log_2(n)$ Halbierungen auf einzelne Elemente reduzieren können. Hätten wir nun eine Möglichkeit, beim Halbieren auch noch sicherzustellen, dass die beiden Hälften entmischt sind (also, dass alle Elemente in der ersten Hälfte kleiner sind als die Elemente in der zweiten Hälfte), so hätten wir schon fast gewonnen.

  * 1. Die ganze Liste in zwei Teile teilen:
    * wir wählen (zufällig) ein Element aus, den `pivot`.
    * wir ändern die Liste so, dass alle Elemente kleiner als `pivot` im linken Teil der Liste sind, alle grösseren im rechten Teil, und `pivot` dazwischen am Index `mitte`.
    * hierfür sollten `n` Vergleiche notwendig sein (wir vergleichen alle Elemente mit `pivot`)
  * 2. Schritt 1 rekursiv wiederholen für die beiden Teil-Listen `[links,mitte-1]` und `[mitte+1,rechts]`
    * auf jeder Rekursions-Ebene werden `n` Vergleiche getätigt (verteilt auf alle Teillisten).
    * wir benötigen ca. $log_2(n)$ Halbierungen, um die Liste in minimale Listen mit nur je einem Element aufzuteilen - diese sind trivialerweise bereits sortiert.
  * damit benötigen wir $n\cdot{}log(n)$ Vergleiche

Hm, ist $n\cdot{}log(n)$ viel besser als $\frac{n^2}{2}$? [[https://stackoverflow.com/questions/23329234/which-is-better-on-log-n-or-on2|Stackoverflow]] hat die Antwort.

Das obige Rezept beschreibt den [[wpde>Quicksort]] Algorithmus. Getraust du dich an eine Implementierung in Python?

++++Hinweise|

  * Die Schwierigkeit ist ja, dass wir den Index `mitte` des gewählten Pivots nicht zum vornherein kennen.
  * Es bietet sich an, als Pivot das letzte Element in der Liste zu wählen.
    * Das funktioniert wunderbar für gut vermischte Listen, ist aber eine schlechte Idee, wenn die Liste bereits grösstenteils sortiert ist.
  * Schritt 1 könnte als Funktion `teile(l, links, rechts)` wie folgt vorgehen:
    * von links her suchen, bis wir ein Element finden, das grösser als Pivot ist.
    * von rechts her suchen, bis wir ein Element finden, das kleiner/gleich Pivot ist.
    * beide Elemente tauschen.
    * weitersuchen, bis die Suchen von links und rechts zusammengefunden haben.
    * Pivot in der Mitte platzieren.
  * in Python ist es sehr einfach, zwei Elemente zu tauschen: `l[i], l[j] = l[j], l[i]`

++++

<nodisp 1>
++++Lösung|
<code python quicksort.py>
def teile(l, links, rechts):
    """
    Divide-Step von Quicksort: Teilt die angegebene Liste in zwei Teile und gibt
    den Index des Pivot-Elements zurück.
    Alle Elemente vor dem Pivot-Element sind <= dem Pivot, alle Elemente nachher sind
    grösser als der Pivot.
    """
    # Pivot wählen - wir nehmen das letzte Element.
    pivot = l[rechts]
    i = links
    j = rechts - 1
    # i und j bewegen sich von den Enden her zur Mitte hin.
    # Wenn wir auf beiden Seiten ein Element gefunden haben,
    # das auf die andere Seite gehört, werden sie getauscht.
    while i < j:
        # Suche das erste Element von links, das > ist als pivot
        while i <= j and l[i] <= pivot:
            i += 1
        # Suche das hinterste Element von rechts, das <= ist als pivot
        while j >= i and l[j] > pivot:
            j -= 1
            
        # Elemente tauschen
        if i < j:
            l[i], l[j] = l[j], l[i]

    # i ist jetzt an j vorbei. Alle Elemente <= pivot sind links von i.
    # Pivot an der richtigen Stelle einfügen
    if l[i] > pivot:
        l[i], l[rechts] = pivot, l[i]
    return i

def quick_sort(l, links=None, rechts=None):
    links = links or 0
    rechts = rechts or len(l) - 1
    # Falls die Liste weniger als 2 Elemente hat, ist sie bereits sortiert.
    if links < rechts:
        # Andernfalls: Teile die Liste in zwei Teile...
        mitte = teile(l, links, rechts)
        # Die beiden Teile sind nun entmischt: alle Elemente links der
        # Mitte sind kleiner als die Elemente rechts der Mitte.
        # Somit reicht es, die beiden Teile zu sortieren, damit ist die ganze 
        # Liste sortiert.
        quick_sort(l, links, mitte - 1)
        quick_sort(l, mitte + 1, rechts)
    return l

l = [35, 71, 93, 88, 1, 83, 83, 56, 10, 96]
print(quick_sort(l))
</code>
++++
</nodisp>