Sortiermethoden

Beschreibung / Inhalt
Das Dokument ist eine Zusammenstellung von Algorithmen zur Sortierung von Arrays. Es werden drei verschiedene Verfahren beschrieben: Selection Sort, Insertion Sort und Bubble Sort.

Selection Sort funktioniert, indem das kleinste verbleibende Element ausgewählt und mit dem an erster Stelle befindlichen Element ausgetauscht wird. Danach wird das zweitkleinste Element ausgewählt und an zweiter Stelle einsortiert. Dieser Prozess wird fortgesetzt, bis das gesamte Array sortiert ist.

Insertion Sort sortiert das Array, indem die Elemente eins nach dem anderen betrachtet werden und an ihrem richtigen Platz innerhalb des bereits sortierten Bereichs einsortiert werden. Das betrachtete Element wird in die sortierte Liste eingefügt, indem größere Elemente um eine Position nach rechts verschoben werden und das betrachtete Element auf dem freigewordenen Platz eingefügt wird.

Bubble Sort vergleicht benachbarte Elemente und vertauscht sie, wenn es notwendig ist. Bei jedem Durchlauf wird das größte Element an die rechte Seite des Arrays geschoben.

Das Dokument enthält auch eine Tabelle, die die Abschätzungen der Best-Case-, Average-Case- und Worst-Case-Laufzeiten der Algorithmen sowie ihre asymptotische Ordnung angibt.

Zusammenfassend bietet das Dokument eine umfassende Beschreibung der drei Arten von Sortieralgorithmen und gibt eine Abschätzung ihrer Leistungsbewertungen an.
Direkt das Referat aufrufen

Auszug aus 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 - ...
Direkt das Referat aufrufen