Auswahlsortierung: Algorithmus erklärt mit Python Code Example

Inhaltsverzeichnis:

Anonim

Was ist Auswahlsortierung?

SELECTION SORT ist ein Vergleichssortieralgorithmus, mit dem eine zufällige Liste von Elementen in aufsteigender Reihenfolge sortiert wird. Der Vergleich erfordert nicht viel zusätzlichen Platz. Es wird nur ein zusätzlicher Speicherplatz für die zeitliche Variable benötigt.

Dies wird als In-Place- Sortierung bezeichnet. Die Auswahlsortierung hat eine Zeitkomplexität von O (n 2 ), wobei n die Gesamtzahl der Elemente in der Liste ist. Die zeitliche Komplexität misst die Anzahl der Iterationen, die zum Sortieren der Liste erforderlich sind. Die Liste ist in zwei Partitionen 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.

In diesem Algorithmus-Tutorial lernen Sie:

  • Was ist Auswahlsortierung?
  • Wie funktioniert die Auswahlsortierung?
  • Problem Definition
  • Lösung (Algorithmus)
  • Visuelle Darstellung
  • Auswahl Sortierprogramm mit Python 3
  • Code Erklärung
  • Zeitliche Komplexität der Auswahl Sortieren
  • Wann wird die Auswahlsortierung verwendet?
  • Vorteile der Auswahlsortierung
  • Nachteile der Auswahlsortierung

Wie funktioniert die Auswahlsortierung?

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

Beispiel:

  • Wenn beispielsweise der Index des Mindestwerts 3 ist, wird der Wert des Elements mit Index 3 auf Index 0 gesetzt, während der Wert auf Index 0 auf Index 3 gesetzt wird. Wenn das erste Element in der unsortierten Partition ist den Minimalwert, dann gibt es seine Positionen zurück.
  • Das als Mindestwert festgelegte Element wird dann auf die Partition auf der linken Seite verschoben, bei der es sich um die sortierte Liste handelt.
  • Die partitionierte Seite hat jetzt ein Element, während die nicht partitionierte Seite (n - 1) Elemente hat, wobei n die Gesamtzahl der Elemente in der Liste ist. Dieser Vorgang wird immer wieder wiederholt, bis alle Elemente verglichen und nach ihren Werten sortiert wurden.

Problem Definition

Eine Liste von 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 anfangs leer, während der unsortierte Abschnitt die gesamte Liste enthält

Schritt 3) Wählen Sie den Mindestwert aus dem nicht partitionierten Abschnitt und platzieren Sie ihn in dem sortierten Abschnitt.

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

Visuelle Darstellung

Bei einer Liste von fünf Elementen veranschaulichen die folgenden Bilder, wie der Auswahlsortieralgorithmus die Werte beim Sortieren durchläuft.

Das folgende Bild zeigt die unsortierte Liste

Schritt 1)

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

3 ist der Mindestwert, daher werden die Positionen 21 und 3 vertauscht. Die Werte mit grünem Hintergrund repräsentieren die sortierte Partition der Liste.

Schritt 2)

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

Der Wert 6 ist der Mindestwert, behält also seine Position bei.

Schritt 3)

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

Der Wert 9 ist der Mindestwert, sodass die Position in der sortierten Partition beibehalten wird.

Schritt 4)

Der Wert 33 wird mit den übrigen Werten verglichen.

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

Schritt 5)

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

Die endgültige Liste entspricht der im obigen Bild gezeigten.

Auswahl Sortierprogramm 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 = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [21,6,9,33,3]print(selectionSort(el))

Führen Sie den obigen Code aus, um die folgenden Ergebnisse zu erzielen

[3, 6, 9, 21, 33]

