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 daran, dass ständig etwas gesucht wird. In einer CD-Sammlung 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.
Sucht man einen bestimmten Titel, klickt man einfach auf "Titel" und der PC sortiert die Playlist automatisch nach den Titeln. Genau so 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.
Zeit-Aspekt
Den bereits oben erwähnten Zeit-Aspekt wollen wir nun etwas näher untersuchen, und zwar an einem sehr viel einfacheren Beispiel. Betrachten wir dazu eine Liste aus zehn int-Zahlen.
| 20 | 3 | 5 | 12 | 17 | 4 | 9 | 2 | 13 | 8 |
In dieser unsortierten Liste wollen wir die Zahl 4 suchen. Ein Mensch sieht sich diese Liste an und findet die Zahl 4 sofort. Das liegt daran, dass unser Gehirn kein Problem mit Parallelverarbeitung hat. Zehn Zahlen hat man locker gleichzeitig im Blick und kann die gesuchte Zahl sofort lokalisieren. Ein Computer kann das aber nicht.
Algorithmen können immer nur zwei Zahlen miteinander vergleichen, das liegt an der Hardware, an der Architektur der Rechner. Ein Such-Algorithmus würde also die erste Zahl (20) nehmen und mit der gesuchten Zahl (4) vergleichen. Da die Zahlen nicht übereinstimmen, würde der Algorithmus mit der nächsten Zahl (3) weitermachen. Auch hier wäre der Vergleich negativ, also käme die übernächste Zahl (5) an die Reihe und so weiter. Nach sechs Vergleichen endlich hätte der Algorithmus die Suchzahl (4) gefunden. Wäre nach der Zahl 8 gesucht worden, hätte der Algorithmus sogar zehn Vergleiche durchführen müssen.
Nehmen wir nun an, der Suchalgorithmus hätte einen sortierten Array zur Verfügung:
| 2 | 3 | 4 | 5 | 8 | 9 | 12 | 13 | 17 | 20 |
Bereits nach dem dritten Vergleich findet der Algorithmus die Zahl 4, und nach dem fünften Vergleich die Zahl 8. Sie sehen also an diesem einfachen Beispiel, wie sinnvoll es ist, eine Datensammlung vor dem Suchen zu sortieren.
Vergleich der Sortierzeiten
Wir wollen für beide Arrays (unsortiert / sortiert) die durchschnittliche Suchzeit bestimmen. Wie machen wir das am besten?
Vorschlag 1
Wir suchen nach jeder der 10 Zahlen und notieren die Anzahl der notwendigen Vergleiche. Dann addieren wir diese Zahlen und dividieren die Summe durch 10.
Dieser Vorschlag hört sich gut an, probieren wir ihn aus.
unsortierte Liste.
| 20 | 3 | 5 | 12 | 17 | 4 | 9 | 2 | 13 | 8 |
Für die Zahl 20 benötigen wir nur einen Vergleich, für die Zahl 3 zwei Vergleiche, für die Zahl 5 drei Vergleiche und so weiter. Wir kommen dann auf eine durchschnittliche Suchzeit von 1 + 2 + 3 + ... + 10 = 55/10 = 5,5 Zeiteinheiten.
sortierte Liste.
| 2 | 3 | 4 | 5 | 8 | 9 | 12 | 13 | 17 | 20 |
Für die Zahl 2 benötigen wir nur einen Vergleich, für die Zahl 3 zwei Vergleiche, für die Zahl 4 drei Vergleiche und so weiter. Wir kommen dann auf eine durchschnittliche Suchzeit von 1 + 2 + 3 + ... + 10 = 55/10 = 5,5 Zeiteinheiten.
Die Suchzeiten unterscheiden sich hier gar nicht. Aber unser Bauchgefühl und auch die alltägliche Erfahrung zeigen uns doch, dass man in einer sortierten Liste viel schneller zum Suchergebnis kommt als in einer unsortieren. Also müssen wir irgendeinen Denkfehler bei dem Vergleich gemacht haben.
Worin besteht dieser Denkfehler?
Wir haben nur nach den Zahlen gesucht, die sich tatsächlich in der Liste befinden. Wir sollten ja aber eigentlich gar nicht wissen, welche Zahlen in der Liste vorhanden sind. Viele Zahlen wie zum Beispiel die 6 sind gar nicht in der Liste vertreten. Wenn wir also "echte" Suchzeiten ermitteln wollen, müssen wir anders vorgehen.
Vorschlag 2
In den Listen sind Zahlen im Bereich 1 bis 20 enthalten. Wir suchen nun nach jeder dieser 20 Zahlen und addieren die Suchzeiten, die Summe dividieren wir dann durch 20.
unsortierte Liste.
| 20 | 3 | 5 | 12 | 17 | 4 | 9 | 2 | 13 | 8 |
Für die Zahl 1 benötigen wir 10 Vergleiche, da die Zahl nicht in der Liste enthalten ist. Für die Zahl 2 werden 8 Vergleiche benötigt, für die Zahl 3 zwei Vergleiche und so weiter. Wir summieren nun
10 + 8 + 2 + 6 + 3 + 10 + 10 + 10 + 7 + 10 + 10 + 4 + 9 + 10 + 10 + 10 + 5 +10 + 10 + 1 = 155. Mit 155/20 = 7,75 erhalten wir die durchschnittliche Suchzeit.
sortierte Liste.
| 2 | 3 | 4 | 5 | 8 | 9 | 12 | 13 | 17 | 20 |
Für die Zahl 2 benötigen wir nur einen Vergleich, für die Zahl 3 zwei Vergleiche, für die Zahl 4 drei Vergleiche und so weiter. Für die Zahl 6 benötigen wir nicht 10 Vergleiche, wie bei der unsortierten Liste, sondern nur 5 Vergleiche. Denn beim 5. Vergleich sehen wir die Zahl 8, und die ist ja eindeutig größer als 6. Das heißt, die Zahl 6 kann nicht in der Liste enthalten sein. Wir summieren also
1 + 1 + 2 + 3 + 4 + 5 + 5 + 5 + 6 + 7 + 7 + 7 + 8 + 9 + 9 + 9 + 9 + 10 + 10 + 10 = 127. Die durchschnittliche Suchzeit ist hier 127/20 = 6,35. Das ist weniger als die Suchzeit für die unsortierte Liste, aber nicht besonders deutlich weniger. An sich hätte man hier eine besseres Ergebnis erwartet.
Hätten wir nur nach den Zahlen 1 bis 10 gesucht, wäre der Vorteil der sortierten Liste deutlicher gewesen: 3,9 Vergleiche gegenüber 7,6 Vergleichen bei der unsortierten Liste. Wir wollen das einmal nachrechnen:
Unsortierte Liste: 10 + 8 + 2 + 6 + 3 + 10 + 10 + 10 + 7 + 10 = 76 Vergleiche, also im Schnitt 7,6 Vergleiche für das Suchen einer Zahl.
Sortierte Liste: 1 + 1 + 2 + 3 + 4 + 5 + 5 + 5 + 6 + 7 = 39 Vergleiche, im Schnitt also auf 3,9 Vergleiche pro Suchzahl.
Fazit: Das Suchen in einer sortierten Liste geht also wesentlich schneller als das Suchen in einer unsortierten Liste. Dabei haben wir noch nicht einmal ein optimales Suchverfahren für die sortierte Liste angewandt, sondern das einfachste Suchverfahren: Von vorne nach hinten, die sogenannte lineare Suche.
Seitenanfang -
Weiter mit der Klasse "Liste" …