Was ist selectionsort?

Selectionsort

Selectionsort ist ein einfacher, vergleichsbasierter Sortieralgorithmus. Er sortiert ein Array, indem er wiederholt das kleinste (oder größte, je nach Sortierreihenfolge) Element aus dem unsortierten Teil des Arrays findet und es mit dem ersten Element des unsortierten Teils austauscht. Dieser Vorgang wird für den restlichen unsortierten Teil des Arrays wiederholt, bis das gesamte Array sortiert ist.

Wie es funktioniert:

1. Finde das Minimum: Durchsuche den unsortierten Teil des Arrays, um das kleinste Element zu finden.
2. Tausche: Tausche das kleinste Element mit dem ersten Element des unsortierten Teils.
3. Wiederhole: Wiederhole die Schritte 1 und 2 für den verbleibenden unsortierten Teil des Arrays.

Beispiel:

Betrachten wir das Array [64, 25, 12, 22, 11].

1. Das kleinste Element ist 11. Wir tauschen 11 mit 64, sodass das Array jetzt [11, 25, 12, 22, 64] ist.
2. Der unsortierte Teil ist jetzt [25, 12, 22, 64]. Das kleinste Element ist 12. Wir tauschen 12 mit 25, sodass das Array jetzt [11, 12, 25, 22, 64] ist.
3. Der unsortierte Teil ist jetzt [25, 22, 64]. Das kleinste Element ist 22. Wir tauschen 22 mit 25, sodass das Array jetzt [11, 12, 22, 25, 64] ist.
4. Der unsortierte Teil ist jetzt [25, 64]. Das kleinste Element ist 25. Wir tauschen 25 mit 25 (keine Änderung), sodass das Array jetzt [11, 12, 22, 25, 64] ist.
5. Das Array ist jetzt sortiert.

Eigenschaften:

• Einfachheit: Selectionsort ist leicht zu verstehen und zu implementieren.
• In-Place Sortierung: Er sortiert das Array direkt, ohne zusätzlichen Speicherplatz zu benötigen.
• Nicht stabil: Selectionsort ist nicht stabil, was bedeutet, dass die relative Reihenfolge gleicher Elemente möglicherweise nicht erhalten bleibt. Siehe: https://de.wikiwhat.page/kavramlar/Stabilität%20(Sortieralgorithmus)
• Schlechte Performance: Selectionsort hat eine Zeitkomplexität von O(n^2) in allen Fällen (bester, durchschnittlicher und schlechtester Fall), was ihn für große Datensätze ineffizient macht. Siehe: https://de.wikiwhat.page/kavramlar/Zeitkomplexität

Verwendung:

Selectionsort ist in der Praxis selten die beste Wahl. Aufgrund seiner schlechten Performance wird er in der Regel nur für kleine Datensätze oder zu Lehrzwecken verwendet. Für größere Datensätze sind effizientere Algorithmen wie Mergesort, Quicksort oder Heapsort besser geeignet. Siehe: https://de.wikiwhat.page/kavramlar/Mergesort, https://de.wikiwhat.page/kavramlar/Quicksort, https://de.wikiwhat.page/kavramlar/Heapsort