Selection Sort: Algorithmus erklärt mit Python Codebeispiel

Was ist Auswahlsortierung?

AUSWAHL SORTIEREN ist ein Vergleichssortierungsalgorithmus, der zum Sortieren einer zufälligen Liste von Elementen in aufsteigender Reihenfolge verwendet wird. Der Vergleich erfordert nicht viel zusätzlichen Platz. Es benötigt nur einen zusätzlichen Speicherplatz für die temporäre Variable.

Dies ist bekannt als an Ort und Stelle Sortierung. Die Auswahlsortierung hat eine Zeitkomplexität von O(n²), wobei n die Gesamtzahl der Elemente in der Liste ist. Die Zeitkomplexität misst die Anzahl der Iterationen, die zum Sortieren der Liste erforderlich sind. Die Liste ist in zwei Abschnitte unterteilt: Die erste Liste enthält sortierte Elemente, während die zweite Liste unsortierte Elemente enthält.

Standardmäßig ist die sortierte Liste leer und die unsortierte Liste enthält alle Elemente. Die unsortierte Liste wird dann nach dem Mindestwert durchsucht, der dann in die sortierte Liste eingefügt wird. Dieser Vorgang wird wiederholt, bis alle Werte verglichen und sortiert wurden.

Wie funktioniert die Auswahlsortierung?

Das erste Element in der unsortierten Partition wird mit allen Werten auf der rechten Seite verglichen, um zu prüfen, ob es sich um den Mindestwert handelt. Wenn es nicht der Mindestwert ist, wird seine Position mit dem Mindestwert getauscht.

Beispiel

Wenn beispielsweise der Index des Mindestwerts 3 ist, wird der Wert des Elements mit Index 3 auf Index 0 platziert, während der Wert, der sich auf Index 0 befand, auf Index 3 platziert wird. Wenn das erste Element in der unsortierten Partition ist den Mindestwert, dann gibt es seine Positionen zurück.
Das als Minimalwert ermittelte Element wird dann in die Partition auf der linken Seite, die sortierte Liste, verschoben.
Die partitionierte Seite hat jetzt ein Element, während die unpartitionierte Seite (n – 1) Elemente hat, wobei n die Gesamtzahl der Elemente in der Liste ist. Dieser Vorgang wird immer wieder wiederholt, bis alle Elemente anhand ihrer Werte verglichen und sortiert wurden.

Problem Definition

Eine Liste mit Elementen in zufälliger Reihenfolge muss in aufsteigender Reihenfolge sortiert werden. Betrachten Sie die folgende Liste als Beispiel.

[21,6,9,33,3]

Die obige Liste sollte sortiert werden, um die folgenden Ergebnisse zu erzielen

[3,6,9,21,33]

Lösung (Algorithmus)

Schritt 1) Ermitteln Sie den Wert von n, der der Gesamtgröße des Arrays entspricht

Schritt 2) Teilen Sie die Liste in sortierte und unsortierte Abschnitte auf. Der sortierte Abschnitt ist zunächst leer, während der unsortierte Abschnitt die gesamte Liste enthält

Schritt 3) Wählen Sie den Mindestwert aus dem unpartitionierten Abschnitt aus und platzieren Sie ihn im sortierten Abschnitt.

Schritt 4) Wiederholen Sie den Vorgang (n – 1) Mal, bis alle Elemente in der Liste sortiert sind.

Visuelle Darstellung

Die folgenden Abbildungen zeigen, wie der Auswahlsortieralgorithmus bei der Sortierung einer Liste mit fünf Elementen die Werte durchläuft.

Das folgende Bild zeigt die unsortierte Liste

Schritt 1)

Der erste Wert 21 wird mit den restlichen Werten verglichen, um zu prüfen, ob es sich um den Minimalwert handelt.

3 ist der Mindestwert, daher sind die Positionen von 21 und 3 vertauscht. Die grün hinterlegten Werte stellen den sortierten Teil der Liste dar.

Schritt 2)

