Zum Inhalt
Anmelden
Alle Apps

Sortier-Rennen

Über diese App

Bubble, Insertion und Selection Sort im Rennen: Drei Bahnen sortieren dieselbe Liste im gleichen Takt, ein Takt ist ein Vergleich. Balken gleiten beim Tausch aneinander vorbei, Zähler zeigen Vergleiche und Vertauschungen. Mit 5, 2, 9, 1, 7, 3 ist Insertion nach 11 Vergleichen fertig, Bubble und Selection nach 15; sortiert braucht Insertion 5. Einzelansicht mit Pseudocode und Python der Folien, Vorhersagen, Verdopplung bis n = 102400 neben den Zeiten der Folie.

Mit Erklärmodus: Ein KI-Tutor führt dich durch die App, zeigt in der Szene, worauf es ankommt, und beantwortet deine Fragen.

Drei einfache Sortierverfahren

Bubble Sort vergleicht Nachbarn und tauscht sie, wenn sie falsch herum stehen; in jedem Durchlauf wandert so das größte Element des unsortierten Teils nach hinten. Insertion Sort schiebt das nächste Element im sortierten Anfang nach links, bis es passt. Selection Sort sucht im Rest das kleinste Element und tauscht es nach vorn. Bubble und Selection brauchen immer n(n−1)/2 Vergleiche, bei sechs Werten also 15. Insertion braucht zwischen n−1 und n(n−1)/2, je nach Vorsortierung.

Was die App zeigt

Drei Bahnen sortieren dieselbe Liste im gleichen Takt; ein Takt ist ein Vergleich. Balken zeigen die Werte, die zwei verglichenen leuchten auf und gleiten beim Tausch aneinander vorbei. Zeiger i, j und min, der sortierte Bereich, Zähler für Vergleiche und Vertauschungen und ein Fortschrittsbalken machen den Aufwand sichtbar. In der Einzelansicht laufen Pseudocode und Python-Code der Folien mit, die aktuelle Zeile ist markiert. Alle Zahlen stimmen mit echtem Python 3.13 überein.

Selbst ausprobieren

Starte das Rennen mit 5, 2, 9, 1, 7, 3: Insertion ist nach 11 Vergleichen fertig, Bubble und Selection nach 15. Mit der sortierten Liste braucht Insertion nur 5, umgekehrt kommen alle drei gleichzeitig an. Eigene oder zufällige Listen mit bis zu 16 Werten sind möglich, in der Einzelansicht fragt die App vor jedem Vergleich, ob getauscht wird. Im Panel Verdopplung wächst n von 100 bis 102400, neben den Zeiten der Folie.

Häufige Fragen

Wie viele Vergleiche braucht Bubble Sort?
Die einfache Fassung vergleicht in jedem Durchlauf alle Nachbarn des unsortierten Teils, insgesamt n(n−1)/2-mal, unabhängig von der Eingabe. Bei 6 Werten sind das 15 Vergleiche, bei 100 Werten 4950. Ohne Abbruchbedingung läuft sie auch dann weiter, wenn die Liste schon sortiert ist.
Warum ist Insertion Sort bei vorsortierten Listen schnell?
Insertion Sort vergleicht jeden neuen Wert mit seinem linken Nachbarn und hört auf, sobald dieser nicht größer ist. Bei einer sortierten Liste kostet jeder Wert genau einen Vergleich, insgesamt n−1. Bei einer umgekehrten Liste muss jeder Wert ganz nach vorn, dann sind es n(n−1)/2.
Warum bedeutet doppelte Länge viermal so viel Arbeit?
Bei n(n−1)/2 Vergleichen wächst der Aufwand quadratisch: Doppelt so viele Werte werden jeweils mit doppelt so vielen anderen verglichen. Aus 4950 Vergleichen für n = 100 werden 19900 für n = 200 und 79800 für n = 400, jeweils rund das Vierfache.
Was zeigt die App Sortier-Rennen?
Bubble, Insertion und Selection Sort laufen auf derselben Liste im gleichen Takt gegeneinander, mit Zählern für Vergleiche und Vertauschungen, Pseudocode und Python-Code der Folien, Vorhersagefragen und einer Verdopplungstabelle neben gemessenen Laufzeiten.

Fach: Informatik

Mehr aus Informatik

Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps