TechCodeview

In deze tutorial implementeren we het selectie-sorteeralgoritme in Python. Het is een vrij eenvoudig algoritme dat minder swapping gebruikt.

In dit algoritme selecteren we bij elke doorgang het kleinste element uit een ongesorteerde array en wisselen we met het begin van de ongesorteerde array. Dit proces gaat door totdat alle elementen op de juiste plaats zijn geplaatst. Het is eenvoudig en een intern sorteeralgoritme voor vergelijkingen.

Werking van selectiesortering

Hieronder volgen de stappen om de werking van de selectiesortering in Python uit te leggen.

Laten we een ongesorteerde array nemen om het selectie-sorteeralgoritme toe te passen.

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

Stap 1: Haal de lengte van de array op.

lengte = len(matrix) → 6

jsp

Stap 2: Eerst stellen we het eerste element in als minimumelement.

Stap 3: Vergelijk nu het minimum met het tweede element. Als het tweede element kleiner is dan het eerste, wijzen we dit als minimum toe.

Opnieuw vergelijken we het tweede element met het derde en als het derde element kleiner is dan het tweede, wijzen we dit als minimum toe. Dit proces gaat door totdat we het laatste element vinden.

Stap 4: Na elke iteratie wordt het minimumelement vóór de ongesorteerde array verwisseld.

Stap - 5: De tweede tot en met derde stap worden herhaald totdat we de gesorteerde array krijgen.

Selectie Sorteeralgoritme

Het selectie-sorteeralgoritme als volgt.

Algoritme

 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>

Uitleg -

Laten we de bovenstaande code begrijpen -

• Eerst definiëren we de selectie_sort() functie die array als argument gebruikt.
• In de functie krijgen we de lengte van de array die werd gebruikt om het aantal doorgangen te bepalen dat moest worden gemaakt om waarden te vergelijken.
• Zoals we kunnen zien, gebruiken we twee lussen: de buitenste en de binnenste lus. De buitenste lus wordt gebruikt om de waarden van de lijst te doorlopen. Deze lus itereert naar 0 tot (lengte-1). De eerste iteratie zal dus worden uitgevoerd (5-1) of 4 keer. In elke iteratie wordt de waarde van de variabele i aan de variabele toegewezen
• De binnenste lus gebruikt om elke waarde van het rechterelement te vergelijken met de andere waarde van het meest linkse element. Dus de tweede lus begint zijn iteratie vanaf i+1. Er wordt alleen de waarde gekozen die ongesorteerd is.
• Zoek het minimumelement in de ongesorteerde lijst en werk de minIndex-positie bij.
• Plaats de waarde aan het begin van de array.
• Zodra de iteratie is voltooid, wordt de gesorteerde array geretourneerd.
• Eindelijk maken we een ongesorteerde array en gaan we naar de selectie_sort() Het drukt de gesorteerde array af.

Tijdcomplexiteit van selectiesortering

Tijdcomplexiteit is essentieel voor de hoeveelheid tijd die een algoritme nodig heeft om het te sorteren. Bij de selectiesortering zijn er twee lussen. De buitenste lus loopt n keer door (n is een totaal aantal elementen).

De binnenste lus wordt ook n keer uitgevoerd. Het vergelijkt de rest van de waarde met de waarde van de buitenste lus. Er zijn dus n*n uitvoeringstijden. Daarom is de tijdscomplexiteit van het samenvoeg-sorteeralgoritme O(n²).

De tijdscomplexiteit kan in drie categorieën worden onderverdeeld.