Insertion Sort
Das Sortieren durch direktes Einfügen funktioniert folgendermaßen:
Man betrachte der Reihe nach die Elemente mit dem Index 2 bis
N. Dabei überprüft man immer die, zwangsmäßig schon
sortierten, Element links davon, ob sie größer sind, als das
momentan betrachtete. Ist dies der Fall, so rutschen sie ein Platz nach
rechts. Ist das nicht (mehr) der Fall, so wird rechts von diesem Element,
das kleiner ist, als das betrachtete, in den, durch Rechtsverschiebung
der anderen Elemente entstandenen Leerraum, das als Vergleichswert fungierende
eingefügt.
Folge: alle Element links von ihm sind kleiner, als es selbst, aber
nicht alle rechts von ihm müssen zwangsläufig größer sein.
Im durchschnittlichen Fall werden N²/4 Vergleiche und N²/8
Austauschoperationen durchgeführt. Im ungünstigsten Fall steigen
diese Zahlen auf N²/2 Vergleiche und N²/4 Austauschoperationen.
Achtung: In feld[0] muß
ein Wert gesetzt werden, der kleiner ist, als alle anderen im Feld, da
sonst die while-Schleife über das linke Feldende laufen kann. Alternativ
kann auch der Schleifenkopf auf while(j>1
&& feld[j-1] > v) erweitert werden, was jedoch nicht empfehlenswert
ist, da die Komplexität der inneren Schleife ansteigt, was Leistungseinbußen
zur Folge hat.
void cm_Insertion(itemType feld[], int N) {
int i, j;
itemType wert;
for(i=2; i<=N; ++i) {
wert = feld[i];
j = i;
while(feld[j-1] > wert) {
feld[j] = feld[j-1];
--j;
}
feld[j] = wert;
}
}
|
Computer
Programmieren (incl. C++ Kurs)
Algorithmen
Bücher
Zeitschriften
Heavy Metal
Mountainbiking
Meine Katze
Über mich und die Site
Links
Downloads
Gästebuch
HP mit Umfrage
