Demonstration von Sortierverfahren

SortierverfahrenZu den Grundalgorithmen der Informatik gehören die Sortierverfahren. In nahezu jeder Anwendung treten sie in der einen oder anderen Form auf.

Jedes der Verfahren beinhaltet Vorteile und Nachteile. Neben langsamen Algorithmen, die aber einfach zu programmieren sind, findet man sehr schnelle mit anspruchsvoller Umsetzung.

In diesem Unterprogramm werden 18 Sortierverfahren simuliert, d.h., deren Wirkungsweise wird anhand einer grafischen Darstellung demonstriert. Zu den Verfahren gehören:
Bubble-Sort und zwei modifizierte Verfahren, Shaker-, Insert-, Heap-, Shell-Sort, die sehr schnellen Select- und Quick-Sort und weitere Verfahren.

An dem Rollbalken stellen Sie zuerst die gewünschte Anzahl der zu sortierenden Zahlen von 200 bis 16000 ein.
Innerhalb der Listbox wählen Sie eines der Verfahren und starten die Simulation über Sortieren. Danach simuliert das Programm in einem Fenster die Wirkungsweise des Verfahrens, indem nach jedem Einzelsortiervorgang (Tausch eines Elements) deren relative Position zu den anderen Elementen grafisch veranschaulicht wird.

Zur Charakterisierung der Güte eines Sortierverfahrens wählt man oft drei verschiedene Ausgangssituationen:

         1. zufällig verteilte Zahlen
         2. entgegengesetzt vorsortierte Zahlen
         3. schon sortierte Zahlen

Diese drei Möglichkeiten stellt Ihnen das Programm dar. Wählen Sie z.B. das Quick-Sort-Verfahren, so können Sie sehr gut das rekursive Aufspalten der Ausgangsmenge in immer kleinere Mengen nachvollziehen. Bubble-Sort verdeutlicht die Herkunft des Namens (Bubble = Blase), da Sie dort sehen können, wie die einzelnen Elemente als „Blasen“ aufsteigen, hier nach rechts wandern.

Beachten Sie bitte: Die angezeigten Sortierzeiten werden durch die grafische Anzeige eines jeden Elementtauschs völlig verfälscht. Sortierzeiten von 1 Min. und mehr für 4000 Zahlen und das Verfahren Bubble-Sort sind in der Praxis völlig undiskutabel.

Demonstration von Sortierverfahren
Herunterladen

Download

Dieses Teilprogramm kann hier als Einzelprogramm heruntergeladen werden.

Ein wesentlich umfangreicheres Programm zu Sortierverfahren finden Sie unter: Sortierkino
Dr.-Ing. Ansgar Matthes hat in diesem Programm eine sehr große Anzahl verschiedener Sortieralgorithmen grafisch veranschaulicht.

Einfache Sortierverfahren

In einem 2.Programm können Sie einfache Sortiervorgänge nachvollziehen. Dazu wählen Sie zuerst, welchen Sortieralgorithmus Sie untersuchen möchten. Vorgegeben sind:

  • Insert-Sort, Sortieren durch direktes Einfügen
  • Bubble-Sort, Sortieren durch direkten Austausch
  • Bubble-Sort (2), Sortieren durch direkten Austausch mit Optimierung des Abbruchs
  • Ripple-Sort, Sortieren durch paarweisen Austausch
Einfache Sortierverfahren
Herunterladen

Betätigen Sie den Schalter neue Werte, so erzeugt das Programm zehn Zahlen, die dem zweiten Auswahlkriterium entsprechen und stellt diese von oben nach unten grafisch dar. Für die Bereitstellung der Elemente können Sie wählen zwischen

  • Zufällige Werte
  • Vorsortierte Werte
  • Entgegengesetzt sortierte Werte
  • Fast sortierte Werte, d.h., bis auf ein Element sind alle in der richtigen Reihenfolge

Starten Sie nun die Simulation mit dem Schalter Neustart, so beginnt das Programm, die Zahlen zu sortieren. Die Geschwindigkeit des Ablaufs stellen Sie an dem Rollbalken ein. Klicken Sie auf einen der Abbruch-Schalter und anschließend auf Fortsetzung, wird der Sortiervorgang an der Unterbrechung einfach fortgesetzt.

Bei Insert-Sort sehen Sie zum Beispiel, wie eine gewählte Zahl nach oben wandert und über einem kleineren Element eingefügt wird. Dieses Sortierverfahren wird von den meisten Menschen genutzt, wenn zum Beispiel Karteikarten zu sortieren sind. Bubble-Sort trägt seinen Namen, weil hier große Zahlen wie Luftblasen im Wasser nach oben wandern. Ripple-Sort wiederum ordnet die Zahlen, indem wellenförmige Bewegungen durch die Zahlenmenge laufen.