, , projekte:vorkurs-informatik:sortieren

Ordnung muss sein: Sortieren

Wie können wir Daten sortieren? Zum Beispiel haben wir eine Liste von Personennamen und wollen diese alphabetisch sortiert haben. Zuerst werden wir per Hand probieren, wie dies gemacht werden kann. Die Grundidee: Wir haben viele Kärtchen (z.B. 10, 20, 40, 80 oder 100 Stück) mit dreistelligen Zahlen. Diese sind etwas durcheinander geraten und wir sortieren diese per Hand. Dabei wird die Zeit gemessen, wie lange dies abhängig von der Anzahl der Karten dauert.

Zeichnet eine Kurve mit der Anzahl der Karten auf der x-Achse und der benötigten Sortier-Zeit in Sekunden auf der y-Achse. Ihr könnt so auch die Zeiten von mehreren Personen vergleichen. Gibt es schnellere Strategien zum Sortieren?

Nun wollen wir überlegen, wie dies auf dem Computer bewerkstelligt werden kann. Auf dem Computer haben wir nur bestimmte, ausgewählte Operationen zur Verfügung. Leider lässt sich nicht alles so leicht programmieren wie wir das per Hand auf dem Tisch machen können.

Sortieren stapelweise

Stellen wir uns vor, wir haben Stapel zur Verfügung auf die wir nur oben was drauflegen können und nur von oben wieder weg nehmen können. Des weiteren können wir zwei Stapel aufeinander stellen, wobei die Reihenfolge der Kärtchen im Stapel gleich bleibt. Reicht das zum Sortieren?

Formalisieren wir zuerst unsere Pseudo-Befehle für Karten-Stapel:

  • leer?: ist der Stapel leer, also ohne Karten? Dann ist er schon sortiert…
  • drauflegen(Karte): die Karte auf den Stapel legen
  • drauflegen(Stapel): den Stapel drauf legen
  • runternehmen: nimmt oberste Karte vom Stapel

Quick-Sort

Die Strategie ist folgende: Bei einem leeren Stapel haben wir nichts zu tun. Ansonsten nehmen wir eine Karte vom Stapel und nennen sie trennwert. Dann wird der restliche Stapel schrittweise abgebaut und zwei neue Stapel aufgebaut. In den einen kommen alle Karten kleiner als der Trennwert und in den anderen Stapel alle größeren und gleich großen. Nun wiederholen wir dies für die beiden Stapel. Diese Rekursion endet bei leeren Stapeln. Sind wir damit fertig, so wissen wir, dass beide Stapel sortiert sind. Also können wir sie einfach aufeinander legen: Zuerst der Stapel mit den kleinen Karten, dann die Trennwert-Karte, dann der Stapel mit den größeren Karten. Das Ergebnis nach dem zusammenlegen muss also wieder sortiert sein und wir sind fertig.

Probiert dies per Hand mit ein paar Karten. Und klappt es? Diskutiert mit anderen oder dem Tutor wenn sich der Stapel nicht sortieren ließ.

Entwerft ein Ablaufdiagramm für Quick-Sort. Es dürfte helfen, zuerst mit kleineren Teilproblemen anzufangen:

  • Gegeben sei ein Stapel und der Trennwert: Wie wird der Stapel in die beiden Stapel mit kleineren und größeren Karten zerlegt?
  • Gegeben sei ein Stapel: Trennen, sortieren und zusammenfügen. Und keine Karte von einem leeren Stapel runternehmen!

Und nun auf dem Computer

Für den Vorkurs wollen wir eine vereinfachte Stapel-Klasse benutzen. Diese kann nur Zeichenketten aufnehmen. Sie heißt vk::Stapel und ist in stapel.hpp definiert (siehe auch cpp-hilfsfunktionen). Implementiert damit den Quick-Sort-Algorithmus. Für ganz ungeduldige gibt es eine Vorlage zum einfüllen der fehlenden Teile: quicksort.cpp.

Sortieren der Reihe nach

Legt eine Reihe Kärtchen nebeneinander. Stellt euch vor, das wir nur noch die Position von zwei Kärtchen in dieser Reihe vertauschen können, z.B. das 5. mit dem 3. Kärtchen. Dies entspricht den Vektoren (="Arrays") in unserer Programmiersprache. Wie können wir diesmal sortieren?

Formalisieren wir zuerst unsere Pseudo-Befehle für solche Karten-Reihen:

  • N: ist die Anzahl der Karten
  • Karte[i]: das Kärtchen, dass zur Zeit an der i-ten Stelle liegt
  • vertausche Karte[i] Karte[j]: vertausche die beiden Karten zwischen Stelle i und j. Die anderen bleiben dort wo sie gerade liegen.

