Informatik
Sortieren
Vergleichen, tauschen, wiederholen: wie aus Chaos Ordnung wird.
Das brauchst du vorher
Deine Playlist nach Titel, deine Fotos nach Datum, die Bestenliste im Spiel nach Punkten: Überall begegnet dir Sortiertes. Das ist kein Zufall, denn in sortierten Daten findest du alles viel schneller wieder. Wie bringt man aber eine durcheinandergewürfelte Liste in Ordnung?
Warum sortieren?
Aus dem Thema Suchen weißt du: Die findet Einträge blitzschnell, aber nur in sortierten Listen. Sortieren ist also die Vorarbeit, die schnelles Suchen erst möglich macht. Einmal sortieren, danach beliebig oft schnell suchen: Dieser Tausch lohnt sich fast immer.
Vergleichen und Tauschen
Eine einfache Sortieridee geht so: Du vergleichst immer zwei Nachbarn in der Liste. Stehen sie in der falschen Reihenfolge, tauschst du sie. Dann rückst du eine Position weiter und vergleichst das nächste Paar. Bist du einmal durch die ganze Liste gelaufen, ist das größte Element nach hinten gewandert, so wie eine Luftblase im Wasser nach oben steigt. Deshalb heißt das Verfahren . Wie viele Vergleiche so ein Durchgang kostet, kannst du direkt abzählen: Bei 6 Einträgen gibt es 5 Nachbarpaare, also 5 Vergleiche, immer einen weniger, als die Liste Einträge hat.
Vergleiche: 0 · Tausche: 0
Mehrere Durchgänge
Ein Durchgang reicht meistens nicht, denn er schiebt nur das größte Element sicher ans Ende. Also läufst du wieder von vorne los, vergleichst und tauschst erneut. Mit jedem Durchgang landet das nächstgrößte Element an seinem Platz. Bei 6 Einträgen sind darum höchstens 5 Durchgänge nötig: Stehen 5 Elemente sicher hinten, bleibt für das letzte nur noch der freie Platz ganz vorne. Und wenn in einem kompletten Durchgang kein einziger Tausch mehr nötig war, weißt du sicher, dass die Liste fertig sortiert ist.
Sortieren im großen Stil
Computer sortieren jeden Tag Millionen von Einträgen: Suchergebnisse, Kontaktlisten, Preise in Onlineshops. Für riesige Datenmengen gibt es raffiniertere Verfahren als Bubble Sort, aber die Grundidee bleibt dieselbe: Ordnung entsteht aus vielen kleinen Vergleichen. Wer das Prinzip einmal verstanden hat, versteht auch die schnellen Verfahren leichter.
Aufgaben
0 von 6 gelöstZeit zum Ausprobieren. Du kannst nichts kaputt machen, jeder Versuch zählt.
Warum lohnt es sich, eine Liste zu sortieren?
Was macht Bubble Sort mit zwei Nachbarn, die in der falschen Reihenfolge stehen?
Wie viele Nachbarvergleiche brauchst du für den ersten Durchgang durch eine Liste mit 4 Einträgen?
Bringe die Schritte eines Bubble-Sort-Durchgangs in die richtige Reihenfolge.
- 1Eine Position weiterrücken und das nächste Paar ansehen
- 2Zwei Nachbarn vergleichen
- 3Am Ende des Durchgangs steht das größte Element hinten
- 4Bei falscher Reihenfolge die beiden tauschen
Du sortierst die Liste 3, 1, 2 mit einem Durchgang Bubble Sort. Wie viele Tausche passieren dabei?
Die binäre Suche findet Einträge blitzschnell, aber nur in … Listen.
Damit geht es weiter