TechCodeview

In diesem Tutorial implementieren wir den Auswahlsortierungsalgorithmus in Python. Es handelt sich um einen recht einfachen Algorithmus, der weniger Austauschvorgänge verwendet.

Bei diesem Algorithmus wählen wir in jedem Durchgang das kleinste Element aus einem unsortierten Array aus und tauschen es mit dem Anfang des unsortierten Arrays aus. Dieser Vorgang wird fortgesetzt, bis alle Elemente an der richtigen Stelle platziert sind. Es ist einfach und ein Sortieralgorithmus für den direkten Vergleich.

Funktionsweise der Auswahlsortierung

Im Folgenden finden Sie die Schritte zur Erläuterung der Funktionsweise der Auswahlsortierung in Python.

Nehmen wir ein unsortiertes Array, um den Auswahlsortierungsalgorithmus anzuwenden.

[30, 10, 12, 8, 15, 1]

Schritt 1: Ermitteln Sie die Länge des Arrays.

Länge = len(array) → 6

Schritt 2: Zuerst legen wir das erste Element als Mindestelement fest.

Schritt 3: Vergleichen Sie nun das Minimum mit dem zweiten Element. Wenn das zweite Element kleiner als das erste ist, weisen wir es als Minimum zu.

Wieder vergleichen wir das zweite Element mit dem dritten und weisen es als Minimum zu, wenn das dritte Element kleiner als das zweite ist. Dieser Vorgang wird fortgesetzt, bis wir das letzte Element gefunden haben.

Schritt 4: Nach jeder Iteration wird das minimale Element vor dem unsortierten Array ausgetauscht.

Schritt - 5: Der zweite bis dritte Schritt wird wiederholt, bis wir das sortierte Array erhalten.

Auswahlsortierungsalgorithmus

Der Auswahlsortierungsalgorithmus ist wie folgt.

Algorithmus

 selection_sort(array) repeat (0, length - 1) times set the first unsorted element as the minimum for each of the unsorted elements if element <currentminimum set element as new minimum swap with first unsorted position end selection_sort < pre> <h2>Selection Sort Program using Python</h2> <p>The following code snippet shows the selection sort algorithm implementation using Python.</p> <p> <strong>Code -</strong> </p> <pre> def selection_sort(array): length = len(array) for i in range(length-1): minIndex = i for j in range(i+1, length): if array[j] <array[minindex]: minindex="j" array[i], array[minindex]="array[minIndex]," array[i] return array print('the sorted is: ', selection_sort(array)) < pre> <p> <strong>Output:</strong> </p> <pre> The sorted array is: [3, 6, 9, 21, 33] </pre> <p> <strong>Explanation -</strong> </p> <p>Let&apos;s understand the above code -</p> <ul> <li>First, we define the <strong>selection_sort()</strong> function that takes array as an argument.</li> <li>In the function, we get the length of the array which used to determine the number of passes to be made comparing values.</li> <li>As we can see that, we use two loops - outer and inner loop. The outer loop uses to iterate through the values of the list. This loop will iterate to 0 to (length-1). So the first iteration will be perform (5-1) or 4 times. In each iteration, the value of the variable i is assigned to the variable</li> <li>The inner loop uses to compare the each value of right-side element to the other value on the leftmost element. So the second loop starts its iteration from i+1. It will only pick the value that is unsorted.</li> <li>Find the minimum element in the unsorted list and update the minIndex position.</li> <li>Place the value at the beginning of the array.</li> <li>Once the iteration is completed, the sorted array is returned.</li> <li>At last we create an unsorted array and pass to the <strong>selection_sort()</strong> It prints the sorted array.</li> </ul> <h2>Time Complexity of Selection Sort</h2> <p>Time complexity is an essential in term of how much time an algorithm take to sort it. In the selection sort, there are two loops. The outer loop runs for the n times (n is a total number of element).</p> <p>The inner loop is also executed for n times. It compares the rest of the value to outer loop value. So, there is n*n times of execution. Hence the time complexity of merge sort algorithm is O(n<sup>2</sup>).</p> <p>The time complexity can be categorized into three categories.</p> <hr></array[minindex]:></pre></currentminimum>

Erläuterung -

Lassen Sie uns den obigen Code verstehen -

• Zuerst definieren wir die Selection_sort() Funktion, die ein Array als Argument verwendet.
• In der Funktion erhalten wir die Länge des Arrays, das zur Bestimmung der Anzahl der Durchgänge zum Vergleichen von Werten verwendet wird.
• Wie wir sehen können, verwenden wir zwei Schleifen – eine äußere und eine innere Schleife. Die äußere Schleife dient zum Durchlaufen der Werte der Liste. Diese Schleife wird von 0 bis (Länge 1) durchlaufen. Die erste Iteration wird also (5-1) oder 4 Mal durchgeführt. In jeder Iteration wird der Variablen der Wert der Variablen i zugewiesen
• Die innere Schleife vergleicht jeden Wert des Elements auf der rechten Seite mit dem anderen Wert auf dem Element ganz links. Die zweite Schleife beginnt ihre Iteration also bei i+1. Es wird nur der unsortierte Wert ausgewählt.
• Suchen Sie das kleinste Element in der unsortierten Liste und aktualisieren Sie die minIndex-Position.
• Platzieren Sie den Wert am Anfang des Arrays.
• Sobald die Iteration abgeschlossen ist, wird das sortierte Array zurückgegeben.
• Zuletzt erstellen wir ein unsortiertes Array und übergeben es an Selection_sort() Es gibt das sortierte Array aus.

Zeitliche Komplexität der Auswahlsortierung

Die zeitliche Komplexität ist ein wesentlicher Faktor dafür, wie viel Zeit ein Algorithmus zum Sortieren benötigt. Bei der Auswahlsortierung gibt es zwei Schleifen. Die äußere Schleife wird n-mal ausgeführt (n ist die Gesamtzahl der Elemente).

Die innere Schleife wird ebenfalls n-mal ausgeführt. Der Rest des Werts wird mit dem Wert der äußeren Schleife verglichen. Es gibt also n*n Mal eine Ausführung. Daher beträgt die zeitliche Komplexität des Zusammenführungssortierungsalgorithmus O(n).²).

Die Zeitkomplexität kann in drei Kategorien eingeteilt werden.