/ Algorithmen & Komplexität

Selection Sort Vergleiche

Anzahl Vergleiche beim Selection Sort — unabhängig von der Eingabereihenfolge: Vergleiche = n · (n − 1) / 2.

01 · Eingabe

Selection Sort Vergleiche berechnen

Anzahl Vergleiche beim Selection Sort — unabhängig von der Eingabereihenfolge: Vergleiche = n · (n − 1) / 2.

Lösen für

Vergleiche = n · (n − 1) / 2

n Elementanzahl

Worum geht es?

Selection Sort sucht in jeder Iteration das Minimum des unsortierten Restbereichs und schiebt es an die nächste Position. Dabei sind die Vergleiche unabhängig von der Eingabereihenfolge — egal ob sortiert, zufällig oder gegensortiert, es werden immer n · (n − 1) / 2 Vergleiche durchgeführt.

Die Anzahl der Tausche ist dagegen mit O(n) deutlich geringer als bei Bubble Sort. Das macht Selection Sort attraktiv, wenn das Schreiben (etwa auf langsame Medien) teuer ist und das Lesen billig.

Die Formel

Formel Selection Sort

Vergleiche = n · (n − 1) / 2

Umstellung:
    n = (1 + √(1 + 8 · Vergleiche)) / 2

Die Variablen

Symbol	Bedeutung	Einheit	Erklärung
n	Elementanzahl	—	Anzahl zu sortierender Elemente.
Vergleiche	Vergleiche	—	Anzahl Vergleiche (immer gleich).

Minimal-Beispiel

n = 8 Elemente:

Rechnung Vergleiche

Vergleiche = 8 · 7 / 2
           = 28

Praxis-Beispiele

Beispiel 1 — n = 500

Rechnung n = 500

Vergleiche = 500 · 499 / 2
           = 124 750

Beispiel 2 — Best Case = Worst Case

Eine bereits sortierte Eingabe ändert nichts:

Rechnung Unabhängigkeit

n = 100   →   Vergleiche = 4950
(gleich für sortiert, zufällig, gegensortiert)

Beispiel 3 — Tauschvergleich zu Bubble Sort

n = 1000, gegensortiert:

Rechnung Schreibzugriffe

Selection:  Vergleiche 499 500   Tausche  ≤ 999
Bubble:     Vergleiche 499 500   Tausche  499 500

Selection Sort schreibt ca. 500× weniger.