Der Wert 6, der das erste Element in der unsortierten Partition ist, wird mit den übrigen Werten verglichen, um herauszufinden, ob ein niedrigerer Wert vorhanden ist

Der Wert 6 ist der Minimalwert, er behält also seine Position.

Schritt 3)

Das erste Element der unsortierten Liste mit dem Wert 9 wird mit den übrigen Werten verglichen, um zu prüfen, ob es sich um den Mindestwert handelt.

Der Wert 9 ist der Mindestwert, sodass er seine Position in der sortierten Partition behält.

Schritt 4)

Der Wert 33 wird mit den restlichen Werten verglichen.

Der Wert 21 ist kleiner als 33, daher werden die Positionen vertauscht, um die obige neue Liste zu erstellen.

Schritt 5)

Wir haben nur noch einen Wert in der unpartitionierten Liste. Daher ist es bereits sortiert.

Die endgültige Liste ähnelt der im obigen Bild gezeigten.

Auswahl Sortieren Programm mit Python 3

Der folgende Code zeigt die Implementierung der Auswahlsortierung mit Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ): 
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

Die Ausführung des obigen Codes erzeugt folgende Ergebnisse

[3, 6, 9, 21, 33]

Code Erklärung

Die Erklärung für den Code lautet wie folgt

Hier ist die Code-Erklärung:

Definiert eine Funktion namens „selectionSort“.
Ruft die Gesamtzahl der Elemente in der Liste ab. Wir benötigen dies, um die Anzahl der Durchgänge beim Wertevergleich zu bestimmen.
Äußere Schleife. Verwendet die Schleife, um die Werte der Liste zu durchlaufen. Die Anzahl der Iterationen beträgt (n – 1). Der Wert von n ist 5, also ergibt (5 – 1) 4. Das bedeutet, dass die äußeren Iterationen viermal durchgeführt werden. In jeder Iteration wird der Wert der Variablen i der Variablen minValueIndex zugewiesen
Innere Schleife. Verwendet die Schleife, um den Wert ganz links mit den anderen Werten auf der rechten Seite zu vergleichen. Der Wert für j beginnt jedoch nicht beim Index 0. Er beginnt bei (i + 1). Dadurch werden die Werte ausgeschlossen, die bereits sortiert wurden, sodass wir uns auf Elemente konzentrieren, die noch nicht sortiert wurden.
Sucht den Mindestwert in der unsortierten Liste und platziert ihn an der richtigen Position
Aktualisiert den Wert von minValueIndex, wenn die Austauschbedingung wahr ist
Vergleicht die Werte der Indexnummern minValueIndex und i, um festzustellen, ob sie ungleich sind.
Der Wert ganz links wird in einer zeitlichen Variablen gespeichert
Der niedrigere Wert von der rechten Seite nimmt die erste Position ein
Der im Zeitwert gespeicherte Wert wird an der Position gespeichert, die zuvor der Minimalwert innehatte
Gibt die sortierte Liste als Funktionsergebnis zurück
Erstellt eine Liste el mit Zufallszahlen
Drucken Sie die sortierte Liste nach dem Aufruf der Auswahlsortierfunktion und übergeben Sie dabei el als Parameter.

Zeitliche Komplexität der Auswahlsortierung

Die Sortierkomplexität wird verwendet, um die Anzahl der Ausführungszeiten auszudrücken, die zum Sortieren der Liste erforderlich sind. Die Implementierung besteht aus zwei Schleifen.

Die äußere Schleife, die die Werte einzeln aus der Liste auswählt, wird n-mal ausgeführt, wobei n die Gesamtzahl der Werte in der Liste ist.

Die innere Schleife, die den Wert aus der äußeren Schleife mit den restlichen Werten vergleicht, wird ebenfalls n-mal ausgeführt, wobei n die Gesamtzahl der Elemente in der Liste ist.

Daher beträgt die Anzahl der Ausführungen (n * n), was auch als O(n) ausgedrückt werden kann²).

Die Auswahlsortierung hat drei Komplexitätskategorien, nämlich;

