Ein junger Mann sortiert seine CDs
Das Bild wurde von Photoshop 2025 generiert.
Sortieren
Sortieren ist einer der häufigsten Prozesse in der praktischen Informatik und eines der interessantesten Themen in der theoretischen Informatik. Warum ist das Sortieren überhaupt so wichtig?
Der Grund dafür, dass in der Informatik ständig sortiert wird, liegt darin, dass ständig etwas gesucht wird.
In einer CD-Sammlung (Sie wissen ja hoffentlich noch, was eine CD ist) sucht man einen bestimmten Titel, oder man sucht die CD, die man zum letzten Geburtstag von seiner Freundin geschenkt bekommen hat, oder man sucht ein bestimmtes Musikstück, von dem man genau weiß, dass man es hat. Hat man seine Songs auf dem PC oder Handy gespeichert, ist das Suchen meistens kein Problem.
Eine typische Playlist in einem Musikprogramm
Autor: Ulrich Helmich 2022, Lizenz: Public Domain.
Sucht man einen bestimmten Titel, klickt man in der Kopfzeile der Tabelle einfach auf "Titel", und die Anwendung sortiert die Playlist automatisch nach den Titeln, so wie auf dem Bild oben.
Genauso gut kann man auf "Album" oder "Interpret" klicken, und die Liste wird entsprechend sortiert. Das Suchen geht so natürlich viel schneller als bei einer völlig unsortierten Liste.
Suchen
Den bereits oben erwähnten Zeitaspekt wollen wir nun etwas näher untersuchen, und zwar an einem sehr viel einfacheren Beispiel. Betrachten wir dazu eine Liste aus zehn int-Zahlen.
Liste unsortiert:
| 20 | 3 | 5 | 12 | 17 | 4 | 9 | 2 | 13 | 8 |
Liste sortiert:
| 2 | 3 | 4 | 5 | 8 | 9 | 12 | 13 | 17 | 20 |
Beide Listen enthalten zehn Zahlen aus dem Bereich 1 bis 20. Wir wollen nun die Zahlen 1, 2, 3, 4, 5 und 6 in diesen beiden Listen suchen und dabei die Suchzeiten vergleichen. Als "Suchzeit" nehmen wir vereinfachend die Anzahl der Vergleiche, die notwendig sind, um die jeweilige Suchzahl zu finden oder sicher festzustellen, dass sie nicht in der Liste enthalten ist.
| Suchzahl | Vergleiche in unsortierter Liste |
Vergleiche in sortierter Liste |
| 1 | 10 | 1 |
| 2 | 8 | 1 |
| 3 | 2 | 2 |
| 4 | 6 | 3 |
| 5 | 3 | 4 |
| 6 | 10 | 5 |
Um die gesuchten sechs Zahlen zu finden beziehungsweise ihr Fehlen festzustellen, benötigt man in unserer unsortierten Liste insgesamt deutlich mehr Vergleiche als in der sortierten Liste.
Um beispielsweise die Suchzahl 1 in der unsortierten Liste zu suchen, muss man bis an das Ende der Liste gehen (also 10 Vergleiche durchführen), um dann festzustellen, dass die 1 überhaupt nicht in der Liste enthalten ist. Das Gleiche gilt auch für die Suchzahl 6: Erst nach 10 Vergleichen kann man mit Sicherheit sagen, dass die Zahl nicht in der Liste enthalten ist.
Bei der sortierten Liste ist das ganz anders. Die erste Zahl ist die 2. Wäre die 1 in der Liste enthalten, müsste sie ganz vorne stehen. Das ist aber nicht der Fall, also kann man bereits nach einem Vergleich mit Sicherheit sagen, dass die 1 nicht in der Liste enthalten ist. Die Suchzahlen 2, 3, 4 und 5 findet man nach sehr wenigen Vergleichen, da sie vorne in der Liste stehen. Und um festzustellen, dass die 6 nicht in der Liste enthalten ist, muss man nur bis zur 8 gehen. Da die Liste aufsteigend sortiert ist, kann hinter der 8 keine 6 mehr vorkommen.
Eine kleine Optimierung
Wenn Sie in der Bibliothek vor einem Regal mit Romanen stehen und nach einem Buch von Igor Zapparoni suchen, werden Sie mit Sicherheit nicht ganz links beim Buchstaben "A" mit der Suche anfangen, sondern weit rechts beim Buchstaben "Z".
Eine ähnliche Idee kann man auch bei einer sortierten Zahlenliste verfolgen. Angenommen, in der sortierten Liste sind Zahlen aus dem Bereich zwischen 1 und 100 enthalten. Sucht man nach einer kleinen Zahl, kann es sinnvoll sein, von links zu suchen. Bei einer großen Zahl kann man dagegen von rechts beginnen. Voraussetzung ist allerdings, dass man ungefähr weiß, wie die Werte in der Liste verteilt sind. Allein aus dem Wertebereich 1 bis 100 kann man noch nicht schließen, dass die Werte gleichmäßig verteilt sind.
Ein kleines Java-Testprogramm, das ich einmal geschrieben habe, zeigt an zwei Beispielen, dass eine solche Strategie bei einer passenden Verteilung der Zahlen die Zahl der notwendigen Vergleiche deutlich verringern kann. Hier die Ausgabe für das Suchen von 10 Suchzahlen in einem Array, das aus 100 int-Zahlen besteht:
Suchzeit für 10 Zahlen im unsortierten Array: 188 Suchzeit für 10 Zahlen im sortierten Array, von links: 125 Suchzeit für 10 Zahlen im sortierten Array, von links oder rechts: 38
Und hier ein zweiter Durchlauf des Programms mit einem neuen Zufalls-Array:
Suchzeit für 10 Zahlen im unsortierten Array: 168 Suchzeit für 10 Zahlen im sortierten Array, von links: 91 Suchzeit für 10 Zahlen im sortierten Array, von links oder rechts: 58
Die beiden Testläufe zeigen für diese Beispiele:
a) In dem sortierten Array waren weniger Vergleiche erforderlich als in dem unsortierten Array.
b) Die zusätzliche Entscheidung, ob von links oder von rechts gesucht wird, konnte die Zahl der Vergleiche noch weiter verringern.
Aus zwei Testläufen kann man allerdings noch keine allgemeine Aussage über die Geschwindigkeit eines Suchverfahrens ableiten. Dazu müsste man sehr viele unterschiedliche Fälle untersuchen und die verwendeten Suchverfahren genauer analysieren.
Suchverfahren
Das Thema "Suchverfahren" ist fast genauso wichtig in der Informatik wie das Thema "Sortierverfahren". In der Stufe Q1 werden wir dieses Thema noch etwas vertiefen. Dann werden wir auch die binäre Suche und andere verbesserte Suchstrategien kennenlernen.
Im Informatikstudium spielen Such- und Sortierverfahren bereits im ersten Semester eine wichtige Rolle. Das weiß ich aus eigener Erfahrung, weil ich 2025/26 die Gelegenheit hatte, Erstsemester an einer Hochschule in Informatik zu unterrichten.
Seitenanfang -
Weiter mit der Klasse "Liste" …