Selection Sort (Auswahl-Sortierung)

Der Selection Sort Algorithmus gehört zu den intuitivsten Sortierverfahren. Er findet wiederholt das kleinste Element im Array und bewegt es an den Anfang. Anschließend sucht er das kleinste Element im verbliebenen Teil des Arrays und wiederholt diesen Vorgang, bis das Ende des Arrays erreicht ist.

a = [...]
for i in range(len(a)):                  # Hier platzieren wir das Minimum von a[i:] an Position a[i]
    min_idx = i                          # Index des kleinsten Elements
    for j in range(i + 1, len(a)):       # Finde den Index des kleinsten Elements
        if a[j] < a[min_idx]:            # Falls wir ein kleineres Element finden
            min_idx = j                  # Aktualisiere den Index des kleinsten Elements
    a[i], a[min_idx] = a[min_idx], a[i]  # Vertausche a[i] und a[min_idx]
print(a)

Bei jeder Iteration nehmen wir das kleinste Element aus dem verbleibenden Array und vertauschen es mit dem aktuellen Element anhand ihrer Indizes. Falls das aktuelle Element bereits das kleinste ist, bleibt das Array unverändert, da das Element sich dann mit sich selbst vertauscht.

Der Selection Sort Algorithmus findet also stets das kleinste Element im Array und vertauscht den aktuellen Index mit diesem Minimum. Das bedeutet, dass in jeder Iteration das gesamte verbleibende Array durchsucht wird, um das Minimum zu finden (die min-Funktion läuft Element für Element durch, um den kleinsten Wert zu ermitteln). Aus diesem Grund hat der Algorithmus insgesamt n Iterationen, die jeweils etwa n Durchläufe beinhalten ⇒ Operationen.

Lassen Sie uns den Algorithmus an einigen Arrays durchspielen:

[4, 1, -1, 0, 2, 8]

i = 0 ⇒ val = -1 ⇒ idx = 2 ⇒ swap ⇒ [-1, 1, 4, 0, 2, 8]

i = 1 ⇒ val = 0 ⇒ idx = 3 ⇒ swap ⇒ [-1, 0, 4, 1, 2, 8]

i = 2 ⇒ val = 1 ⇒ idx = 3 ⇒ swap ⇒ [-1, 0, 1, 4, 2, 8]

i = 3 ⇒ val = 2 ⇒ idx = 4 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]

i = 4 ⇒ val = 4 ⇒ idx = 4 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]

i = 5 ⇒ val = 8 ⇒ idx = 5 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]

[10, 5, 1, -1, -2, -7]

i = 0 ⇒ val = -7 ⇒ idx = 5 ⇒ swap ⇒ [-7, 5, 1, -1, -2, 10]

i = 1 ⇒ val = -2 ⇒ idx = 4 ⇒ swap ⇒ [-7, -2, 1, -1, 5, 10]

i = 2 ⇒ val = -1 ⇒ idx = 3 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]

i = 3 ⇒ val = 1 ⇒ idx = 3 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]

i = 4 ⇒ val = 5 ⇒ idx = 4 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]

i = 5 ⇒ val = 10 ⇒ idx = 5 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]

[1, 2, 3, 4, 5]

i = 0 ⇒ val = 1 ⇒ idx = 0 ⇒ swap ⇒ [1, 2, 3, 4, 5]

i = 1 ⇒ val = 2 ⇒ idx = 1 ⇒ swap ⇒ [1, 2, 3, 4, 5]

i = 2 ⇒ val = 3 ⇒ idx = 2 ⇒ swap ⇒ [1, 2, 3, 4, 5]

i = 3 ⇒ val = 4 ⇒ idx = 3 ⇒ swap ⇒ [1, 2, 3, 4, 5]

i = 4 ⇒ val = 5 ⇒ idx = 4 ⇒ swap ⇒ [1, 2, 3, 4, 5]

Aufgabe

Gegeben n ganze Zahlen, sortieren Sie sie in aufsteigender Reihenfolge mit Hilfe von Selection Sort.

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl n (1 ≤ n ≤ 1000), die die Anzahl der Elemente im Array angibt.

Die nächste Zeile enthält n ganzzahlige Werte (mit ≤ ≤ ), getrennt durch Leerzeichen.

Ausgabe

Das Programm soll das eingegebene Array in aufsteigender Reihenfolge ausgeben.

Examples

Eingabe	Ausgabe
5 5 5 3 2 3	2 3 3 5 5

Aufgabe

Eingabe

Ausgabe

Examples

Constraints

To check your solution you need to sign in

Sign in to continue