Suchen und Sortieren
Diese Seite befindet sich im Aufbau. Anregungen und Hinweise bitte an: adrian.degonda@gmail.com
Hinweis: Damit die interaktiven Programme korrekt angezeigt werden, wird empfohlen die ganze Fensterbreite des Laptops zu benutzen.
Suchen
Hinter den weissen Feldern ist jeweils eine Zahl versteckt. Wir suchen bestimmte Zahlen (= beispielhafte Repräsentation von bestimmten Daten).
Die lineare Suche
Suche die gesuchte Zahl indem du auf die weissen Felder klickst.
Überlege dir: Wie viele Male müsstest du wohl im Durchschnitt suchen, wenn du die Suche ca. 100x wiederholen würdest?
(Link zum Programm)
Hinweise zur lineare Suche (aufklappbar)
Im Durchschnitt wirst du n/2, in diesem Fall 10 Mal (20 Felder / 2) suchen müssen, um die gesuchte Zahl zu finden. Wir nennen diese Zahl den average case und dieser wird sich nicht verändern, egal welche Strategie du anwendest. Der best case wäre 1, wenn zufälligerweise bei der ersten Suchanfrage die gesuchte Zahl gefunden wird und beim worst case (hier: 20) wird diese erst bei der letzten Suchanfrage gefunden.
Die binäre Suche
Effizienter klappt die Suche, wenn die Daten bereits sortiert sind. In diesem Beispiel sind die Daten von der kleinsten zur grössten Zahl vorsortiert. Wiederhole die Suche auch hier einige Male und überlege dir dabei:
Wie gehst du jetzt an das Problem an?
Gibt es eine Strategie, mit der du die Zahl «am schnellsten» findest?
Was bedeuten die blauen Felder, die nach den ersten Suchanfragen erscheinen?
Hinweise zur binären Suche (aufklappbar)
Bei diesem Suchalgorithmus ist der Durchschnitt der Suchanfragen (average case) um einiges tiefer als bei der linearen Suche. Die blauen Felder bedeuten, dass die gesuchte Zahl nicht in dort sein kann. Das wissen wir, weil die Zahlenreihe der Grösse nach geordnet ist und die aufgedeckte Zahl z. B. zu gross war. Das bedeutet auch, dass alle nachfolgenden Zahlen zu gross sein werden.
Sortieren
In vielen Fällen lohnt es sich also, die Daten zu sortieren, weil wir diese dadurch viel schneller durchsuchen können. Um zu sortieren, braucht der Computer ganz genaue Anweisungen. Sogenannte Sortieralgorithmen gibt es ganz viele.
Bubble Sort
Ein bekanntest Beispiel ist der Algorithmus Bubble Sort. Dieser funktioniert grob folgendermassen:
Pseudocode;
Wiederhole, bis die ganze Zahlenreihe sortiert ist.
Vergleiche die erste mit der nächsten Zahl.
Falls die linke Zahl grösser ist, vertausche die beiden Zahlen.
Vergleiche die zweite mit der nächsten Zahl.
Falls du am Schluss angekommen bist, beginne wieder mit der ersten Zahl.
Bei der Visualisierung des Bubble sorts siehst du, dass zuerst die grösste Zahl nach rechts "wandert" und dort angekommen als «sortiert» (orange) markiert wird.
Erklärungen:
Mit «Bubble Sort (auto: aus)» kannst du die automatisierte Animation laufen und stoppen lassen.
Mit «+1» kannst du einen Schritt weiter gehen (Vergleich oder Vertauschung von Zahlen)
Grün: Zwei Elemente, die aktuell verglichen werden
Blau: Nicht sortierte Elemente
Orange: Sortierte Elemente
Gelb: Sortierte Elemente, wenn Algorithmus abgeschlossen ist.
Insertion Sort (Insert Sort)
Ein weiteres Beispiel ist Insert Sort. Hierbei wird jeweils eine Zahl genommen und nach links an der richtigen Position eingeführt. Es kann sein, dass weitere Zahlen zwischen diesen vorerst sortierten Zahlen eingefügt werden.
Pseudocode:
Wähle die zweite Zahl.
Wiederholen, bis die Zahl links davon nicht kleiner ist:
Tausche aus, gehe eine Stelle nach links.
Gehe zur nächsten unsortierten Zahl
Bei der Visualisierung des Insertion Sorts siehst du, dass eine Zahl (grün) immer nach links an die vorerst richtigen Stelle "wandert".
Erklärungen:
Mit «Insert Sort (auto: aus)» kannst du die automatisierte Animation laufen und stoppen lassen.
Mit «+1» kannst du einen Schritt weiter gehen (Vergleich oder Vertauschung von Zahlen)
Grün: Aktuelle Position der verarbeiteten Zahl
Blau: Noch nicht sortierte Elemente
Orange: Vorerst sortierte Elemente
Gelb: Sortierte Elemente, wenn Algorithmus abgeschlossen ist.
Selection Sort (Select Sort)
Ein weiteres Beispiel ist Selection Sort. Hierbei wird jeweils nach der kleinsten Zahl gesucht und diese mit der ersten unsortierten Stelle getauscht.
Pseudocode:
Wiederhole bis sortiert:
Wähle die nächste unsortierte Zahl. Vergleiche diese mit den restlichen Zahlen (nach rechts)
Falls eine kleine Zahl gefunden wird, vertausche die Zahlen.
Wenn am Ende der Reihe angekommen:
Die unsortierte Zahl ist sortiert
Bei der Visualisierung des Selection Sorts siehst du, dass die Zahlen ganz links immer bereits fertig (grün) sortiert sind.
Erklärungen:
Mit «Selection Sort (auto: aus)» kannst du die automatisierte Animation laufen und stoppen lassen.
Mit «+1» kannst du einen Schritt weiter gehen (Vergleich oder Vertauschung von Zahlen)
Grün: Sortierte Zahlen
Blau: Noch nicht sortierte Elemente
Orange: Element, das verglichen wird
Gelb: Sortierte Elemente, wenn Algorithmus abgeschlossen ist.
Bogo Sort
Bogo Sort ist ein wenig speziell, denn «bogus» bedeutet übersetzt nämlich falsch. Bei diesem ineffizienten Sortierverfahren wird zufällig neu geordnet und geschaut, ob mit viel Glück die richtige Reihenfolge getroffen worden ist.
Pseudocode:
Wiederhole:
Ordne die Elemente zufällig.
Überprüfe, ob die neue Ordnung sortiert ist.
Achtung, Bogo Sort ist sehr ineffizient. Der «average case», also die durchschnittliche Anzahl an Versuchen kann mit der Fakltät der Anzahl Elemente berechnet werden:
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720 (Bedeutung: Bei 6 Elementen werden im Durchschnitt 720 Versuche benötigt, um zufällig eine sortierte Ordnung zu erhalten)
7! = 5'040
8! = 40'320
Erklärungen:
Mit «Bogo Sort (auto: aus)» kannst du die automatisierte Animation laufen und stoppen lassen.
Mit «+1 Versuch» kannst du einen Schritt weiter gehen (Elemente zufällig neu ordnen)
Gelb: Sortierte Elemente, wenn Algorithmus abgeschlossen ist.