Selection-Sort

Wir suchen die kleinste Karte und vertauschen diese mit der ersten Karte. Nun schauen wir uns die restlichen Kärtchen ab der zweiten an. Die nun kleinste Karte wird zur 2. Stelle hin vertauscht und der Rest ab dem 3. Kärtchen angeschaut. Das geht so weiter bis wir die ganze Reihe durch sind. Probiert dies mal für eine feste Anzahl Karten aus (z.B. 50).

Entwerft ein Ablaufdiagramm für diesen Algorithmus und testet ihn per Hand. Es ist sinnvoll, den Algorithmus in kleinere Teile zu zerlegen. Zum Beispiel:

  • Wie finden wir die Position der kleinsten Karte von Position i bis zum Ende (N)?
  • Wie werden zwei Karten zwischen Position i und j getauscht?
  • Wie sieht die Schleife aus, um schrittweise das kleinste Kärtchen nach Vorne zu tauschen?

Bubble-Sort

Nicht die kleinste Suchen, sondern von Vorne nach Hinten durch die Reihe laufen. Immer wenn die aktuelle Karte größer als die nächste ist, werden beide vertauscht. Dadurch blubbern die großen Karten ans Ende der Reihe. Es wird solange über die Reihe gelaufen, bis es nichts mehr zu vertauschen gab.

Entwerft ein Ablaufdiagramm für diesen Algorithmus und testet ihn per Hand. Der Algorithmus lässt sich wieder in kleinere Teile zerlegen:

  • von 1 bis N über die Reihe laufen und gegebenenfalls benachbarte Kärtchen vertauschen. Als Ergebnis wird zurückgegeben, ob mindestens eine Vertauschung stattfand.
  • solange den ersten Teil ausführen lassen, bis dieser meldet, dass nichts vertauscht wurde.

Das ganze mit Vektoren in C++

Nachdem Ihr die Algorithmen erfolgreich per Hand zum Sortieren angewendet habt, könnt Ihr Bubble-Sort oder Selection-Sort selber programmieren. Im folgenden Quelltext-Fragment seht ihr Beispiele zur Verwendung von Vektoren in C++. Dafür brauchen wir #include <vector> und #include <string>. Die Vertausche-Funktion std::swap wird mit #include <algorithm> importiert. Bei Fragen helfen wie immer gerne die Tutoren weiter.

  // ein Vektor für Zeichenketten deklarieren
  std::vector<std::string> namen;
 
  // eine Reihe aufbauen: was anhängen
  namen.push_back("Meier");
  namen.push_back("Lügenscheidt");
  namen.push_back("Treufuß");
 
  // die Anzahl der Einträge erfragen
  int N = namen.size();
 
  // durchlaufen und ausgeben
  int i=0;
  while (i<N) {
    vk::println( namen[i] );
    i = i+1;
  }
 
  // vertauschen des 3. und 1. Eintrags 
  std::string temp = namen[1];
  namen[1] = namen[3];
  namen[3] = temp;
 
  // vertauschen, kürzere Variante
  std::swap(namen[1], namen[3]);

QuickSort auf Vektoren

Diskutieren Sie, wie die folgenden Teilschritte von Quicksort auf Vektoren umgesetzt werden könnten. Testen Sie ihre Ideen per Hand mit ein paar Karten.

  • Auswahl des Trennwertes
  • Trennen des Vektors in kleinere und größere Werte. Dies kann z.B. durch std::swap Schritte innerhalb des selben Vektors gemacht werden.
  • Zusammenfügen der einzelnen Vektoren oder Teilvektoren.

Experimentieren: Was ist schneller

Welcher der 3 Algorithmen zum Sortieren in Vektoren ist wohl der schnellste? Erzeugen Sie dafür große Test-Daten (zum Beispiel Zufallszahlen mit vk::random_int(max) und schreiben sie diese in eine Datei. Messen Sie dann die Zeiten, die für das Sortieren der Daten notwendig sind (z.B. mit einer Stoppuhr). Wie könnte die Genauigkeit dieser Messungen verbessert werden?

Mit generate > daten.txt können wir die Ausgabe des Programms generate in die Datei daten.txt schreiben. Ähnlich können wir auch die Eingabe aus einer Datei holen: quicksort < daten.txt.

projekte/vorkurs-informatik/sortieren.txt · Zuletzt geändert: 28.09.2009 02:09 von rrotta