TechCodeview

Šioje pamokoje įdiegsime pasirinkimo rūšiavimo algoritmą Python. Tai gana paprastas algoritmas, naudojant mažiau mainų.

Šiame algoritme mes pasirenkame mažiausią elementą iš nerūšiuoto masyvo kiekviename žingsnyje ir keičiame su nerūšiuoto masyvo pradžia. Šis procesas tęsis tol, kol visi elementai bus išdėstyti tinkamoje vietoje. Tai paprastas palyginimo rūšiavimo algoritmas.

Atrankos rūšiavimo darbas

Toliau pateikiami žingsniai, paaiškinantys atrankos rūšiavimo veikimą Python.

dijkstra

Paimkime nerūšiuotą masyvą, kad pritaikytume pasirinkimo rūšiavimo algoritmą.

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

1 žingsnis: Gaukite masyvo ilgį.

ilgis = len(masyvas) → 6

2 žingsnis: Pirma, pirmąjį elementą nustatome kaip minimalų elementą.

3 veiksmas: Dabar palyginkite minimumą su antruoju elementu. Jei antrasis elementas mažesnis už pirmąjį, jį priskiriame kaip minimumą.

Vėlgi, palyginame antrąjį elementą su trečiuoju ir, jei trečiasis yra mažesnis nei antrasis, priskirkite jį kaip minimumą. Šis procesas tęsiasi tol, kol randame paskutinį elementą.

4 veiksmas: Po kiekvienos iteracijos minimalus elementas pakeičiamas prieš nerūšiuotą masyvą.

5 veiksmas: Antras – trečias žingsniai kartojami tol, kol gauname surūšiuotą masyvą.

Pasirinkimo rūšiavimo algoritmas

Pasirinkimo rūšiavimo algoritmas yra toks.

Algoritmas

 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>

Paaiškinimas -

Supraskime aukščiau pateiktą kodą -

• Pirma, mes apibrėžiame Selection_sort() funkcija, kuri naudoja masyvą kaip argumentą.
• Funkcijoje gauname masyvo ilgį, kuris buvo naudojamas norint nustatyti, kiek kartų reikia atlikti lyginant reikšmes.
• Kaip matome, mes naudojame dvi kilpas - išorinę ir vidinę. Išorinė kilpa naudojama sąrašo reikšmėms kartoti. Ši kilpa kartosis nuo 0 iki (ilgis-1). Taigi pirmoji iteracija bus atlikta (5-1) arba 4 kartus. Kiekvienoje iteracijoje kintamajam priskiriama kintamojo i reikšmė
• Vidinė kilpa naudojama kiekvienai dešiniojo elemento vertei palyginti su kita kairiojo elemento verte. Taigi antroji kilpa pradeda savo iteraciją nuo i+1. Jis pasirinks tik nerūšiuotą vertę.
• Suraskite mažiausią elementą nesurūšiuotame sąraše ir atnaujinkite minIndex poziciją.
• Įdėkite reikšmę masyvo pradžioje.
• Kai iteracija baigta, surūšiuotas masyvas grąžinamas.
• Galiausiai sukuriame nerūšiuotą masyvą ir pereiname prie Selection_sort() Jis spausdina surūšiuotą masyvą.

Atrankos rūšiavimo laiko sudėtingumas

Laiko sudėtingumas yra esminis veiksnys nustatant, kiek laiko algoritmas užtrunka jį surūšiuoti. Pasirinkimo rūšiavime yra dvi kilpos. Išorinė kilpa veikia n kartų (n yra bendras elementų skaičius).

Vidinė kilpa taip pat vykdoma n kartų. Jis lygina likusią vertę su išorinės kilpos reikšme. Taigi, yra n * n vykdymo kartų. Taigi sujungimo rūšiavimo algoritmo sudėtingumas laike yra O(n²).

Laiko sudėtingumą galima suskirstyti į tris kategorijas.