Schlimmsten Fall – hier erfolgt die Auflistung in absteigender Reihenfolge. Der Algorithmus führt die maximale Anzahl von Ausführungen durch, die als [Big-O] O(n) ausgedrückt wird²)
bester Fall – dies tritt auf, wenn die bereitgestellte Liste bereits sortiert ist. Der Algorithmus führt die Mindestanzahl von Ausführungen aus, die als [Big-Omega] ?(n²)
Durchschnittlicher Fall – dies tritt auf, wenn die Liste in zufälliger Reihenfolge ist. Die durchschnittliche Komplexität wird ausgedrückt als [Big-theta] ?(n²)

Die Auswahlsortierung weist eine Speicherkomplexität von O(1) auf, da sie eine zeitliche Variable zum Austauschen von Werten erfordert.

Wann sollte die Auswahlsortierung verwendet werden?

Die Auswahlsortierung eignet sich am besten, wenn Sie Folgendes tun möchten:

Sie müssen eine kleine Liste von Elementen in aufsteigender Reihenfolge sortieren
Wenn die Kosten für den Austausch von Werten unbedeutend sind
Es wird auch verwendet, wenn Sie sicherstellen müssen, dass alle Werte in der Liste überprüft wurden.

Vorteile der Auswahlsortierung

Die Vorteile der Auswahlsortierung sind folgende

Es funktioniert sehr gut bei kleinen Listen
Es handelt sich um einen In-Place-Algorithmus. Es benötigt nicht viel Platz zum Sortieren. Für die Speicherung der zeitlichen Variablen ist nur ein zusätzlicher Platz erforderlich.
Es funktioniert gut bei Artikeln, die bereits sortiert wurden.

Nachteile der Auswahlsortierung

Im Folgenden sind die Nachteile der Auswahlsortierung aufgeführt.

Bei der Arbeit an großen Listen ist die Leistung schlecht.
Die Anzahl der während der Sortierung durchgeführten Iterationen ist n-Quadrat, wobei n die Gesamtzahl der Elemente in der Liste ist.
Andere Algorithmen, wie beispielsweise Quicksort, weisen im Vergleich zum Selectionsort eine bessere Leistung auf.

Zusammenfassung

Selectionsort ist ein direkter Vergleichsalgorithmus, der verwendet wird, um eine zufällige Liste in eine geordnete Liste zu sortieren. Er hat eine Zeitkomplexität von O(n²)
Die Liste ist in zwei Abschnitte unterteilt, sortiert und unsortiert. Der Mindestwert wird aus dem unsortierten Abschnitt ausgewählt und in den sortierten Abschnitt eingefügt.
Dieser Vorgang wird wiederholt, bis alle Artikel sortiert sind.
Implementierung des Pseudocodes in Python 3 beinhaltet die Verwendung von zwei for-Schleifen und if-Anweisungen, um zu prüfen, ob ein Swapping notwendig ist
Die Zeitkomplexität misst die Anzahl der Schritte, die zum Sortieren der Liste erforderlich sind.
Die höchste Zeitkomplexität tritt auf, wenn die Liste in absteigender Reihenfolge ist. Sie hat eine Zeitkomplexität von [Big-O] O(n²)
Die beste Zeitkomplexität tritt auf, wenn die Liste bereits in aufsteigender Reihenfolge ist. Sie hat eine Zeitkomplexität von [Big-Omega] ?(n²)
Die durchschnittliche Zeitkomplexität tritt auf, wenn die Liste in zufälliger Reihenfolge ist. Sie hat eine Zeitkomplexität von [Big-theta] ?(n²)
Die Auswahlsortierung eignet sich am besten, wenn Sie eine kleine Liste von Elementen sortieren müssen, die Kosten für den Austausch von Werten keine Rolle spielen und die Überprüfung aller Werte obligatorisch ist.
Die Auswahlsortierung funktioniert bei großen Listen nicht gut
Andere Sortieralgorithmen wie Quicksort weisen im Vergleich zur Auswahlsortierung eine bessere Leistung auf.

Du magst vielleicht: