Selection-Sort

Sortieren Sie die roten Steine in aufsteigender und anschliessend in absteigender Reihenfolge. Beachten Sie die Anzahl notwendiger Schritte.

Bedienung: Mit rechtem Mausklick kann der aktive Stein (weisser Hintergrund) für die grün markierte Position vorgemerkt werden. Ein linker Mausklick springt zum nächsten Stein, ohne den aktuellen vorzumerken. Der vorgemerkte Stein ist gelb markiert.

Beim Selection-Sort wird jeweils das grösste oder kleinste Element ausgewählt und an den Beginn der Folge gesetzt. Dies wird in jedem Schritt mit einem um ein Element kleineren Bereich gemacht. Das kleinste oder grösste Element wird gesucht, indem das bin anhin kleinste bzw. grösste angetroffene Element markiert wird. Der Aufwand von Selection-Sort für n Elemente lässt sich wie folgt berechnen:

(n-1) + (n-2) + ... + 3 + 2 + 1 = (n-1)*n/2

Der Selectionsort-Algorithmus gehört daher zur Komplexitätsklasse 0(n²). Vgl. die sogenannte O-Notation

Hinweis: Ein Computer kann pro Arbeitsschritt nur die Grösse von zwei Steinen vergleichen. In diesem Fall die Grösse des aktiven Steins mit der Grösse des gelb markierten Steins.

fs in ksw - sci

Bubble-Sort

Sortieren Sie die roten Steine in aufsteigender und anschliessend in absteigender Reihenfolge. Beachten Sie die Anzahl notwendiger Schritte.

Bubble-Sort wird auch Sortieren durch Aufsteigen genannt, da die Elemente wie Blasen im Wasser aufsteigen. In der Praxis wird Bubblesort kaum eingesetzt, da andere Verfahren schneller sind. Der Aufwand von Bubble-Sort wächst mit der Anzahl-Spielsteinen n im Quadrat: O(n²). D.h. bei doppelt so vielen Steinen dauert das Sortieren rund viermal so lange. Dieses Verhalten wird mit der sogenannten O-Notation festgehalten.

Hinweis: Man stellt fest, dass der Computer pro Schritt nur die Grösse von zwei Steinen vergleichen kann, und die anderen Steine nicht im "Blick" hat. Dies zeigt die typische Funktionsweise eines Computers.

fs in ksw - sci

Insertion-Sort

Sortieren Sie die roten Steine.

Das Vorgehen ist mit dem Aufnehmen von Karten bei einem Kartenspiel vergleichbar. Die erste Karte wird aufgenommen und an die erste Stelle gesetzt. Nach dem Aufnehmen einer weiteren Karte wird diese von rechts nach links mit den bereits einsortierten Karten verglichen und bei der richtigen Position eingefügt. Die bereits aufgenommenen Karten sind zu jedem Zeitpunkt sortiert. In der Simulation sind die noch nicht aufgenommenen Karten dunkel dargestellt.

Der Aufwand von Insertion-Sort wächst mit der Anzahl-Spielsteinen n im Quadrat: O(n²). D.h. bei doppelt so vielen Steinen dauert das Sortieren rund viermal so lange. » O-Notation

In welcher Reihenfolge die Objekte vorliegen hat einen Einfluss auf den Aufwand. Testen Sie dies, indem Sie die Steine einmal aufsteigend und einmal absteigend sortieren. Im Besten Fall ist Insertion-Sort sogar linear mit O(n), d.h. schneller als komplizierte Sortierverfahren wie Quick-Sort und Merge-Sort.

Aufwandberechnung mit O(n²):

Anzahl Objekte	Anzahl Schritte
4	16
8	64
16	256
32	1'024
64	4'096
128	16'384
256	65'536

fs in ksw - sci

Tournament-Sort

Sortieren Sie die roten Steine und beachten Sie die Anzahl notwendiger Schritte. Findet sich ein Unterschied zwischen aufsteigendem und absteigendem Sortieren?

Vorbild für den Tournamentsort ist ein Tournierspielplan. Es treten immer zwei Objekte gegeneinander an und der Gewinner rückt eine Ebene hoch in Richtung Halbfinal und Final. Die Sieger aus dem Final werden separat aufgereiht und sind bei korrektem Turnierverlauf durch dieses Verfahren sortiert.
Der Aufwand des Tournament-Sort wächst mit der Anzahl-Spielsteinen n logarithmisch: O(n * log₂(n)). » O-Notation

Aufwandberechnung gemäss dieser Formel:

Anzahl Objekte	Anzahl Schritte
4	8
8	24
16	64
32	160
64	384
128	896
256	2'048

fs in ksw - sci

Sortieranweisung

1. Falls dein Stapel nur eine Karte enthält, gib ihn zurück, andernfalls:
2. Teile den Stapel in möglich zwei gleich grosse Teilstapel. Gib jeden Stapel an einen Gehilfen weiter und bitte ihn, den Stapel genau nach dem hier beschriebenen Verfahren zu sortieren.
3. Warte, bis dir beide Gehilfen die sortierten Teilstapel zurückgegeben haben. Dann nimm oben ab den beiden Stapeln mit einer Art Reissverschlussprinzip die Karten so, dass ein sortierter Gesamtstapel entsteht.
4. Gib diesen sortierten Stapel an deinen Meister zurück.

Besprechung

Diese Sortieranweisung ist rekursiv, d.h. sie nimmt auf sich selber Bezug (vgl. 2. Teil von Pkt. ii). Zudem wird das Gesamtproblem in möglichst kleine Teilprobleme zerlegt. Die Methode ein Problem durch Zerlegung in Teilprobleme zu lösen wird "divide et impera"-Prinzip genannt.
Der Aufwand des Merge-Sort wächst mit der Anzahl-Karten n logarithmisch: O(n * log₂(n)). » O-Notation

fs in ksw - sci

Sortieranweisung

1. Falls dein Stapel nur eine Karte enthält, gib ihn zurück, andernfalls:
2. Ziehe eine Karte aus dem Stapel. Durchlaufe die restlichen Karten und lege alle Karten die kleiner oder gleich der gezogenen Karte sind auf Stapel 1. Alle grösseren Karten lege auf den Stapel 2.
3. Gib die beiden Stapel, sofern sie Karten enthalten, an einen Gehilfen weiter und bitte ihn, den Stapel genau nach dem hier beschriebenen Verfahren zu sortieren.
4. Warte, bis dir beide Gehilfen die sortierten Teilstapel zurückgegeben haben. Dann lege auf den Stapel 1 die gezogene Karte und auf diese den Stapel 2. Gib diesen Gesamtstapel an deinen Meister zurück.

Besprechung

Diese Sortiermethode ist rekursiv, d.h. sie nimmt auf sich selber Bezug (vgl. 2. Teil von Pkt. iii). Sie verwendet das Prinzip "divide et impera".
Der Aufwand des Quick-Sort wächst mit der Anzahl Elemente n logarithmisch: O(n * log₂(n)). » O-Notation

Zusätzliche Animation

Äusserst schön umgesetzte Animation von sorting.at.

fs in ksw - sci