I den här handledningen kommer vi att implementera urvalssorteringsalgoritmen i Python. Det är ganska okomplicerad algoritm med mindre byte.
I den här algoritmen väljer vi det minsta elementet från en osorterad array i varje pass och byter med början av den osorterade arrayen. Denna process kommer att fortsätta tills alla element är placerade på rätt plats. Det är enkelt och en algoritm för jämförelsesortering på plats.
Arbete av urvalssort
Följande är stegen för att förklara hur urvalssorteringen fungerar i Python.
Låt oss ta en osorterad array för att tillämpa urvalssorteringsalgoritmen.
[30, 10, 12, 8, 15, 1]
Steg 1: Få längden på arrayen.
längd = len(array) → 6
Steg 2: Först ställer vi in det första elementet som minimumelement.
konvertera char till sträng java
Steg 3: Jämför nu minimum med det andra elementet. Om det andra elementet är mindre än det första, tilldelar vi det som ett minimum.
Återigen jämför vi det andra elementet med det tredje och om det tredje elementet är mindre än det andra, tilldela det som minimum. Denna process fortsätter tills vi hittar det sista elementet.
Steg - 4: Efter varje iteration byts minimielementet framför den osorterade arrayen.
Steg - 5: Det andra till det tredje steget upprepas tills vi får den sorterade arrayen.
Valsorteringsalgoritm
Valsorteringsalgoritmen enligt följande.
Algoritm
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'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> Förklaring -
Låt oss förstå koden ovan -
- Först definierar vi selection_sort() funktion som tar array som ett argument.
- I funktionen får vi längden på arrayen som användes för att bestämma antalet pass som ska göras vid jämförelse av värden.
- Som vi kan se det använder vi två slingor - yttre och inre slinga. Den yttre slingan använder för att iterera genom värdena i listan. Denna loop kommer att iterera till 0 till (längd-1). Så den första iterationen kommer att utföras (5-1) eller 4 gånger. I varje iteration tilldelas variabeln i värdet till variabeln
- Den inre slingan används för att jämföra varje värde för elementet på höger sida med det andra värdet på elementet längst till vänster. Så den andra slingan börjar sin iteration från i+1. Det kommer bara att välja värdet som är osorterat.
- Hitta minimielementet i den osorterade listan och uppdatera minIndex-positionen.
- Placera värdet i början av arrayen.
- När iterationen är klar returneras den sorterade arrayen.
- Till sist skapar vi en osorterad array och går vidare till selection_sort() Den skriver ut den sorterade arrayen.
Tidskomplexitet för urvalssortering
Tidskomplexitet är avgörande för hur mycket tid en algoritm tar för att sortera den. I urvalssorteringen finns det två slingor. Den yttre slingan löper n gånger (n är ett totalt antal element).
Den inre slingan exekveras också n gånger. Den jämför resten av värdet med det yttre slingvärdet. Så det finns n*n tider för avrättning. Därför är tidskomplexiteten för sammanslagningssorteringsalgoritmen O(n2).
Tidskomplexiteten kan kategoriseras i tre kategorier.