Code Erklärung

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

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 zu bestimmen, die beim Vergleichen von Werten durchgeführt werden müssen.
  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. Dies bedeutet, dass die äußeren Iterationen viermal ausgefü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 bei Index 0. Er beginnt bei (i + 1). Dies schließt die bereits sortierten Werte aus, sodass wir uns auf Elemente konzentrieren, die noch nicht sortiert wurden.
  5. Findet den Mindestwert in der unsortierten Liste und platziert ihn an der richtigen Position
  6. Aktualisiert den Wert von minValueIndex, wenn die Auslagerungsbedingung erfüllt ist
  7. Vergleicht die Werte der Indexnummern minValueIndex und i, um festzustellen, 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 Wert, der im Zeitwert gespeichert wurde, wird an der Position gespeichert, die zuvor vom Mindestwert gehalten wurde
  11. Gibt die sortierte Liste als Funktionsergebnis zurück
  12. Erstellt eine Liste el mit Zufallszahlen
  13. Drucken Sie die sortierte Liste, nachdem Sie die Auswahlsortierfunktion aufgerufen haben, die el als Parameter übergibt.

Zeitliche Komplexität der Auswahl Sortieren

Die Sortierkomplexität wird verwendet, um die Anzahl der Ausführungszeiten auszudrücken, die zum Sortieren der Liste erforderlich sind. Die Implementierung hat 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 der äußeren Schleife mit den übrigen 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 2 ) ausgedrückt werden kann .

Die Auswahlsortierung weist nämlich drei Komplexitätskategorien auf;

  • Schlimmster Fall - hier ist die Liste in absteigender Reihenfolge. Der Algorithmus führt die maximale Anzahl von Ausführungen aus, die als [Big-O] O (n 2 ) ausgedrückt wird.
  • Bester Fall - Dies tritt auf, wenn die bereitgestellte Liste bereits sortiert ist. Der Algorithmus führt die minimale Anzahl von Ausführungen durch, die als [Big-Omega] Ω (n 2 ) ausgedrückt wird.
  • Durchschnittlicher Fall - Dies tritt auf, wenn die Liste in zufälliger Reihenfolge vorliegt. Die durchschnittliche Komplexität wird ausgedrückt als [Big-Theta] ⊝ (n 2 )

Die Auswahlsortierung hat eine Raumkomplexität von O (1), da eine zeitliche Variable zum Austauschen von Werten erforderlich ist.

Wann wird die Auswahlsortierung verwendet?

Die Auswahlsortierung wird am besten verwendet, wenn Sie:

  • 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

Das Folgende sind die Vorteile der Auswahlsortierung

  • Es funktioniert sehr gut auf kleinen Listen
  • Es ist ein In-Place-Algorithmus. Es benötigt nicht viel Platz zum Sortieren. Zum Halten der zeitlichen Variablen ist nur ein zusätzlicher Platz erforderlich.
  • Es funktioniert gut bei Elementen, die bereits sortiert wurden.

Nachteile der Auswahlsortierung

Das Folgende 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 z. B. Quicksort, weisen im Vergleich zur Auswahlsortierung eine bessere Leistung auf.

Zusammenfassung:

  • Die Auswahlsortierung ist ein In-Place-Vergleichsalgorithmus, mit dem eine zufällige Liste in eine geordnete Liste sortiert wird. Es hat eine zeitliche Komplexität von O (n 2 )
  • 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.
  • Diese Sache wird wiederholt, bis alle Elemente sortiert wurden.
  • Um den Pseudocode in Python 3 zu implementieren, müssen zwei for-Schleifen und if-Anweisungen verwendet werden, um zu überprüfen, ob ein Austausch erforderlich ist
  • Die zeitliche Komplexität misst die Anzahl der Schritte, die zum Sortieren der Liste erforderlich sind.
  • Die Zeitkomplexität im schlimmsten Fall tritt auf, wenn die Liste in absteigender Reihenfolge vorliegt. Es hat eine zeitliche Komplexität von [Big-O] O (n 2 )
  • Die beste Zeitkomplexität tritt auf, wenn die Liste bereits in aufsteigender Reihenfolge vorliegt. Es hat eine zeitliche Komplexität von [Big-Omega] Ω (n 2 )
  • Die durchschnittliche Zeitkomplexität tritt auf, wenn die Liste in zufälliger Reihenfolge vorliegt. Es hat eine zeitliche Komplexität von [Big-Theta] ⊝ (n 2 )
  • Die Auswahlsortierung wird am besten verwendet, wenn Sie eine kleine Liste von Elementen zum Sortieren haben, 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.