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

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

Sortiere 8 Spielkarten oder Zahlenkarten [60, 32, 16, 35, 77, 29, 22, 80] (Online-Alternative).

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

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

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

Sortieren ist eines der Grundprobleme der Informatik, und es existieren 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.

Schreibe eine Funktion is_sorted(l) die genau dann True zurückgibt, wenn l aufsteigend sortiert ist, sonst False.

Hinweise

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.

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?

Hier ist der Lösungsweg für Selection Sort Schritt für Schritt zusammengestellt.

Hier dasselbe für In-place Selection Sort.

Du hast folgende beiden Listen:

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"]

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.

  1. „Die Obstsorte … hat die Farbe …“ oder
  2. „Die Obstsorte … wurde nicht gefunden.“

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]))

Der Algorithmus wird hier vorgestellt und Schritt für Schritt implementiert.

Selection Sort ist in-place (es wird kein zusätzlicher Platz benötigt), und stabil (enthält die Liste zwei Elemente mit gleichem Schlüssel, so wird ihre Reihenfolge nicht verändert).

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 $(n-1)/2$ Vergleiche pro Position.
• Insgesamt führen wir $n*(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?

Von der Binärsuche wissen wir, dass wir eine Liste in $log2(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. $log2(n)$ Halbierungen, um die Liste in minimale Listen mit nur je einem Element aufzuteilen - diese sind trivialerweise bereits sortiert.
  • damit benötigen wir $n*log(n)$ Vergleiche

Hm, ist $n*log(n)$ viel besser als $n^2/2$? Stackoverflow hat die Antwort.

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

Hinweise