TechCodeview

V tomto tutoriálu budeme implementovat algoritmus řazení výběru v Pythonu. Je to docela přímočarý algoritmus využívající méně swapování.

V tomto algoritmu vybereme nejmenší prvek z netříděného pole v každém průchodu a prohodíme se začátkem netříděného pole. Tento proces bude pokračovat, dokud nebudou všechny prvky umístěny na správném místě. Je to jednoduchý a na místě srovnávací třídicí algoritmus.

Práce se selekcí

Následují kroky vysvětlující fungování třídění Selection v Pythonu.

Vezměme netříděné pole, abychom použili algoritmus řazení výběru.

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

Krok 1: Získejte délku pole.

délka = len(pole) → 6

Krok 2: Nejprve nastavíme první prvek jako minimální prvek.

Krok – 3: Nyní porovnejte minimum s druhým prvkem. Pokud je druhý prvek menší než první, přiřadíme jej jako minimum.

Opět porovnáme druhý prvek se třetím a pokud je třetí prvek menší než druhý, přiřadíme jej jako minimum. Tento proces pokračuje, dokud nenajdeme poslední prvek.

Krok – 4: Po každé iteraci se před nesetříděným polem vymění minimální prvek.

Krok – 5: Druhý až třetí krok se opakuje, dokud nezískáme seřazené pole.

Algoritmus řazení výběru

Algoritmus řazení výběru je následující.

Algoritmus

 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>

Vysvětlení -

získat připojení

Pojďme pochopit výše uvedený kód -

• Nejprve definujeme select_sort() funkce, která bere pole jako argument.
• Ve funkci získáme délku pole, které bylo použito k určení počtu průchodů, které mají být provedeny porovnáním hodnot.
• Jak vidíme, používáme dvě smyčky - vnější a vnitřní. Vnější smyčka používá k iteraci přes hodnoty seznamu. Tato smyčka bude iterovat do 0 až (délka-1). Takže první iterace bude provedena (5-1) nebo 4krát. V každé iteraci je k proměnné přiřazena hodnota proměnné i
• Vnitřní smyčka slouží k porovnání každé hodnoty prvku na pravé straně s jinou hodnotou na prvku zcela vlevo. Takže druhá smyčka začíná iteraci od i+1. Vybere pouze hodnotu, která není seřazena.
• Najděte minimální prvek v netříděném seznamu a aktualizujte pozici minIndex.
• Umístěte hodnotu na začátek pole.
• Jakmile je iterace dokončena, vrátí se setříděné pole.
• Nakonec vytvoříme netříděné pole a předáme jej select_sort() Vytiskne seřazené pole.

Časová složitost řazení výběru

Časová složitost je podstatná z hlediska toho, kolik času algoritmu zabere, aby ji seřadil. V řazení výběru jsou dvě smyčky. Vnější smyčka běží nkrát (n je celkový počet prvků).

Vnitřní smyčka se také provádí nkrát. Porovnává zbytek hodnoty s hodnotou vnější smyčky. Existuje tedy n*n časů provedení. Časová složitost algoritmu řazení sloučení je tedy O(n²).

Časovou náročnost lze rozdělit do tří kategorií.