Sortiermethoden

Schlagwörter:
Referat, Hausaufgabe, Sortiermethoden
Themengleiche Dokumente anzeigen

Referat
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 a j 1 ) x a j ; a j a j 1 ; a j 1 x; 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 4. Abschätzung Selection Sort Insertion Sort Bubblesort C min n - 1 n - n 2 n - n 2 C n n - 2 4 n - n 2 n - n 2 C max n n - ...

Autor:
Kategorie:
Sonstiges
Anzahl Wörter:
1304
Art:
Fachbereichsarbeit
Sprache:
Deutsch
Bewertung dieser Hausaufgabe
Diese Hausaufgabe wurde bislang noch nicht bewertet.
Zurück