Auswahlsortierung: Algorithmus erklärt anhand eines Python-Codebeispiels

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 Zeitspanneplexität von O(n2), wobei n die Gesamtzahl der Elemente in der Liste ist. Die Zeit complexity 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 von Elementen in zufälliger Reihenfolge muss in aufsteigender Reihenfolge sortiert werden. Betrachten Sie Folgendeswing Liste als Beispiel.

[21,6,9,33,3]

Die obige Liste sollte sortiert werden, um Folgendes zu erhaltenwing Ergebnisse

[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

Angesichts einer Liste von fünf Elementen folgt das Folgendewing Bilder veranschaulichen, wie der Auswahlsortierungsalgorithmus die Werte beim Sortieren durchläuft.

Die folgendenwing Das Bild zeigt die unsortierte Liste

Visuelle Darstellung

Schritt 1)

Visuelle Darstellung

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

Visuelle Darstellung

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)

Visuelle Darstellung

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

Visuelle Darstellung

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

Schritt 3)

Visuelle Darstellung

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.

Visuelle Darstellung

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

Schritt 4)

Visuelle Darstellung

Der Wert 33 wird mit den restlichen Werten verglichen.

Visuelle Darstellung

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

Schritt 5)

Visuelle Darstellung

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

Visuelle Darstellung

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

Auswahlsortierungsprogramm mit Python 3

Die folgendenwing Code zeigt die Auswahlsortierungsimplementierung 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))

Führen Sie den obigen Code aus, um Folgendes zu erhaltenwing Ergebnisse

[3, 6, 9, 21, 33]

Code Erklärung

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

Auswahlsortierungsprogramm mit Python 3

Hier ist die Code-Erklärung:

  1. Definiert eine Funktion namens „selectionSort“.
  2. Ruft die Gesamtzahl der Elemente in der Liste ab. Wir benötigen dies, um die Anzahl der Durchgänge beim Wertevergleich zu bestimmen.
  3. Ä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
  4. 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.
  5. Sucht den Mindestwert in der unsortierten Liste und platziert ihn an der richtigen Position
  6. Aktualisiert den Wert von minValueIndex, wenn die Austauschbedingung wahr ist
  7. Compares die Werte der Indexzahlen minValueIndex und i, um zu sehen, ob sie nicht gleich sind
  8. Der Wert ganz links wird in einer zeitlichen Variablen gespeichert
  9. Der niedrigere Wert von der rechten Seite nimmt die erste Position ein
  10. Der im Zeitwert gespeicherte Wert wird an der Position gespeichert, die zuvor der Minimalwert innehatte
  11. Gibt die sortierte Liste als Funktionsergebnis zurück
  12. Erstellt eine Liste el mit Zufallszahlen
  13. Drucken Sie die sortierte Liste nach dem Aufruf der Auswahlsortierfunktion und übergeben Sie dabei el als Parameter.

Time Complexität der Auswahlsortierung

Die Sorte complexity wird verwendet, um die Anzahl der Ausführungszeiten auszudrücken, die zum Sortieren der Liste erforderlich sind. Die Implementierung verfügt über 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 compares Der Wert aus der äußeren Schleife wird mit den restlichen Werten 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 kann2).

Die Auswahlsortierung umfasst drei Kommunikationskategorienplexität 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 wird2)
  • I'm besten fall – Dies geschieht, wenn die bereitgestellte Liste bereits sortiert ist. Der Algorithmus führt die minimale Anzahl von Ausführungen durch, die als [Big-Omega] ?(N2)
  • Durchschnittlicher Fall – Dies geschieht, wenn die Liste in zufälliger Reihenfolge vorliegt. Der durchschnittliche complexität wird ausgedrückt als [Big-Theta] ?(n2)

Die Auswahlsortierung hat ein Leerzeichen complexität von O(1), da es eine zeitliche Variable benötigt, die zum Austauschen von Werten verwendet wird.

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 folgendenwing sind die Vorteile der Auswahlsortierung

  • 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

Die folgendenwing sind die Nachteile der Auswahlsortierung.

  • 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 Quicksort weisen im Vergleich zur Auswahlsortierung eine bessere Leistung auf.

Zusammenfassung

  • Die Auswahlsortierung ist ein direkter Vergleichsalgorithmus, der zum Sortieren einer Zufallsliste in eine geordnete Liste verwendet wird. Es hat eine Zeitkomplexität von O(n2)
  • 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.
  • Die Implementierung des Pseudocodes in Python 3 erfordert die Verwendung von zwei for-Schleifen und if-Anweisungen, um zu prüfen, ob ein Austausch erforderlich ist
  • Die Zeit complexity misst die Anzahl der Schritte, die zum Sortieren der Liste erforderlich sind.
  • Der Worst-Case-Zeit-ComplexDies geschieht, wenn die Liste in absteigender Reihenfolge vorliegt. Es hat eine Zeitkomplexität von [Big-O] O(n2)
  • Im besten Fall Zeit complexDies geschieht, wenn die Liste bereits in aufsteigender Reihenfolge vorliegt. Es hat eine Zeitkomplexität von [Big-Omega] ?(N2)
  • Die durchschnittliche Fallzeit complexDies geschieht, wenn die Liste in zufälliger Reihenfolge vorliegt. Es hat eine Zeitkomplexität von [Big-Theta] ?(n2)
  • 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.