TechCodeview

V tomto návode implementujeme algoritmus triedenia výberu v Pythone. Je to celkom jednoduchý algoritmus využívajúci menej swapovania.

V tomto algoritme vyberieme najmenší prvok z nezoradeného poľa v každom prechode a vymeníme ho so začiatkom nezoradeného poľa. Tento proces bude pokračovať, kým nie sú všetky prvky umiestnené na správnom mieste. Je to jednoduchý a na mieste porovnávací triediaci algoritmus.

Fungovanie triedenia výberu

Nasledujú kroky na vysvetlenie fungovania triedenia výberu v Pythone.

Vezmime si nezoradené pole, aby sme použili algoritmus triedenia výberu.

string.valueof java

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

Krok 1: Získajte dĺžku poľa.

dĺžka = dĺžka (pole) → 6

Krok 2: Najprv nastavíme prvý prvok ako minimálny prvok.

parafrázovať ako rudyard kipling

Krok - 3: Teraz porovnajte minimum s druhým prvkom. Ak je druhý prvok menší ako prvý, priradíme ho ako minimum.

Opäť porovnáme druhý prvok s tretím a ak je tretí prvok menší ako druhý, priradíme ho ako minimum. Tento proces pokračuje, kým nenájdeme posledný prvok.

Krok - 4: Po každej iterácii sa minimum prvku vymení pred nezoradené pole.

Krok - 5: Druhý až tretí krok sa opakuje, kým nezískame zoradené pole.

Algoritmus triedenia výberu

Algoritmus triedenia výberu je nasledujúci.

Algoritmus

návratové pole java

 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>

vysvetlenie -

Poďme pochopiť vyššie uvedený kód -

• Najprv definujeme select_sort() funkcia, ktorá berie pole ako argument.
• Vo funkcii dostaneme dĺžku poľa, ktoré sa použilo na určenie počtu prechodov, ktoré sa majú vykonať porovnaním hodnôt.
• Ako vidíme, používame dve slučky - vonkajšiu a vnútornú. Vonkajšia slučka používa na iteráciu cez hodnoty zoznamu. Tento cyklus sa bude opakovať od 0 do (dĺžka-1). Takže prvá iterácia sa vykoná (5-1) alebo 4 krát. V každej iterácii sa k premennej priradí hodnota premennej i
• Vnútorná slučka sa používa na porovnanie každej hodnoty prvku na pravej strane s inou hodnotou prvku úplne vľavo. Takže druhá slučka začína svoju iteráciu od i+1. Vyberie len hodnotu, ktorá nie je zoradená.
• Nájdite minimálny prvok v netriedenom zozname a aktualizujte pozíciu minIndex.
• Umiestnite hodnotu na začiatok poľa.
• Po dokončení iterácie sa vráti zoradené pole.
• Nakoniec vytvoríme nezoradené pole a prejdeme do select_sort() Vytlačí zoradené pole.

Časová náročnosť zoradenia výberu

Časová zložitosť je podstatná z hľadiska toho, koľko času algoritmu zaberie jeho triedenie. V triedení výberu sú dve slučky. Vonkajšia slučka beží n krát (n je celkový počet prvkov).

Vnútorná slučka sa tiež vykonáva n-krát. Porovnáva zvyšok hodnoty s hodnotou vonkajšej slučky. Existuje teda n*n časov vykonania. Časová zložitosť algoritmu zoradenia zlúčenia je teda O(n²).

Časovú náročnosť možno rozdeliť do troch kategórií.