Sortieren
Ideen 2024
Ideen aus der Informatik Didaktik:
-
Statt Karten zu sortieren: ein System, bei dem kein „Face Value“ ersichtlich ist und der Vergleich teuer. Bsp: Kinder-Überraschungs-Eier gefüllt mit unterschiedlicher Menge Sand. Als Vergleichsmöglichkeit eine langsame Balkenwaage (Physik?). → Verhindert die Übersicht über den Sortierbereich, macht das Vergleichen teuer.
Inspiriert häufiger zu Quicksort (teile die Elemente in alle Kleineren und alle Grösseren als ein Zufallselement - Challenge: Rekursion).
Ansonsten:
Oder: Merge Sort: Jeder SuS hat zwei Elemente und sortiert sie trivialerweise. Dann versuchen immer zwei Schüler ihre Elemente zusammenzufügen.
Didaktische Umsetzung:
Gruppen à 4 mit 9 Eiern, 1 Waage
Jede Gruppe versucht, einen Algorithmus zu entwerfen und dokumentieren ihn.
Jede Gruppe preist ihren Algorithmus an (best case, 8 Vergleiche)
Rotation: jede Gruppe setzt den Algo einer anderen Gruppe um und versucht, den Worst Case (36 Vergleiche) zu finden.
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] (Online-Alternative).
Kugeln
Du hast 8 Plastikkugeln, die sich nur im Gewicht unterscheiden, und eine Tafelwaage. Das Ziel ist, die Kugeln nach Gewicht zu sortieren.
Sortieralgorithmen
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?
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.
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.
Lösung
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']))
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
Aufgabe C4: Selection Sort anwenden
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.
„Die Obstsorte … hat die Farbe …“ oder
„Die Obstsorte … wurde nicht gefunden.“
Lösung
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]))
C5 (Zusatzaufgabe): Insertion Sort
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}$? Stackoverflow hat die Antwort.
Das obige Rezept beschreibt den 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.
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]
Lösung
- 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))