Selection Sort Sortieren durch direktes Auswahlen

1. Selection Sort (Sortieren durch direktes Auswählen)

Dieser Algorithmus läuft wie folgt ab: Finde zuerst das kleinste Element im Feld und tausche es gegen das an der ersten Stelle befindliche Element aus, finde danach das zweitkleinste Element und tausche es gegen das an zweiter Stelle befindliche Element aus und fahre in dieser Weise fort, bis das gesamte Feld sortiert ist. Diese Methode wird Selection Sort (Sortieren durch direktes Auswählen) genannt, da sie darin besteht, daß wiederholt das kleinste verbliebene Element >>ausgewählt<< wird, wie in Abbildung 1 dargestellt ist.

Das nachfolgende Programm ist eine Implementation dieses Prozesses. Für jedes i von bis

N - 1 tauscht es a[i] gegen das kleinste Element in a[i], .., a[N] aus:

void straightselection (int a[ ], int N)

}

Während der Index i von links nach rechts durch die Datei wandert, befinden sich die Elemente links vom Index auf ihrer entgültigen Position im Feld (und werden nicht wieder berührt), so daß das Feld vollständig sortiert ist, wenn der Index das rechte Ende erreicht.

Vorteil dieser Methode ist, daß jedes Element wirklich höchstens einmal bewegt wird.

i = 1:                                 i = 5:

min = 1 6 min = 5 6 8

j = 2 3 4 5 6 7 8 j = 6 7 8

t = 01 t = 16

i = 2:                                 i = 6:

min = 2 6 min = 6

j = 3 4 5 6 7 8 j = 7 8

t = 04 t=

i = 3:                                 i = 7:

min = 3 4 6 min = 7 8

j = 4 5 6 7 8 j = 8

t= 07 t= 55

i = 4:

min = 4 8

j = 5 6 7 8

t = 12

Abbildung 1 Selection Sort

2. Insertion Sort (Sortieren durch direktes Einfügen)

Dies ist die Methode, die Menschen oft beim Kartenspielen anwenden, um ihre Karten zu sortieren: Betrachte die Elemente eines nach dem anderen und füge jedes an seinen richtigen Platz zwischen den bereits betrachteten ein (wobei diese sortiert bleiben). Das gerade betrachtete Element wird eingefügt, indem die größeren Elemente einfach um eine Position nach rechts bewegt werden und das Element dann auf dem freigewordenen Platz eingefügt wird, wie Abbildung 2 zeigt.

Dieser Prozeß ist im folgenden Programm implementiert. Für jedes i von bis N werden die Elemente a[1], .., a[i] sortiert, indem a[i] an die entsprechende Stelle in der sortierten Liste von Elementen in a[1], ., a[i - 1] gesetzt wird:

void straightinsertion (int a[ ], int N)

a[j+1] = v;

}

}

Beim Selection Sort sind die Elemente links vom Zeiger i während des Sortierens in einer sortierten Reihenfolge angeordnet, doch sie befinden sich nicht auf ihrer endgültigen Position, da sie möglicherweise bewegt werden müssen, um für später gefundene kleinere Elemente Platz zu machen. Das Feld ist jedoch vollständig sortiert, wenn der Zeiger das rechte Ende erreicht.

Es muß jeoch eine wichtige Einzelheit beachtet werden: Für die meisten Eingaben funktioniert die Prozedur insertion nicht! Die while-Anweisung läuft über das linke Ende des Feldes hinaus, wenn v das kleinste Element im Feld ist. Um Abhilfe zu schaffen, setzen wir einen >>Marken<<-Schlüssel auf a[0], den wir mindestens so klein wählen wie das kleinste Element im Feld. Marken werden gewöhnlich in Situationen wie dieser verwendet, um die Aufnahme eines nahezu im positiv ausfallenden Test (im vorliegenden Falle j > i) in die innere Schleife zu vermeiden.

i = 2:                                 i = 6:

v = 07 v = 01

a[0] = 07 a[0] = 01

j = 1 j = 5 4 3 2 1

i = 3:                                 i = 7:

v = 23 v = 63

a[0] = 23 a[0] = 63

j = 2 j = 6

i = 4:                                 i = 8:

v = 16 v = 12

a[0] = 16 a[0] = 12

j = 3 2 j = 7 6 5 4

i = 5:

v = 55

a[0] = 55

j = 4

Abbildung 2 Insertion Sort

3. Bubblesort (Sortieren durch direktes Austauschen)

Das Prinzip ist folgendes: Durchlaufe immer wieder das Feld und vertausche jedesmal, wenn es notwendig ist, benachbarte Elemente; wenn bei einem Durchlauf kein Austausch mehr erforderlich ist, ist das Feld sortiert. Eine Implementation des Verfahrens wird nachfolgend angegeben:

void bubblesort (int a[ ], int N)

}

Man muß etwas nachdenken, um sich davon zu überzeugen, daß dieser Weg überhaupt zum Ziel führt. Hierzu bemerken wir, daß jedesmal, wenn während des ersten Durchlaufs das maximale Element vorgefunden wird, dieses mit jedem der rechts von ihm befindlichen Elemente vertauscht wird, und dies so lange, bis es die Position am rechten Ende des Feldes erreicht hat. Während des zweiten Durchlaufs wird dann das zweitgrößte Element an die richtige Position bewegt usw. Somit läuft der Bubble Sort wie eine Abart des Selection Sort ab, obwohl viel mehr Aufwand getrieben wird, um jedes Element an die richtige Position zu bringen.

i = 8:                                 i = 4:

j = 1 2 3 4 5 6 7 j = 1 2 3

x= 23 55 63 x = 04

i = 7:                                 i = 3:

j = 1 2 3 4 5 6 j = 1 2

x = 23 55 x =

i = 6:                                 i = 2:

j = 1 2 3 4 5 j = 1

x = 16 23 x =

i = 5:

j = 1 2 3 4

x = 07 16

Abbildung 3 Bubble Sort

Abschätzung