Sortieren im Vergleich

Zwei Leute sortieren denselben Kartenstapel: Der eine tauscht ständig Nachbarn, die andere sucht immer die kleinste Karte und legt sie nach vorn. Beide werden fertig, aber wer hat weniger Arbeit? Genau so vergleichen Informatikerinnen und Informatiker Sortierverfahren: Sie zählen die Vergleiche und die Tausche. Das machen wir jetzt auch.

Bubble Sort: fleißig, aber langsam

Bubble Sort kennst du schon: Es vergleicht immer zwei Nachbarn und tauscht sie, wenn sie falsch herum stehen. So steigt die größte Zahl wie eine Blase ans Ende, dann geht alles wieder von vorn los. Das Problem: Es wird enorm viel verglichen und getauscht. Bei 5 Zahlen sind es im schlimmsten Fall 10 Vergleiche, bei 10 Zahlen schon 45. Verdoppelst du die Anzahl, vervierfacht sich die Arbeit ungefähr.

Auswahl-Sortieren: das Minimum nach vorn

Auswahl-Sortieren geht anders vor: Suche in der ganzen Liste die kleinste Zahl und stelle sie ganz nach vorn. Suche dann im unsortierten Rest wieder die kleinste und stelle sie an die zweite Position, und so weiter. Um das Minimum von 5 Zahlen zu finden, merkst du dir die erste Zahl und vergleichst sie mit jeder weiteren: 4 Vergleiche, also immer einer weniger, als Zahlen da sind. Im Rest sind es dann 3, dann 2, dann 1, zusammen also ebenfalls 10 Vergleiche. Bei den Vergleichen nehmen sich beide Verfahren wenig, aber Auswahl-Sortieren tauscht viel seltener: pro Runde höchstens einmal.

Warum clevere Verfahren gewinnen

Bei 10 Zahlen ist der Unterschied egal. Aber bei einer Million Einträgen brauchen Bubble Sort und Auswahl-Sortieren rund 500 Milliarden Vergleiche. Clevere Verfahren wie Merge Sort teilen die Liste immer wieder in Hälften und kommen mit etwa 20 Millionen Vergleichen aus: rund 25000 Mal weniger. Deshalb fühlt sich Sortieren auf deinem Handy sofort an, obwohl dahinter riesige Datenmengen stecken. Die Wahl des Verfahrens entscheidet, nicht die Geschwindigkeit des Geräts.