[Java] Sortieren durch Auswahl (Selection Sort)

Grievous
Supermoderator
Beiträge: 893

Aktivitätspunkte: 5 060

Registrierungsdatum: 16. August 2009

Wohnort: Berlin

Beruf: Schüler

Danksagungen: 237 / 35

Freitag, 28. Januar 2011, 13:24

Sortieren durch Auswahl (Selection Sort)

Beschreibung

Überblick:
Sortieren durch Auswahl (Selection Sort) ist ein einfacher Sortieralgorithmus. Dieser Sortieralgorithmus hat jedoch eine Zeitkomplexität von Θ(n²) und ist damit für größere Datenmengen nicht geeignet.

Funktionsweise:
Der sortierte Teil ist zum Anfang leer. Wir suchen bei jedem Durchgang aus dem unsortierten Teil das Element mit dem kleinsten Inhalt heraus und vertauschen es mit dem ersten Element des unsortierten Teils.

9 ist die Grenze.
(alle Zahlen bis 9 sind bereits sortiert)

1 3 5 9 - 10 6 13 11
sortiert - unsortiert

9 und 6 werden getauscht.

Dann erhöhen wir die Grenze des sortierten Teils um ein Element und wiederholen den Vorgang bis das Feld sortiert ist.

Anzahl der Suchaktionen:
Im ungünstigsten Fall finden nach Aufstellen der gaußschen Summenformel ½ ⋅ (n²-n) Suchaktionen statt. Im günstigstens Fall liegt die Anzahl der Suchaktionen ebenfalls bei ½ ⋅ n² - ½ ⋅ n.

Anzahl der Tauschaktionen:
Im ungünstigsten Fall finden n Tauschaktionen statt. Im günstigsten Fall liegt die Anzahl der Tauschaktionen jedoch bei 0.