In diesem Beitrag geht es um die Implementierung eines einfachen Sortierungs-Algorithmus, der die Bezeichnung Selection Sort hat. Dabei wird hier auf die Programmiersprache Python zurückgegriffen. Ausgangspunkt für dieses Beispiel ist eine Liste mit fünf Ganzzahlen:

numbers = [27, 4, 11, 33, 9]

Funktionsweise

Bevor es an den Code geht, erkläre ich zunächst die Funktionsweise des Selection Sort. Die Liste wird von Index 0 bis zum Ende durchlaufen, wobei überprüft wird, ob der jeweilige Wert des aktuellen Index der bisher niedrigste Wert ist. Übertragen auf die Liste numbers bedeutet dies, dass zunächst der Wert 27 an Index 0 der niedrigste Wert ist. Dieser Index wird daher einer Variable zugewiesen, die stets den niedrigsten Wert gespeichert haben soll (im Code ist dies später die Variable min_index).

Es folgt jetzt Index 1 mit dem Wert 4, der niedriger ist als der Wert 27. Also ist jetzt 4 der niedrigste Wert, was wiederum bedeutet, dass unserer Variable min_index jetzt der Index 1 zugewiesen wird.

Betrachten wir die Werte an den Indizes 2 bis 4 stellen wir fest, dass kein Wert niedriger ist als die Zahl 4 an Index 1. Unsere Variable min_index speichert also bis zum Ende des ersten Durchlaufs Index 1 (mit dem Wert 4).

Zum Schluss wird dann der Wert an Index 1 mit dem Wert von Index 0 getauscht, so dass nach dem ersten Durchlauf in diesem Beispiel die Zahl 4 an erster Position steht.

Jetzt beginnt der zweite Durchlauf. Da wir wissen, dass sich an erster Position (Index 0) die Zahl mit dem niedrigsten Wert befindet, beginnen wir jetzt bei Index 1. Im nächsten Durchlauf wird dann bei Index 2 begonnen, usw. Dies führt letztendlich zu einer sortierten Liste.

Python-Code

In Python könnte die Implementierung wie folgt aussehen:

#!/usr/bin/env python3

def selection_sort(seq: list) -> list:

    for i in range(len(seq)):
        min_index = i

        for j in range(i + 1, len(seq)):
            if seq[j] < seq[min_index]:
                min_index = j

        seq[i], seq[min_index] = seq[min_index], seq[i]

    return seq


if __name__ == '__main__':
    numbers = [27, 4, 11, 33, 9]
    sorted_numbers = selection_sort(numbers)
    print(sorted_numbers)

Als Ergebnis wird die sortierte Liste [4, 9, 11, 27, 33] ausgegeben.