Kapitel 2 - Ordnung muss sein!.pdf

2. Ordnung muss sein! Einführung Ordnung ist das halbe Leben. Schön ist jedoch, wenn man nicht das halbe Leben da- mit zubringen muss, sie zu halten! Wie gut, dass es heute Computer gibt, die einen darin unterstützen. Wie aus dem deutschen Kunstwort „Informatik“ schon ersichtlich wird, hat das Ge-...

2. Ordnung muss sein! Einführung Ordnung ist das halbe Leben. Schön ist jedoch, wenn man nicht das halbe Leben da- mit zubringen muss, sie zu halten! Wie gut, dass es heute Computer gibt, die einen darin unterstützen. Wie aus dem deutschen Kunstwort „Informatik“ schon ersichtlich wird, hat das Ge- schäft eines Informatikers sehr viel mit Information zu tun: Diese soll nicht einfach nur irgendwo abgelegt werden, sondern man möchte sie auch möglichst schnell wie- der auffinden. Das Grundproblem unterscheidet sich dabei nicht von der Frage, die auch für das Arbeitszimmer, die Küche und andere Bereiche des Lebens gilt: „Wer Ordnung hält, ist nur zu faul zum Suchen“ oder, etwas vornehmer ausgedrückt, „Der Aufwand, Ord- nung zu schaffen, muss dadurch gerechtfertigt werden, dass man daraus erhöhten Komfort zieht“ – zum Beispiel mehr Platz, schnelleres Auffinden von Dingen usw. Normalerweise versucht man daher, das Chaos erst gar nicht aufkommen zu lassen – jeden neuen Gegenstand also gleich an den richtigen Platz zu setzen. In verschiede- nen Situationen funktioniert das jedoch nicht: Post kommt meistens als ungeordneter Stapel an, Spielkarten werden gemischt ausgegeben usw. Hier wird eine vollständige Sortierung notwendig. In diesem Kapitel beschäftigen wir uns damit, wie Computer die Aufgabe lösen, eine unsortierte Menge von Daten so zu organisieren, dass der Zu- griff auf einen einzelnen Datensatz sehr schnell geht. Um das wiederum experimentell nachzuvollziehen, eignen sich Spielkarten sehr gut: Tipp: Jeder hat Erfahrung damit, hat selbst schon einmal die zugeteilten Karten auf der Die Vorlagen für die Bastel- materialien können Sie auch Hand sortiert, um dann Doppelkopf, Rommé oder Canasta präziser und schneller im Internet herunterladen. spielen zu können. In Abbildung 2.K1 am Ende des Kapitels finden Sie Kopiervorla- Dort finden Sie zusätzlich gen für ein paar ganz spezielle Spielkarten zum Ausschneiden, die statt Kreuz, Karo, Bezugsquellen für fertige Ass und Dame normale Zahlen enthalten, denn dies sind die Größen, mit denen ein Bastelbögen auf Pappe: Computer meistens rechnen muss: Geburtsdaten und Sozialversicherungsnummern www.abenteuer-informatik.de für Rentenauszahlung, Matrikelnummern von Studierenden für die Prüfungsverwal- tung, Kontonummern und viele mehr. Schneiden Sie die Karten aus – Mischen ist erst einmal nicht notwendig! Das Sortierproblem Bei allen Aufgaben, die man mit dem Computer lösen möchte, ist ein guter Ansatz, sie erst einmal manuell zu erforschen, um ein Gefühl dafür zu bekommen und die Problemstellung zu erfassen. Wie wir beim Auffinden des kürzesten Weges im letzten 49  Kapitel gesehen haben, ist dabei oft die Problemgröße relevant. Das ist in unserem Fall die Anzahl zu sortierender Objekte. Machen Sie daher einen ersten Versuch: Nehmen Sie etwa die Hälfte der blau/grün/rot bedruckten Karten und sortieren Sie sie nach der blauen Zahl. Ergebnis sollte eine zusammenhängende Reihe von Karten (ohne Lücken) auf Ihrem Schreibtisch sein. Falls hier nicht genug Platz ist, dürfen selbstverständlich auch mehrere Reihen untereinander die Sortierung ergeben. Eigentlich war das aber nur die Übung für den eigentlichen Versuch: Nehmen Sie nun 120 dieser Karten (einschließlich der gerade sortieren) und mischen Sie erneut. Bilden Sie dann sechs Stapel zu jeweils 20 Karten, die Sie bereitlegen. Sie benötigen außerdem eine Uhr mit Sekundenangabe oder eine Stoppuhr: Messen Sie die Zeit, die Sie zum Sortieren des ersten Stapels nach den blauen Zahlen benötigen, und schreiben Sie das Ergebnis auf. Danach sammeln Sie die Karten wieder ein, nehmen einen weiteren Stapel hinzu, so dass es jetzt 40 Karten sind. Sortieren Sie nun nach den roten Zahlen. Auf diese Weise sparen Sie das Mischen zwischendurch, weil die roten Zahlen unsortiert sind, wenn die blauen sortiert sind, und umgekehrt. Notieren Sie auch hier die benötigte Zeit. Wiederholen Sie das mit 60, 80, 100 und 120 Karten. Stellen Sie nun die Ergebnisse graphisch dar: Nehmen Sie ein Stück kariertes Papier und übertragen Sie die nebenstehende Abbildung! Machen Sie dann für jeden Ihrer Messwerte ein Kreuz über der entsprechenden Anzahl von Karten (20, 40, 60,...) in der Höhe, die der benötigten Zeit zum Sortieren entspricht, und verbinden Sie die Kreuze mit Linien! Vielleicht haben Sie ja auch noch willige „Opfer“ in Ihrer Umgebung, mit denen Sie den gleichen Versuch durchführen können: Lassen Sie sie zunächst ebenfalls eine An- zahl von Karten (ungefähr 60) sortieren, um sich an den Vorgang zu gewöhnen, und messen Sie dann die Zeit zum Sortieren von 20, 40, 60 usw. Karten. Übertragen Sie die Ergebnisse möglichst jeweils mit einer eigenen Farbe in Ihr Diagramm. Ein Beispiel dafür sehen Sie in der Abbildung 2.1. Nehmen Sie sich nach jedem Versuch auch kurz Zeit, um die Strategie des Sortierers mit ein paar Stichworten festzuhalten. Wie können wir das Diagramm interpretieren? Die erste Erkenntnis ist, dass die Zeit zum Sortieren mit der Anzahl der Karten im Allgemeinen ansteigt. Das ist jetzt noch keine bahnbrechende Entdeckung, denn das kennen wir von allen möglichen alltägli- chen Vorgängen: Das Spülen von 20 Tellern dauert auch länger als das von zehn Stück. Aber vielleicht gibt es ja noch andere Faktoren für den Zeitbedarf? Allgemein ist für die Informatik die Identifizierung einer Problemgröße sehr wichtig. Die Problemgröße Ein wichtiger Vorgang bei der Lösung von Aufgaben aus der Informationstech- nik ist das Bestimmen der sogenannten Problemgröße. Sie stellt ein Maß dar, wie schwierig bzw. umfangreich die Aufgabe bzw. das Problem ist. Daher hängt von der Problemgröße entscheidend der zu leistende Aufwand ab. In vielen Fällen ist die Problemgröße recht offensichtlich – wie die Anzahl von Städ- ten einer Landkarte für die Bestimmung eines kürzesten Weges. In anderen Fällen 50 2. Ordnung muss sein!  Abbildung 2.1 Graph Anzahl der Karten vs. Zeit in Sekunden. müssen wir erst einmal darüber nachdenken, und die Problemgröße hängt nicht nur von der Aufgabe selbst ab, sondern auch davon, was sich im Allgemeinen bei gleich bleibendem Aufgabentyp an der tatsächlichen Aufgabenstellung ändert: Beim Sortieren von Objekten ist ein wesentlicher Faktor die Anzahl der Objekte! Das konnten wir in unserem kleinen Experiment feststellen. Aber auch die Größe der zu sortierenden Elemente könnte als Problemgröße dienen: Es ist sicherlich aufwendiger, 100-stellige Zahlen zu sortieren als 6-stellige... Daher müssen wir uns überlegen, was in einer Aufgabenstellung aus der Realität nor- malerweise feststeht und was variabel ist. Die Größe der zu sortierenden Elemente ist dabei meistens recht stabil: Geburtsdaten, Kontonummern, Namen usw. haben eine recht definierte Länge. Wenn wir als IT-Unternehmen ein neues Verfahren für die Sortierung von Daten anbieten, könnten wir also mit dem Slogan „Wir sortieren Kon- tonummern mit der doppelten Länge in der gleichen Zeit wie unsere Konkurrenten“ sicherlich weniger punkten als mit der Aussage „Wir sortieren die doppelte Anzahl von Kontonummern in der gleichen Zeit wie unsere Konkurrenten.“ Für das Sortieren nehmen wir daher im Folgenden immer die Anzahl der Objekte als Problemgröße an. Problemgrößen und Aufwand Von der Problemgröße hängt der Aufwand zum Erfüllen der Aufgabe ab. Wie ver- hält sich das denn nun in unserem Sortier-Experiment? Normalerweise geht man ja Problemgrößen und Aufwand 51  intuitiv vom sogenannten linearen Verlauf aus: Pro Objekt wird eine bestimmte Zeit benötigt – zum Spülen von 100 Tellern benötigt man also 100-mal die Zeit, die für einen einzelnen Teller notwendig ist. Unter Umständen sogar etwas weniger, weil man ja langsam Übung bekommt und so für die letzten Teller kürzer braucht. Schauen Sie sich daraufhin einmal Ihr Diagramm bzw. Ihre Zahlen an. Benötigten Sie zum Sortieren von 40 Karten in etwa doppelt so lange wie für 20? Haben Sie 100 Kar- ten in der fünffachen Zeit von 20 sortiert? Im Beispiel wird das von der grünen Linie ausgedrückt. Wenn Sie das wirklich geschafft haben, sind Sie schon ein Spitzen-Sortie- rer und heben sich von 99 % aller anderen positiv ab. Normal ist, wenn Sie für die Sortierung von 40 Karten knapp dreimal so lange be- nötigen wie für 20, nicht die doppelte Zeit. Für 60 Karten ist die fünf- bis sechsfache Zeit fällig usw. Das sieht man im Beispiel in etwa an der roten und der blauen Linie. Manche Sortierer verdoppeln jeweils sogar die benötigte Zeit, wenn sie einen weiteren Stapel Karten mit sortieren. Das trifft ungefähr für die gelbe Linie zu. Versuchen Sie selbst, dieses Phänomen zu erklären! Was ist der entscheidende Un- terschied zwischen dem Sortieren von Karten und dem Spülen von Tellern? ▶ ▶ ▶ ◀ ◀ ◀ Divide et impera Der Unterschied lässt sich auf eine sehr grundlegende Methode der Informatik zu- ist weder eine Erfindung der rückführen: „divide et impera“ oder zu Deutsch „teile und herrsche“. Diese Methode Informatiker noch etwas, das ist allerdings gar nicht so neu, sondern wird von fast jedem seit Jahrhunderten für die (wie man bei lateinischen Sprüchen denkt) bereits die Erledigung alltäglicher Arbeiten genutzt. Lesen Sie selbst: Römer in die Welt setzten. Der Satz wird König Ludwig XI. von Frankreich (1423 – Das Prinzip „divide et impera“ 1483) zugeschrieben, der ihn als Maxime hatte. Es handel- Sehr häufig hat man im Leben Probleme zu lösen, die zu unüberschaubar und te sich ursprünglich um eine groß sind, um sie in einem Ansatz zu lösen. Vielmehr teilen wir das Gesamt- Militärstrategie, den Gegner problem auf in mehrere, handhabbare Stücke, die wir lösen. Die Teillösungen zu entzweien, um ihn dann werden danach nur noch zusammengefasst. leichter zu beherrschen. Die Informatik hat ihn dann Dieses Prinzip wird auch in der Informatik sehr stark verwendet: Ein Programm für ihre friedlichen Zwecke zerlegt die gestellte Aufgabe zunächst in mehrere kleinere Einheiten, genannt umfunktioniert: eine Aufga- benstellung beherrschbarer Teilprobleme (divide = teile), und weist danach andere Programme an, diese zu machen, indem man sie zu lösen (impera = herrsche, befehlige). Dabei ist sehr wichtig, dass die Teil- einteilt. probleme unabhängig voneinander gelöst werden können, denn sonst müssten die Programme miteinander kommunizieren, unter Umständen auf Lösungen voneinander warten, was den Aufwand wiederum sehr erhöht. Unterschiedliche Probleme können unterschiedlich gut aufgeteilt werden. Das Teller- wasch-Problem stellt hier keine Herausforderung dar: „100 Teller waschen“ hat direkt als Teilproblem „1 Teller waschen“. Dieses wird 100-mal ausgeführt. Jeder Teller kann unabhängig voneinander gewaschen werden, der Gesamtaufwand besteht also in der Summe der einzelnen Aufwände, also 100-mal der Zeit, die zum Waschen eines Tel- lers benötigt wird. Man kann die Zeit sogar durch Parallelisierung optimieren: Stellen wir 100 Tellerwäscher ein, schaffen wir das Problem in der Zeit, die man zum Wa- schen eines einzelnen Tellers benötigt... Wie sieht das aber beim Sortieren von Karten aus? Probieren wir, auch dieses Problem auf die gleiche Weise aufzuteilen. Wir gehen davon aus, pro Arbeitsschritt eine (un- 52 2. Ordnung muss sein! sortierte) Karte auf die Hand zu nehmen, die wir dann in die Folge bereits sortierter Karten einordnen. „100 Karten sortieren“ hat direkt als Unterproblem „eine Karte sortieren“. Wie lange benötigen wir aber, um eine Karte korrekt zu sortieren? Das hängt sehr stark von der Anzahl Karten ab, die bereits auf dem Tisch liegen! Die erste Karte geht sehr schnell, wir können sie einfach hinlegen. Bei der zweiten Karte müssen wir bereits die Entscheidung treffen, ob sie links oder rechts angelegt wird – der Aufwand hat sich vergrößert. Befinden sich bereits 99 Karten auf dem Tisch, müssen wir die neue Karte mit sehr vielen der bereits sortierten Karten vergleichen, um die richtige Position herauszu- finden. Hier liegt der große Unterschied: Der Aufwand zum Lösen eines Teilproblems ist nicht mehr unabhängig von der Problemgröße, wie das beim Tellerwaschen der Fall war! Je mehr Karten wir sortieren, desto länger dauert im Mittel das Sortieren einer Karte. Daher steigt der Aufwand mit jeder Karte, die zu unserer Sortierung hinzukommt, einerseits um den Faktor „die Anzahl der Karten ist höher, daher muss die Anzahl der Sortiervorgänge erhöht werden“, aber zusätzlich auch um den Faktor „jeder Sortier- vorgang dauert im Mittel etwas länger“. Eine der wesentlichen Aufgaben eines Informatikers ist, diese Erhöhung des Zeitauf- wands zu erforschen und dieses Wissen zu nutzen, um die verwendeten Programme zu verbessern, so dass auch hohe Problemgrößen noch bewältigt werden können. Sortieren auf Computerisch... Egal, welche verschiedenen Strategien Sie und Ihre Versuchspersonen bisher ange- wandt haben – diese sind sicherlich in der einen oder anderen Weise auch in der In- formatik bekannt, es existieren also Sortieralgorithmen dafür. Allerdings fällt es schwer, diese zu erkennen, wenn man jemandem beim Sortieren von Karten zuschaut. Ein Mensch hat einfach zu viele Freiheitsgrade, muss beim Agie- ren keine strikten Regeln einhalten. Hier hilft oft, einfach Computer zu spielen: Überlegen Sie, welchen Beschränkungen ein Computer unterworfen ist, wenn er in seinem Speicher Zahlen sortieren soll. Wie könnte man diese Beschränkungen in eine Art „Spiel“ umsetzen, so dass man mit ähnlichen Voraussetzungen die Karten sortiert? Wenn Sie ungefähr wissen, wie der Speicher eines Computers funktioniert, versuchen Sie zunächst, die Frage selbst zu beantworten, ansonsten lesen Sie bitte einfach weiter. ▶ ▶ ▶ ◀ ◀ ◀ Der größte Unterschied zwischen Mensch und Maschine besteht beim Sortieren in der Speicherung: Der menschliche Kartensortierer besitzt quasi überall „Speicher“ – auf der Hand, als Stapel auf dem Tisch, ausgelegt auf dem Tisch usw. Beim Computer ist der Speicher streng in Positionen organisiert und jede Position, genannt Speicher- stelle oder Speicheradresse, kann genau einen Wert bzw. in unserem Spiel eine Karte beinhalten. Sortieren auf Computerisch... 53  Das können wir glücklicherweise als Experiment simulieren. Die Doppelseite mit Ab- bildung 2.K2 ist Ihr eigener Computerspeicher für die Karten aus der Kopiervorlage. Zunächst kommen wir mit dem gelben Bereich mit den Speicherstellen #32 bis #63 aus. Wenn Sie wollen, können Sie aber den Bogen mehrfach kopieren, um einen noch viel längeren Bereich zu erhalten! Die grünen Buchstaben auf den ersten Speicherstel- len sollen genauso wie die roten Zahlenbereiche erst einmal unbeachtet bleiben! Bringen Sie nun ein paar Karten in den neuen Speicher. Für Sie gilt selbstverständlich die Spielregel: Karten dürfen nur genau auf Speicherpositionen liegen, nicht dazwi- schen. Legen Sie zwei beliebige Karten auf die Adressen #32 und #33. Den Inhalt der Speicheradressen können Sie auslesen – einfach darauf schauen. Eine Besonderheit gibt es allerdings beim Schreiben! Was passiert, wenn Sie einen zusätz- lichen Wert auf Position #33 schreiben (also eine Karte auf diese legen)? Bei unserem Abbildung 2.2 Papierspeicher mit unsortier- ten Karten Papierspeicher passiert nicht viel: Eine Speicheradresse kann prinzipiell als Stapel be- liebig viele Karten fassen. Nimmt man die oberen Karten wieder weg, kommen die unteren wieder zum Vorschein. Ein Computer funktioniert anders. Jede Adresse kann genau einen Wert speichern. Gibt man einen neuen Wert hinein, überschreibt man damit den alten Inhalt. Wir müssen also noch als Spielregel festlegen, dass auf jeder Speicheradresse nur eine Kar- te liegen darf: Sobald eine neue Karte auf einer Position abgelegt wird, kommt die eventuell bereits dort liegende Karte auf den Ablagestapel und ist aus dem Spiel. Probieren Sie das versuchsweise anhand eines sehr einfachen Experiments: Die Speicheradressen #32 und #33 sind momentan jeweils mit einer Karte belegt. Tau- schen Sie den Inhalt dieser beiden Positionen aus und halten Sie sich dabei genau an die Spielregeln. ▶ ▶ ▶ ◀ ◀ ◀ Haben Sie das Problem erkannt? Normalerweise würden wir für den Austausch ein- fach eine der Karten in die Hand nehmen, die andere verschieben und dann die Karte aus der Hand auf den verbliebenen Platz legen. Dadurch hätten wir aber die Hand als „Speicher“ genutzt – das ist gegen die Spielregel, nach der Karten nur auf Speicherpo- sitionen des Papierspeichers liegen dürfen. Nehmen wir dagegen eine der Karten und legen sie direkt auf die andere Position, wird diese überschrieben, die Karte mit dem anderen Wert kommt aus dem Spiel – sie ist verloren und der Austausch nicht mehr möglich. 54 2. Ordnung muss sein! Folgerung daraus ist, dass wir den zusätzlichen Speicherplatz („die Hand“) wirklich benötigen: Legen Sie die Karte von Speicherstelle #33 zunächst auf Position #34 ab. Danach können Sie die Karte von #32 auf #33 verschieben und jetzt erst die Karte von #34 auf #32 legen. Das entspricht unseren Spielregeln und exakt so funktioniert die Sache auch im Computer. Abbildung 2.3 Kartentausch nur mit Hilfe einer zusätzlichen Speicher- stelle Für viele Vorgänge wird ein Zwischenspeicher benötigt. Dafür besitzen die meisten Computer auch spezielle Vorkehrungen – Speicheradressen, die besonders schnell und komfortabel abgefragt werden können. Wie setzen wir das im Papierspeicher um? Wo haben wir im echten Leben einen komfortablen Zwischenspeicher für Karten? Wie wäre es mit folgender Erweiterung der Spielregel: Sie dürfen nun maximal eine Karte in der Hand behalten, während Sie die anderen Karten im Speicher verschieben. Zeit für unsere nächsten Schritte als Computer-Simulator. Wählen Sie zufällig sechs der grünen Spielkarten (mit einfachen Buchstaben) aus und legen Sie diese unsortiert auf die Adressen #32 bis #37. Abbildung 2.4 zeigt ein Beispiel. Nun wollen wir die Folge alphabetisch sortieren. Eine Möglichkeit dafür ist, von vor- ne Ordnung zu schaffen. A muss also ganz nach vorne. Nehmen Sie daher A in die Hand, Ihren legalen Zwischenspeicher, und schieben Sie nacheinander T auf die Posi- tion #36, S auf #35, E auf #34 und L auf #33. Nun ist #32 leer, wir können A aus dem Zwischenspeicher dort ablegen. Das Verfahren können wir für D wiederholen, also D aufnehmen, LEST von hinten nach vorne je um eine Position verschieben und dann D auf der freien Position #33 ablegen. Abbildung 2.5 zeigt, wie die Folge jetzt sein sollte. Abbildung 2.4 Unsortierte Karten im Spei- cher Sortieren auf Computerisch... 55  Abbildung 2.5 Nach den ersten Sortierschrit- ten Abbildung 2.6 Die sortierte Folge Nun müssen nur noch L und E getauscht werden und die Folge ist perfekt sortiert, wie Abbildung 2.6 zeigt. War das eine korrekte Vorgehensweise, wenn man einen Computer simulieren möch- te? Betrachten Sie für die Antwort erst einmal nur den allerersten Schritt: A muss ganz nach vorne. Zwei Erkenntnisse haben wir hier genutzt, die wir als Menschen sofort haben, die der Computer aber nicht ohne Weiteres besitzen kann: 1. A ist im Speicher die Karte mit dem alphabetisch kleinsten Buchstaben. 2. Die Karte mit dem kleinsten Buchstaben liegt auf Position #36. Woher wissen wir das? Weil wir natürlich alle Karten gleichzeitig sehen und bereits unser Unterbewusstsein spontan die Situation für uns analysiert. Ein Computer kann zwar auf seinen gesamten Speicher zugreifen, aber im Normalfall immer nur gleichzeitig eine Adresse anschauen. Es ist für ihn daher im Normalfall ein aufwendiger Prozess, herauszufinden, welche der vorhandenen Karten denn nun ganz nach vorne muss. Wir fügen das auch noch unseren Spielregeln hinzu. Dazu benötigen wir die Pfeile aus den Bastelbögen.Wenn wir eine Speicherstelle auslesen wollen, muss immer ein Pfeil auf die entsprechende Adresse zeigen. Alle anderen Adressen gelten als unsichtbar. Ich verspreche: Jetzt haben wir wirklich alle Regeln festgelegt, um Computer zu spie- len, und dürfen mit der Umsetzung des ersten Sortierverfahrens beginnen. Alles, was Sie hier erforschen, einschließlich der offenbar ungünstigeren Vorgehens- weisen, ist übrigens tatsächlich in heutigen Computersystemen wiederzufinden. Be- sonders in Bereichen, in denen an korrekten Programmen viel Geld hängt, folgt man gerne dem Informatik-Motto „never change a running system“, also „Verändere nie ein System, wenn es (doch) läuft.“ Daher finden sich in den Programmen oft noch Prinzipien, die an anderen Stellen bereits durch neue Ideen ersetzt wurden. 56 2. Ordnung muss sein!  Abbildung 2.7 Sortierfolge mit Zeigern Selection-Sort Aufgabe ist, die Folge von sechs Buchstabenkarten im Speicher von Anfang bis zum Ende zu sortieren. Abbildung 2.7 zeigt die Aufstellung mit den zur Verfügung stehen- den Zeigern „Speicherzeiger“ sowie „Anfang“, „Ende“ und „Bestes“. Wie bereits oben dargestellt, ist ein immer wiederkehrendes Prinzip der Informatik die Unterteilung eines großen Problems in kleinere, handhabbare Portionen. Eine Un- terteilung des Sortierproblems könnte also lauten: Sortieren von n Karten: Sortiere die Karte mit dem kleinsten Buchstaben an den Anfang Sortiere die restlichen n − 1 Karten Diese Vorgehensweise nennt man auch „Sortieren durch Auswahl“ oder mit engli- schem Fachbegriff „Selection-Sort“, weil immer eine Karte ausgewählt und korrekt einsortiert wird. Versuchen Sie nun, diese Vorschrift zu konkretisieren. Spielen Sie mit den Materi- alien und formulieren Sie einen allgemeinen Algorithmus für Selection-Sort. Die Zeiger helfen Ihnen dabei, Positionen zu markieren. Sie dürfen sie im Algorithmus benutzen. Sie können eine aus dem ersten Kapitel bekannte Schreibweise verwenden oder ein- fach die Vorschrift so aufschreiben, wie es für Sie selbst am besten nachvollziehbar ist. ▶ ▶ ▶ ◀ ◀ ◀ Selection-Sort 57  Ein Vorschlag ist die ausformulierte Vorschrift nach Abbildung 2.8. Abbildung 2.8 Die hier verwendete Notati- Anfang und Ende zeigen auf die erste bzw. die letzte zu on für Algorithmen ist eine sortierende Karte vereinfachte Form der von Isaac Nassi und Ben Shneider- Setze Speicherzeiger und Bestes auf die erste zu sortierende Karte man entwickelten modularen 0. Darstellungsart. Im deutschen Sprachraum ist sie unter den Bezeichnungen „Nassi-Shnei- Verschiebe Speicherzeiger um eine Position nach rechts derman-Diagramm“ oder 1. „Struktogramm“ bekannt. Kommt der Buchstabe unter Speicherzeiger alphabetisch früher 2. als der Buchstabe unter Bestes ? Falls JA: Verschiebe Bestes auf die Position von Speicherzeiger Wenn auf Speicherzeiger Ende steht, weiter bei (4.), 3. sonst wiederhole ab (1.) Vertausche die Karte unter Bestes mit der Karte unter Anfang 4. Verschiebe Anfang um eine Position nach rechts 5. Wenn Anfang = , fertig, Ende 6. sonst wiederhole ab (0.) In den Anweisungen (1.) bis (3.) wird der kleinste Buchstabe gesucht und gefunden. Dieser muss ganz an den Anfang und wird daher getauscht mit der Karte, die den Platz dort belegt (4.). Nun weiß man, dass die Karte an der ersten Position korrekt liegt, dass diese also nie mehr verschoben werden muss: Sie gehört nicht mehr zum zu sortierenden Bereich. Daher rücken wir bei (5.) den Anfangszeiger um eine Position nach rechts und wie- derholen das Sortieren so lange, bis die unsortierte Folge nur noch aus einer einzelnen Karte besteht. Eine Karte ist aber sowieso immer sortiert, daher sind wir fertig! Ich will das Vorgehen hier gar nicht weiter erklären. „Begreifen“ Sie lieber den Algo- rithmus, indem Sie mehrere zufällige Folgen von Karten sortieren. Nehmen Sie hier- für auch gerne die Karten mit den echten Zahlen. Sie können sowohl die rote als auch die blaue Reihe nutzen – wenn Sie das abwechselnd tun, sparen Sie sich das Mischen zwischendurch. Besser durch Blubberblasen? Damit wir noch etwas zum Spielen haben, erkläre ich gleich ein weiteres, sehr bekann- tes Sortierverfahren, das wegen seiner Einfachheit besonders in älteren Programmen recht häufig eingesetzt wird. 58 2. Ordnung muss sein! Die generelle Idee ist dabei: Gehe die Reihe mit Karten von Anfang bis Ende durch. Vergleiche dabei immer zwei direkt nebeneinander liegende Karten. Sind diese richtig sortiert, mache gar nichts, ansonsten vertausche beide. Können Sie wieder das grundlegende Prinzip der Informatik erkennen? Jede Ver- tauschung stellt etwas mehr Ordnung her, bis alle kleinen Fortschritte zusammen die gesamte Arbeit vollbracht haben. Versuchen Sie das anhand einer zufälligen Reihe, wie in Abbildung 2.9. Abbildung 2.9 Unsortierte Folge Nach dem Durchgehen der Reihe ist die Folge bereits etwas mehr sortiert (Abbildung 2.10). Abbildung 2.10 Folge nach einem Durchlauf des Verfahrens Überlegen Sie, was genau Sie über die Folge nach dem ersten Durchlauf sagen kön- nen und ob man diese Aussage so formulieren kann, dass sie für jede beliebige Kombination von Karten gilt, nachdem Sie den Algorithmus einmal durchgeführt haben. ▶ ▶ ▶ ◀ ◀ ◀ Überlegungen dieser Art müssen Informatiker oft anstellen: das Schließen auf eine allgemeine Regel aufgrund eines Beispiels. In diesem Fall sind nach dem ersten Durchlauf zwei Karten korrekt sortiert: C und Q. Ist das aber immer so? Nein! Nimmt man als Ausgangsfolge zum Beispiel PEQCGD, kommt nach dem ersten Durchlauf EPCGDQ heraus, wie in Abbildung 2.11 darge- stellt. C steht also nicht am Anfang, aber wiederum Q am Ende. Wenn Sie darüber nachdenken, muss das auch so sein: Der Reihe nach wird durch das Vertauschen zweier Karten die größere der beiden immer nach rechts gebracht. Die größte Karte wechselt daher auf die Position ganz rechts, wo sie hingehört. Besser durch Blubberblasen? 59  Abbildung 2.11 Unsortierte Folge Auch dieses Sortierverfahren bringt also pro Durchlauf eine Karte an die richtige Stel- le. Wenn wir es so oft durchführen, wie Karten vorhanden sind, müssen also danach alle Karten sortiert sein. Versuchen Sie nach diesem Prinzip einen Algorithmus zu formulieren, in ähnli- cher Weise wie oben Selection-Sort. Sie können wieder die Zeiger Start, Ende und Speicherzeiger verwenden, um den Bereich zu markieren, der noch unsortiert ist. ▶ ▶ ▶ ◀ ◀ ◀ Eine mögliche, in der Praxis häufig verwendete Formulierung sehen Sie in Abbil- dung 2.12: Wenn in einer Anweisung „Wiederhole Folgendes...“ vorkommt, bezieht sich „Folgendes“ auf den eingerückten Text darunter. Der Algorithmus nennt sich übrigens „Bubblesort“, weil man sich vorstellt, dass die Karten durch den immerwährenden Tausch an die korrekte Position kommen, so wie Luftblasen im Wasser an die Oberfläche steigen. Gut, besser, bester? Das Finden verschiedener Algorithmen zur Lösung eines Problems ist für Informati- ker sehr wichtig! Mindestens genauso wichtig ist jedoch, unter allen möglichen Algo- rithmen den besten zu finden. Für einen guten Algorithmus kann es selbstverständlich sehr viele verschiedene Krite- rien geben, zum Beispiel wie viel Programmieraufwand man benötigt oder wie elegant ein entsprechendes Computerprogramm aussieht. Für manche Anwendungen gilt so- gar, dass ein unübersichtliches Programm sehr viel besser ist als ein übersichtliches, weil es von Konkurrenten schwerer abgeschrieben werden kann. Normalerweise untersuchen wir jedoch immer die Zeit, die ein Algorithmus zur Lö- sung einer bestimmten Problemgröße benötigt – je schneller, desto besser. Genau wie bei den Menschen gibt es selbstverständlich auch Computer, die mehr oder weniger zügig arbeiten, und so kann das gleiche Verfahren auf unterschiedlichen Rechnern unterschiedlich viel Zeit in Anspruch nehmen. Daher müssen wir eine vergleichbare, nur auf den Algorithmus, nicht auf die Maschine zutreffende Basis schaffen: Hierfür legen wir einfach fest, welche Schritte des Algorithmus im Computer Zeit kos- ten. Man spricht hier auch von Operationen. Diese werden dann bei der Durchfüh- rung einfach gezählt. 60 2. Ordnung muss sein!  Abbildung 2.12 Anfang und Ende zeigen auf die erste bzw. die letzte zu Ein mögliches Struktogramm sortierende Karte für Bubblesort Wiederhole das Folgende, solange Anfang und Ende noch 0. mehr als eine Karte auseinander liegen Setze den Speicherzeiger auf die erste zu sortierende Karte 1. Wiederhole das Folgende, bis Speicherzeiger auf Ende liegt 2. Ist die Karte unter Speicherzeiger größer als die Karte direkt 3. rechts davon? Wenn JA: Vertausche die beiden Karten Verschiebe Bestes Speicherzeiger um eine Position nach rechts Anfang 4. Verschiebe Ende um eine Position nach links 5. Da normalerweise Zugriffe auf den Speicher immer besonders zeitintensiv sind, kön- nen für unseren Papierspeicher folgende Schritte ausgewählt werden: Verschieben einer Karte auf eine neue Speicherposition Vergleich zweier Karten Selbstverständlich gibt es noch viele weitere Operationen, wie zum Beispiel Verschie- Benchmark-Tests ben eines Zeigers, Wenn-dann-Anweisung usw. Wie bereits oft in diesem Buch ver- Wir beschäftigen uns hier wenden wir jedoch das Prinzip der Abstraktion, um uns das Leben so einfach wie damit, die Laufzeit von Algo- rithmen durch theoretische möglich zu machen – in diesem Fall, indem wir nur die relevanten Operationen aus- Betrachtungen abzuschätzen. wählen. Ein anderer Ansatz ist, es einfach auszuprobieren. Das nennt man „Benchmarking“ Elementaroperationen (von engl. Benchmark = Maßstab). Hier werden die zu Operationen bzw. Arbeitsschritte, die wir bei der Bestimmung der Laufzeit ei- testenden Programme (oder nes Algorithmus für wichtig bzw. zeitkritisch erachten. Welche Operationen auch ganze Systeme) mit Test- hier ausgewählt werden, ist nicht global definiert, sondern vom jeweiligen An- daten laufen gelassen. Der wendungsfall abhängig. Oft handelt es sich um Speichervorgänge (Lesen und benötigte Zeitaufwand zum Lösen der Aufgaben wird Schreiben im Speicher). gemessen und verglichen. Preisfrage: Wie viele unserer Elementaroperationen benötigt das weiter oben be- schriebene Verfahren zum Tausch zweier Karten im Papierspeicher? ▶ ▶ ▶ ◀ ◀ ◀ Gut, besser, bester? 61  Um die Karten auf den Speicherpositionen A und B zu tauschen, sind drei Verschie- beoperationen nötig: Verschiebe Karte von A auf Zwischenspeicher Verschiebe Karte von B nach A Verschiebe Karte von Zwischenspeicher nach B Wenn wir auf diese Weise die bisher aufgeschriebenen Algorithmen für Selection-Sort und Bubblesort analysieren, können wir an den mit farbigen Sternen markierten Stel- len Elementaroperationen identifizieren. Grün steht für einen Vergleich (1 Elemen- taroperation), Rot für den Austausch zweier Speicherpositionen (3 Elementaroperati- onen). Die Abbildungen 2.13 und 2.14 zeigen die Struktogramme. Abbildung 2.13 Selection-Sort mit markierten Anfang und Ende zeigen auf die erste bzw. die letzte zu Elementaroperationen sortierende Karte Setze Speicherzeiger und Bestes auf die erste zu sortierende Karte 0. Verschiebe Speicherzeiger um eine Position nach rechts 1. Kommt der Buchstabe unter Speicherzeiger alphabetisch früher 2. als der Buchstabe unter Bestes ? Falls JA: Verschiebe Bestes auf die Position von Speicherzeiger Wenn auf Speicherzeiger Ende steht, weiter bei (4.), 3. sonst wiederhole ab (1.) Vertausche die Karte unter Bestes mit der Karte unter Anfang 4. Verschiebe Anfang um eine Position nach rechts 5. Wenn Anfang = , fertig, Ende 6. sonst wiederhole ab (0.) Jetzt sind Sie an der Reihe: Überprüfen Sie experimentell, welches Sortierverfah- ren das bessere ist, indem Sie verschiedene Kartenanzahlen mit beiden Verfahren sortieren. Notieren Sie sich dann (zum Beispiel mit einer Strichliste) jedes Mal den Vergleich zweier Karten und (dreifach) den Austausch zweier Karten. Wenn Sie die bunten Sortierkarten nutzen, können Sie abwechselnd die roten und blauen Zahlen nutzen, um dazwischen nicht immer wieder mischen zu müssen. ▶ ▶ ▶ ◀ ◀ ◀ 62 2. Ordnung muss sein!  Abbildung 2.14 Anfang und Ende zeigen auf die erste bzw. die letzte zu Bubblesort mit markierten sortierende Karte Elementaroperationen Wiederhole das Folgende, solange Anfang und Ende noch 0. mehr als eine Karte auseinander liegen Setze den Speicherzeiger auf die erste zu sortierende Karte 1. Wiederhole das Folgende, bis Speicherzeiger auf Ende liegt 2. Ist die Karte unter Speicherzeiger größer als die Karte direkt 3. rechts davon? Wenn JA: Vertausche die beiden Karten Verschiebe Bestes Speicherzeiger um eine Position nach rechts Anfang 4. Verschiebe Ende um eine Position nach links 5. Selbstverständlich ist das Ergebnis davon abhängig, wie gut die Karten jeweils ge- mischt waren. Wenn man zufällig eine bereits sortierte Folge als Ausgangssituation hat, dann benötigt man zum Beispiel gar keine Vertauschungen. Bis auf solche Spe- zialfälle kann man an der entstehenden Tabelle jedoch recht gut ablesen, wie die Re- chenzeit in Abhängigkeit der Problemgröße ansteigt. Bei meinen Versuchen mit bis zu 35 Karten bin ich auf Ergebnisse nach der Tabelle auf der nächsten Seite gekommen. Dabei habe ich in gesonderten Spalten auch den „Auf- wand pro Karte“ vermerkt, indem ich die Anzahl der Elementaroperationen nochmals Nur einige der vielen bekann- ten Sortieralgorithmen: durch die Anzahl der Karten geteilt habe. Bogosort Wie kann man dies interpretieren? Genau wie beim komplett manuellen Sortieren, Bubblesort Cocktailsort wie wir es ganz am Anfang durchgeführt haben, steigt der Aufwand pro Karte mit Combsort der Anzahl der Karten. Man sagt, die Verfahren sind nicht linear, was bedeutet, dass Gnomesort sich der Aufwand nicht mit einem konstanten Faktor aus der einfachen Problemgröße Heapsort ableiten lässt. Insertionsort Introsort Weiterhin kann man ablesen, dass Bubblesort fast durchgehend schlechter ist als Mergesort Selection-Sort: Der Aufwand pro Karte ist bei Bubblesort ungefähr doppelt so groß Quicksort Selection-Sort wie bei Selection-Sort. Shellsort Smoothsort Der folgende Abschnitt (bis zur nächsten Überschrift) erfordert etwas mathemati- Stoogesort sches Vorwissen. Daher ist es nicht schlimm, wenn Sie ihn gegebenenfalls nicht kom- Tournament-Sort plett verstehen oder gleich ganz überspringen möchten. Insgesamt wächst der Aufwand pro Karte bei beiden Verfahren etwa linear zur Prob- lemgröße n. Bei Selection-Sort kann man ihn etwa mit 0, 6 ⋅n abschätzen. Bei Bubble- sort sind es etwa 1, 3 ⋅n. Gut, besser, bester? 63  Für den Gesamtaufwand T müssen wir natürlich noch mit der Anzahl der Karten n multiplizieren und kom- Tabelle men auf Aufwand für das Sortieren verschiedener Kartenzahlen TSelection-Sort (n) ≈ 0, 6 ⋅ n2 sowie Karten Selection- Bubblesort Selection- Bubblesort TBubblesort (n) ≈ 1, 3 ⋅ n2. (=Problem- Sort Sort pro pro Karte größe) Karte Wie sehr können wir eigentlich den Faktoren 0,6 bzw. 2 4 4 2,0 2,0 1,3 vertrauen? Dazu können Sie ein weiteres Experi- 3 9 12 3,0 4,0 ment durchführen: Nehmen wir an, die Sortierung würde auf einem speziellen Computer durchgeführt, 4 15 6 3,8 1,5 der die Operation „vertauschen“ hardwareunterstützt 5 22 22 4,4 4,4 durchführen kann. Daher koste diese nun – wie der 6 30 33 5,0 5,5 Vergleich – nur noch eine Elementaroperation. Wie- 7 39 57 5,6 8,1 derholen Sie nun das Experiment für beide Sortier- verfahren Selection-Sort und Bubblesort! 8 49 79 6,1 9,9 Während sich bei Selection-Sort am Ergebnis wahr- 9 60 111 6,7 12,3 scheinlich nicht viel verändert hat, ist sicherlich Bub- 10 72 96 7,2 9,6 blesort deutlich „besser“ geworden: Selection-Sort 11 85 127 7,7 11,5 nutzt ja genau eine Vertausch-Operation pro Karte. 12 99 201 8,3 16,8 Bubblesort nutzt hingegen, abhängig von der ge- gebenen Vorsortierung, deutlich häufiger die Ver- 13 114 183 8,8 14,1 tauschung, weshalb sich der Faktor durch die neue 14 130 241 9,3 17,2 Annahme deutlich verbessert. Bei mir ergaben sich: 15 147 273 9,8 18,2 TSelection-Sort (n) ≈ 0, 5 ⋅ n2 sowie 16 165 309 10,3 19,3 17 184 403 10,8 23,7 TBubblesort (n) ≈ 0, 7 ⋅ n2. 18 204 366 11,3 20,3 Daraus lässt sich eine ganz entscheidende Erkenntnis ableiten: Konstante Faktoren sind im Allgemeinen 19 225 441 11,8 23,2 sehr stark abhängig von den verwendeten Rechner- 20 247 535 12,4 26,8 systemen und von den Annahmen, die wir für die 21 270 594 12,9 28,3 notwendigen Rechenzeiten treffen. Letztlich nehmen 22 294 534 13,4 24,3 wir hier auch wiederum eine Modellierung vor. Wenn wir diese Modellierung gewissenhaft durchführen, 23 319 616 13,9 26,8 verändert sich in der Regel der höchste Exponent hin- 24 345 756 14,4 31,5 ter der Problemgröße n nie. 25 372 828 14,9 33,1 Hinzu kommt, dass konstante Faktoren durch die 26 400 787 15,4 30,3 Wahl eines schnelleren Computers immer ausgegli- 27 429 861 15,9 31,9 chen werden können. Wären zum Beispiel 1.000.000 28 459 1014 16,4 36,2 Karten zu sortieren, bräuchte mit den ursprünglichen Annahmen Selection-Sort ungefähr 600 Milliarden 29 490 1006 16,9 34,7 Elementaroperationen, Bubblesort 1.300 Milliar- 30 522 1074 17,4 35,8 den. Selbstverständlich würde man in der Praxis den 31 552 1194 17,8 38,5 schnelleren Algorithmus einsetzen. Andererseits kann das Manko jederzeit durch Einsatz eines etwa doppelt 32 586 1251 18,3 39,1 so schnellen Computers ausgeglichen werden. Für be- 33 620 1188 18,8 36,0 stimmte Gegebenheiten mag sogar Bubblesort besser 34 653 1335 19,2 39,3 geeignet sein: Es werden immer nur direkt benachbar- 35 690 1426 19,7 40,7 te Speicherstellen miteinander verglichen. Denkt man 64 2. Ordnung muss sein! daran, dass die Daten auf einer Festplatte liegen, geht also der Vergleich ohne große Bewegung des Schreib-/Lesekopfes vonstatten. Bei Selection-Sort hat man diesen Vor- teil nicht. Wesentlich ist allerdings, wie stark der Zeitaufwand anwächst, wenn die Problemgrö- ße anwächst! Dieses Verhältnis spiegelt sich im höchsten Exponenten und lässt sich nicht durch Wahl eines stärkeren Rechners verändern – genauso wenig wie durch die Feinjustage des Algorithmus! Wenn wir einen besseren Algorithmus finden möchten, ist es also wesentlich, dieses Verhältnis zwischen Problemgröße und Aufwand zu verbessern. Konstante Faktoren spielen eine untergeordnete Rolle! Um Algorithmen miteinander zu vergleichen, lässt man daher normalerweise konstante Faktoren weg. Mit dieser Betrachtungsweise sind beide Sortierverfahren gleichwertig, sie haben quadratische Laufzeit. Wer es formal nicht so genau nimmt, sagt zu ihnen „quadratische Sortierverfahren“. Weitere Quantensprünge? Die hier herausgearbeiteten Nicht nur in der Informatik, auch in anderen Wissenschaften sucht man immer mög- Prinzipien für Aufwandsab- lichst einfache Beschreibungsmöglichkeiten. Eine kurze, prägnante Formel ist immer schätzung gelten für her- vorzuziehen gegenüber einem komplizierten und langen Ausdruck. Wichtig ist, dass kömmliche Computer, die alle wesentlichen Aspekte berücksichtigt wurden. immer genau eine Elementa- roperation auf einmal durch- Wie unterscheidet sich denn nun ein Sortierverfahren, das zu einer anderen Kategorie führen können (oder mit gehört? Nehmen wir an, es gäbe eines, das kubisch, also proportional zu Problemgrö- mehreren Prozessorkernen eine genau definierte Zahl ße-hoch-3 funktioniert. Das würde für die 1.000.000 Karten bereits etwa 1 Trillion von Elementaroperationen Elementaroperationen benötigen, wäre also nicht nur etwas schlechter, sondern wür- auf einmal). de gleich um Größenordnungen länger benötigen, die Aufgabe zu lösen. Glücklicher- Manche Forscher versuchen weise haben wir ja bereits bessere Verfahren kennen gelernt. jedoch, Computer zu bauen, die völlig anders – auf Basis Schön wäre allerdings, wenn wir ein Verfahren hätten, das noch weniger Rechenschrit- von Wahrscheinlichkeiten te benötigt. Hier kann ich vorwegnehmen: Die Elite der „normalen“ Sortierverfahren – operieren. Für unsere kon- ventionellen Berechnungen läuft proportional zu n ⋅ log 2 n mit n als Problemgröße. Damit lassen sich 1.000.000 würde das dann so aussehen, Karten ungefähr mit einem Vielfachen von 10.000 Elementaroperationen sortieren, als ob diese Computer bei was wiederum um Größenordnungen besser ist als Bubble- oder Selection-Sort. höheren Problemgrößen auch eine höhere Zahl von Elemen- taroperationen gleichzeitig Die Aufwandsabschätzung verarbeiten könnten. Nach diesem Prinzip arbeiten zum Mit der Aufwandsabschätzung wird in der Informatik oft die Qualität von Al- Beispiel Quantencomputer. gorithmen bestimmt. Diese Abschätzung gibt an, wie stark die notwendige Re- Andere Forscher legen jedoch Ergebnisse vor, nach denen chenzeit in Bezug zur Problemgröße anwächst. Konstante Faktoren werden hier Quantencomputer in sinn- nicht berücksichtigt. Auf diese Weise kann für kleine Problemgrößen die tat- vollen Größenordnungen nie sächliche Rechenzeit eines „schlechteren“ Algorithmus unter der des besseren funktionieren werden. liegen. Mit der hohen Kunst der Aufwandsabschätzung wollen wir nun einen noch besseren Sortieralgorithmus finden. nlogn oder die Kür des Sortierens Im folgenden Abschnitt werde ich der Kürze halber immer n als Bezeichnung der Problemgröße verwenden, ohne das jedes Mal erneut zu erwähnen. Das ist der unter Informatikern übliche Buchstabe dafür. nlogn oder die Kür des Sortierens 65  Im letzten Abschnitt haben wir experimentell nachvollzogen, warum die bisher durch- gesprochenen Sortierverfahren eine quadratische Aufwandsabschätzung (also n2 ) be- sitzen. Man kann das jedoch auch anders begründen: Ein Sortierschritt der Verfahren sorgt jeweils dafür, dass ein einzelnes Element korrekt positioniert wird (am Ende der Folge). Wir benötigen also n Sortierschritte, bis alle Karten korrekt liegen. Betrachten wir nun einen einzelnen Sortierschritt: Hier wird die gesamte Liste durch- gegangen – bei Selection-Sort, um das größte Element zu finden, bei Bubblesort, um jeweils Paare in die korrekte Reihenfolge zu bringen. Im ersten Schritt müssen wir also n Karten anfassen, im zweiten Schritt eine weniger und so weiter, bis im letzten Schritt n nur eine Karte betrachtet wird. Im Durchschnitt sind also pro Schritt etwa Karten anzufassen (was einem Vielfachen von n Operationen entspricht). 2 Insgesamt gibt es also n Durchläufe mit je n Operationen. n2 Multipliziert ergibt das einen Aufwand von Operationen. Da wir konstante Fak- 2 toren nicht betrachten wollten, fassen wir das zu einer Aufwandsabschätzung von n2 zusammen. Widmen wir uns der nächsten großen Aufgabe: Ein besseres Sortierverfahren soll ge- funden werden! Das können wir offenbar erreichen, indem wir entweder die Anzahl der Durchläufe reduzieren oder den Aufwand pro Durchlauf reduzieren. Wie schon im letzten Kapitel können wir hier auch wieder alltägliche Situationen als Vorbild nutzen – in diesem Fall ein im Sport typischer Wettkampf im K.-o.-Verfahren. Allerdings lassen wir in unserem Fall nicht Sportler, sondern Karten gegeneinander Abbildung 2.15 # 02 Die Karten treten paarweise gegeneinander an. # 04 # 05 # 08 # 09 # 10 # 11 # 16 # 17 # 18 # 19 # 20 # 21 # 22 # 23 0-20 21-29 30-32 33-35 36-39 40-42 43-44 45-46 47-48 49 50 51-52 53-54 55-56 57-58 59-61 # 32 # 33 # 034 # 35 # 36 # 37 # 38 # 39 # 40 # 41 # 42 # 43 # 44 # 45 # 46 # 47 A B C D E F G H I J K L M N O P U B D J WN OM I S P C Q G F T 66 2. Ordnung muss sein!  # 02 Abbildung 2.16 Das Achtelfinale wurde aus- getragen. # 04 # 05 # 08 # 09 # 10 # 11 # 16 # 17 # 18 # 19 # 20 # 21 # 22 # 23 U J W O S P Q T 0-20 21-29 30-32 33-35 36-39 40-42 43-44 45-46 47-48 49 50 51-52 53-54 55-56 57-58 59-61 # 32 # 33 # 034 # 35 # 36 # 37 # 38 # 39 # 40 # 41 # 42 # 43 # 44 # 45 # 46 # 47 A B C D E F G H I J K L M N O P B D N M I C G F antreten. Verwenden Sie den Papierspeicher für den Wettkampf – diesmal einschließ- lich der Speicherstellen #01 bis #31. Legen Sie aber zunächst die unsortierte Folge auf die bereits bekannten Speicheradressen #32 bis #47, also die Hälfte des Papierspei- chers mit #02 als oberstem Element. Ein Beispiel sehen Sie in Abbildung 2.15. Daraufhin spielen wir die erste K.-o.-Runde aus. Die jeweils größere Karte eines Paa- res „gewinnt“ und steigt eine Runde auf, wie in Abbildung 2.16. Im Sport entspräche das dem Achtelfinale, dessen acht Sieger um den Einzug ins Viertelfinale spielen. Als Nächstes rücken die jeweils größeren Karten des Viertelfinales auf die vier höhe- ren Felder vor, quasi als Halbfinalisten. Abbildung 2.17 zeigt das. # 02 Abbildung 2.17 Die Sieger des Achtelfinales stehen im Viertelfinale # 04 # 05 # 08 # 09 # 10 # 11 U W S T # 16 # 17 # 18 # 19 # 20 # 21 # 22 # 23 J O P Q 0-20 21-29 30-32 33-35 36-39 40-42 43-44 45-46 47-48 49 50 51-52 53-54 55-56 57-58 59-61 # 32 # 33 # 034 # 35 # 36 # 37 # 38 # 39 # 40 # 41 # 42 # 43 # 44 # 45 # 46 # 47 A B C D E F G H I J K L M N O P B D N M I C G F nlogn oder die Kür des Sortierens 67  Abbildung 2.18 # 02 Belegung des Viertelfinales mit nachgerückten Kandida- ten des Achtelfinales # 04 # 05 # 08 # 09 # 10 # 11 U W S T # 16 # 17 # 18 # 19 # 20 # 21 # 22 # 23 B J N O I P Q F 0-20 21-29 30-32 33-35 36-39 40-42 43-44 45-46 47-48 49 50 51-52 53-54 55-56 57-58 59-61 # 32 # 33 # 034 # 35 # 36 # 37 # 38 # 39 # 40 # 41 # 42 # 43 # 44 # 45 # 46 # 47 A B C D E F G H I J K L M N O P D M C G Im Sport wären die ausgeschiedenen Mannschaften bereits nach Hause gefahren. Beim Sortieren wäre es allerdings ungünstig, die „Verlierer“ gar nicht mehr weiter zu berücksichtigen. Daher werden nun die frei gewordenen Plätze des Viertelfinales auf- gefüllt: Von unten rücken die entsprechenden Karten nach. In Abbildung 2.18 sehen Sie, wie zum Beispiel B von #33 nach #16 aufgestiegen ist. Nun wird nach dem gleichen Schema das Halbfinale ausgespielt. Es gewinnen W und T, sie rücken ins Finale auf. Beachten Sie, dass wiederum die frei gewordenen Plätze des Halbfinales belegt werden. Dafür stehen nun jeweils zwei Kandidaten zur Verfü- gung und es wird „ausgespielt“, wer aufsteigt. In diesem Fall kommt O auf #09 und Q Abbildung 2.19 # 02 Vor dem Finale # 04 # 05 W T # 08 # 09 # 10 # 11 U O S Q # 16 # 17 # 18 # 19 # 20 # 21 # 22 # 23 B J N M I P G F 0-20 21-29 30-32 33-35 36-39 40-42 43-44 45-46 47-48 49 50 51-52 53-54 55-56 57-58 59-61 # 32 # 33 # 034 # 35 # 36 # 37 # 38 # 39 # 40 # 41 # 42 # 43 # 44 # 45 # 46 # 47 A B C D E F G H I J K L M N O P D C 68 2. Ordnung muss sein!  # 02 Abbildung 2.20 Fertig ausgespieltes K.-o.- W System # 04 # 05 U T # 08 # 09 # 10 # 11 J O S Q # 16 # 17 # 18 # 19 # 20 # 21 # 22 # 23 B D N M I P G F 0-20 21-29 30-32 33-35 36-39 40-42 43-44 45-46 47-48 49 50 51-52 53-54 55-56 57-58 59-61 # 32 # 33 # 034 # 35 # 36 # 37 # 38 # 39 # 40 # 41 # 42 # 43 # 44 # 45 # 46 # 47 A B C D E F G H I J K L M N O P C auf #11. Falls möglich, werden danach noch die verwaisten Plätze des Viertelfinales von unten aufgefüllt. Abbildung 2.19 zeigt das Ergebnis. Nun kommt nur noch das Finale – W gewinnt und kommt auf das Siegerfeld #02. Die entstehende Lücke wird selbstverständlich sofort von den jeweils nächstplatzierten Karten der darunterliegenden Ebenen ausgefüllt, die dadurch entstandene Lücke auch usw. In diesem Fall rückt die Karte U nach, dann J und D. Abbildung 2.20 zeigt das fertige K.-o.-System. Spielt man mit dem kompletten Papierspeicher, dauert es bis zum Finale eine Runde länger und das Siegerfeld ist die rot markierte Position #01. Was bringt uns das Ganze jetzt? Durch das K.-o.-System haben wir garantiert die größte Karte gefunden, denn die liegt auf dem Siegerfeld. Sie gehört an das Ende der sortierten Liste. Dort schieben wir sie daher auch hin. In diesem Fall ist das W. Der Siegerplatz ist nun vakant und selbstverständlich rücken die nächsten Karten nach, indem nacheinander das Finale sowie je eine Partie des Halbfinales und Vier- telfinales ausgetragen werden, bis kein Kandidat zum Nachrücken von unten mehr da ist. Versuchen Sie selbst, die Situation zu ermitteln, nachdem W an die Endposition der sortierten Liste verschoben wurde. ▶ ▶ ▶ ◀ ◀ ◀ Ihr Resultat können Sie mit Abbildung 2.21 vergleichen. Genau das gleiche Prinzip verwenden Sie nun, um immer wieder den nächsten Sieger auf die letzte freie Position der fertigen Sortierung zu verschieben und das Siegerfeld neu zu füllen, indem Sie die Karten darunter nachrücken lassen. Probieren Sie es aus! Zur Kontrolle habe ich Ihnen in Abbildung 2.22 noch ein letztes Zwischenergebnis dargestellt. Sie werden jetzt vielleicht überlegen, wozu der ganze Aufwand eigentlich gut ist, denn wir haben ja bereits zwei gut funktionierende Sortierverfahren kennen gelernt. Was ist anders am K.-o.-Verfahren, das übrigens nach dem englischen Wort für Wettbewerb nlogn oder die Kür des Sortierens 69  Abbildung 2.21 # 02 Situation nach dem „Aus- scheiden“ des Siegers und Nachrücken der nächsten Kandidaten U W # 04 # 05 O T # 08 # 09 # 10 # 11 J N S Q # 16 # 17 # 18 # 19 # 20 # 21 # 22 # 23 B D M I P G F 0-20 21-29 30-32 33-35 36-39 40-42 43-44 45-46 47-48 49 50 51-52 53-54 55-56 57-58 59-61 # 32 # 33 # 034 # 35 # 36 # 37 # 38 # 39 # 40 # 41 # 42 # 43 # 44 # 45 # 46 # 47 A B C D E F G H I J K L M N O P C Abbildung 2.22 # 02 Die Hälfte der Karten ist nun sortiert. M N O P Q S T UW # 04 # 05 J I # 08 # 09 # 10 # 11 D C G # 16 # 17 # 18 # 19 # 20 # 21 # 22 # 23 B F 0-20 21-29 30-32 33-35 36-39 40-42 43-44 45-46 47-48 49 50 51-52 53-54 55-56 57-58 59-61 # 32 # 33 # 034 # 35 # 36 # 37 # 38 # 39 # 40 # 41 # 42 # 43 # 44 # 45 # 46 # 47 A B C D E F G H I J K L M N O P „Tournament-Sort“ genannt wird? Für diese Analyse benötigen wir erst einmal die genaue formale Fassung des Algorithmus. Im Aufstellen formaler Algorithmen sind Sie ja inzwischen bereits Meister. Wollen Sie das ein weiteres Mal unter Beweis stellen, indem Sie für Tournament-Sort eine Ablaufvorschrift erstellen? ▶ ▶ ▶ ◀ ◀ ◀ Meinen Vorschlag finden Sie in Abbildung 2.23. 70 2. Ordnung muss sein!  Abbildung 2.23 Gehe die leeren Ebenen von unten nach oben durch und fülle jedes Feld Algorithmus 0. mit der größeren Karte der beiden zugehörigen Wettbewerber Fülle dabei weiter unten entstehende Lücken sofort wieder mit 1. einer der Karten darunter auf: bei zwei Wettbewerbern bei nur einem Wettbe- bei keinem Wettbewer- 2. mit der größeren Karte werber mit diesem ber bleibt das Feld leer Mache Folgendes so lange, bis keine Karte mehr im Siegerfeld liegt 3. Verschiebe die Siegerkarte auf das erste freie Feld am Ende 4. der sortierten Liste Anfang Fülle dabei weiter unten entstehende Lücken sofort wieder 5. auf wie oben beschrieben Versuchen Sie nun, diesen Algorithmus genau so zu analysieren, wie wir dies be- reits oben getan haben. Wie viele Durchläufe benötigt er für die Sortierung? Wie hoch ist der Aufwand pro Durchlauf? Kleiner Hinweis: Im Prinzip besteht der Algorithmus aus einer Art Vorbereitungs- schritt und der eigentlichen Sortierung. Beides können wir auch getrennt voneinan- der betrachten. ▶ ▶ ▶ ◀ ◀ ◀ Im ersten Teil wird die K.-o.-Tabelle vorbereitet, die erste Karte auf dem Siegerfeld ermittelt. Hierfür muss jedes (anfangs leere) Feld im oberen Bereich der K.-o.-Tabelle mit einer Karte belegt werden. Wie viele leere Felder gibt es übrigens für eine K.-o.-Ta- belle mit n Sortierkarten? Auf der untersten Ebene im gelben Bereich befinden sich n Felder mit den unsortier- ten Karten. Auf der untersten K.-o.-Ebene sind es halb so viele, da je eine von zwei Karten gewinnt. Es folgen wiederum halb so viele, also ein Viertel usw., bis nur noch ein Feld, das Siegerfeld, in der obersten Ebene steht. n n n Insgesamt gibt es also + + +... + 1 Felder auf den Siegerebenen. 2 4 8 Einer mathematischen Rechenregel nach ergibt diese sogenannte geometrische Reihe n n n ungefähr wieder n, also + + +... + 1 ≈ n. 2 4 8 Sie können sich das einfach auch durch Ausprobieren klarmachen: Legen Sie eine An- zahl Karten in einer Reihe aus und dann für jedes Feld der K.-o.-Tabelle eine Münze darüber – also in der Reihe oberhalb eine Münze für je zwei Karten, in der Reihe dar- über wieder eine Münze für je zwei Münzen darunter usw. Zählen Sie die Anzahl der Münzen. Je nachdem, ob die Anzahl der Karten gerade ist bzw. wie oft sie durch zwei teilbar ist, ist sie etwas kleiner oder etwas größer als die Zahl der Münzen, aber immer ungefähr gleich. nlogn oder die Kür des Sortierens 71  Die gesamte Anzahl der Siegerplätze eines K.-o.-Systems ist immer etwa gleich groß wie die Anzahl der Wettbewerber. Wir haben nun also herausgefunden, dass jedes Feld der leeren K.-o.-Tabelle gefüllt werden muss und dass es insgesamt ungefähr n Felder gibt! Nennen wir das einmal n Durchläufe. Beim Füllen eines Feldes müssen gegebenenfalls weiter unten frei werdende Felder mit Nachrückern bestückt werden. Maximal passiert das so oft, wie es Ebenen in der Tabelle gibt. Man nennt die Anzahl der Ebenen auch die Höhe der Tabelle oder ein- fach h. Der Aufwand unseres Tournament-Sorts wird also bestimmt von n Durchläufen mit jeweils h Verschiebeoperationen oder Aufwand = n ⋅ h. Es wäre nun schön, wenn wir die Höhe irgendwie ausrechnen könnten. Ermitteln Sie zunächst durch Probieren, welche Höhe eine Tabelle mit 8, 9, 10, 15, 16, 32 und 64 Karten besitzt. ▶ ▶ ▶ ◀ ◀ ◀ 8 Karten ergeben 4 Ebenen. Bei 9, 10, 15 oder 16 Karten sind es immer 5 Ebenen. Die K.-o.-Tabelle mit 32 Karten hat 6 Ebenen, wie auch einfach am Bastelbogen ablesbar Ebene Anzahl Karten ist. 64 Karten können auf 7 Ebenen sortiert werden. 1 1 Klar wird dies, wenn man bedenkt, dass jede Ebene immer halb so viele Karten enthält 2 2 (ggf. muss aufgerundet werden) wie die darunterliegende Ebene. Die oberste Ebene 3 4 enthält eine Karte. Umgekehrt kann also jede untere Ebene (maximal) doppelt so viele Karten enthalten wie die darüber liegende Ebene. 4 8 5 16 Wenn wir die oberste Ebene mit der Nummer 1 versehen, ergibt sich für das Fassungs- vermögen also die Tabelle am Rand. 6 32 7 64 Eine Tabelle mit 2h Karten besitzt nach dieser Tabelle also h +1 Ebenen! 8 128 Da wir die Anzahl der Karten mit n bezeichnet haben, gilt also nun der Zusammen-...... hang n 2h. h