|
Bewertung von Sortierverfahrenam Beispiel von Selection Sort |
In den folgenden Überlegungen geht es nur um die Abschätzung der Anzahl der notwendigen Vergleichs- und Tauschoperationen
des Verfahrens.
Andere Fragen, z.B. Speicherplatzbedarf, werden nicht betrachtet.
Beim Vergleich muss auch der Aufwand eines Vergleiches gegen den eines Tausches abgewägt werden.
Im einfachsten Fall bedeutet ein Tausch, dass 3 Zuweisungen vorgenommen werden
(vergl. Einführung). Praktisch ist
der Tausch noch wesentlich auwendiger, da hier komplette Datenstrukturen bewegt werden können.
Um die Abschätzungen nachvollziehen zu können, muss das Verfahren SelectionSort sicher beherrscht weden.
| günstigster Fall (best case) |
ungünstigster Fall (worst case) |
allgemeiner Fall (average case) |
||||
|---|---|---|---|---|---|---|
| Unter welchen Voraussetzungen benötigt das Verfahren die wenigsten Vergleichs- und Tauschoperationen? | Unter welchen Voraussetzungen benötigt das Verfahren die meisten Vergleichs- und Tauschoperationen? | Wie viele Vergleichs- und Tauschoperationen werden bei beliebigen Mengen durchschnittlich benötigt? | ||||
| Gegeben sei eine Menge von n Elementen.
a1 a2 a3 ... an-1 an Wie viele Vergleiche werden gemacht?Im ersten Durchlauf wird das kleinste Element mit allen anderen n-1 Elementen verglichen. Im nächsten Durchlauf fällt das erste Element raus, also nur noch n-2 Vergleiche. ... Im letzten Durchlauf gibt es nur noch 1 Vergleich. Insgesamt sind das (n-1) + (n-2) + (n-3) + ... + 2 + 1 =... Wie es schon der kleine Carl Friedrich Gauß gemacht haben soll, kann man beim Zusammenfassen
die Reihenfolge der Summenden ändern [(n-1)+1] + [(n-2)+2] + [(n-3)+3] + ... = n + n + n + ... Bei (n-1) Zahlen gibt es (n-1)/2 Paare, die sich zu n ergänzen.
Formt man die Gleichung etwas um, sieht der Zusammenhang dann so aus: Die Anzahl der Vergleiche hängt quadratisch von der Anzahl der zu sortierenden Elemente ab. Für das Finden des kleinsten Elementes spielt es keine Rolle, ob es schon an seiner Position stand oder nicht. Die Anzahl der Vergleiche ist von der Vorsortierung unabhängig. Wie oft muss getauscht werden?In jedem Durchlauf muss höchstens einmal getauscht werden. Nämlich genau dann, wenn der gefundene minimale Wert
noch nicht an der richtigen Stelle steht. Das ist genau dann der Fall, wenn die Menge vor dem Sortieren bereits sortiert war. Das Verfahren stellt dann (sehr aufwendig) nur fest, dass die Menge sortiert ist. |
Gegeben sei eine Menge von n Elementen.
a1 a2 a3 ... an-1 an Wie viele Vergleiche werden gemacht?Bei der Herleitung der Anzahl für den günstigsten Fall spielte es keine Rolle, ob nach den Vergleichen getauscht werden musste oder nicht. Hier gilt für die Anzahl der Vergleiche derselbe Wert:
Wie oft muss getauscht werden?Bei jedem Durchlauf muss das kleinste Element an die richtige Position, es wird also höchstens einmal pro Durchlauf getauscht. Im ungünstigsten Fall muss in jedem Durchlauf getauscht werden. Das tritt hier ein, wenn die Menge sortiert ist, aber das kleinste Element an der letzten Stelle steht. Dann wird durch den Tausch in einem Durchlauf das kleinste Element des nächsten Durchlaufs an die letzte Stelle gebracht. Da es (n-1) Durchläufe gibt, gibt es im ungünstigsten Fall (n-1) Tauschoperationen. |
Gegeben sei eine Menge von n Elementen.
a1 a2 a3 ... an-1 an Wie viele Vergleiche werden gemacht?Bei der Herleitung der Anzahl für den günstigsten Fall spielte es keine Rolle, ob nach den Vergleichen getauscht werden musste oder nicht. Hier gilt für die Anzahl der Vergleiche derselbe Wert:
Wie oft muss getauscht werden?Die Sortierung der Menge ist völlig unbekannt. Bei 2 Elementen ist die Wahrscheinlichkeit, dass das Element an der richtigen Stelle steht 1/2. Also liegt die Wahrscheinlichkeit für einen Tausch ebenfalls bei 1/2. Bei 3 Elementen ist die Wahrscheinlichkeit, dass das Element an der richtigen Stelle steht 1/3. Also liegt die Wahrscheinlichkeit für einen Tausch bei 2/3. ... Bei n Elementen ist die Wahrscheinlichkeit, dass das Element an der richtigen Stelle steht 1/n. Also liegt die Wahrscheinlichkeit für einen Tausch bei (n-1)/n. Für alle Durchläufe ergibt sich die wahrscheinliche Anzahl von Tauschoperationen aus 
|
| Aufbau der Menge | Anzahl der Vergleiche | Anzahl der Tauschoperationen | |
| best case | Die Menge ist bereits sortiert. |  |
0 |
| worst case | Die Menge ist sortiert. Nur das kleinste Element steht an letzter Stelle. | |
n-1 |
| average case | Die Menge ist völlig unsortiert. | |
|
