PASIRINKIMAS RŪŠIUOTI

Šiame straipsnyje aptarsime atrankos rūšiavimo algoritmą. Atrankos rūšiavimo darbo procedūra taip pat paprasta. Šis straipsnis bus labai naudingas ir įdomus studentams, nes egzaminų metu jie gali susidurti su atrankos rūšiavimo klausimu. Taigi, svarbu aptarti temą.

Atrankos rūšiavimo metu mažiausia reikšmė tarp nerūšiuotų masyvo elementų parenkama kiekvieną kartą ir įterpiama į atitinkamą masyvo vietą. Tai taip pat yra paprasčiausias algoritmas. Tai lyginimo rūšiavimo algoritmas vietoje. Šiame algoritme masyvas yra padalintas į dvi dalis, pirmiausia yra surūšiuota dalis, o kita - nerūšiuota dalis. Iš pradžių surūšiuota masyvo dalis yra tuščia, o nerūšiuota dalis yra duotas masyvas. Išrūšiuota dalis dedama kairėje, o nerūšiuota dalis – dešinėje.

Atrankos rūšiavimo metu pirmasis mažiausias elementas parenkamas iš nerūšiuoto masyvo ir dedamas į pirmąją vietą. Po to pasirenkamas antrasis mažiausias elementas ir dedamas į antrąją padėtį. Procesas tęsiamas tol, kol masyvas bus visiškai surūšiuotas.

Vidutinis ir blogiausias atrankos rūšiavimo sudėtingumas yra O (n²) , kur n yra elementų skaičius. Dėl šios priežasties jis netinka dideliems duomenų rinkiniams.

Pasirinkimo rūšiavimas paprastai naudojamas, kai -

Turi būti rūšiuojamas nedidelis masyvas
Keitimo kaina neturi reikšmės
Privaloma patikrinti visus elementus

Dabar pažiūrėkime atrankos rūšiavimo algoritmą.

Algoritmas

 SELECTION SORT(arr, n) Step 1: Repeat Steps 2 and 3 for i = 0 to n-1 Step 2: CALL SMALLEST(arr, i, n, pos) Step 3: SWAP arr[i] with arr[pos] [END OF LOOP] Step 4: EXIT SMALLEST (arr, i, n, pos) Step 1: [INITIALIZE] SET SMALL = arr[i] Step 2: [INITIALIZE] SET pos = i Step 3: Repeat for j = i+1 to n if (SMALL &gt; arr[j]) SET SMALL = arr[j] SET pos = j [END OF if] [END OF LOOP] Step 4: RETURN pos

Pasirinkimo rūšiavimo algoritmo darbas

Dabar pažiūrėkime, kaip veikia atrankos rūšiavimo algoritmas.

Norėdami suprasti atrankos rūšiavimo algoritmo veikimą, paimkime nerūšiuotą masyvą. Pasirinkimo rūšiavimą bus lengviau suprasti naudojant pavyzdį.

Tegul masyvo elementai yra -

Dabar, norint gauti pirmąją vietą surūšiuotame masyve, visas masyvas turi būti nuskaitytas nuosekliai.

Dabar, 12 yra saugomas pirmoje pozicijoje, atlikus paiešką visame masyve, randama, kad 8 yra mažiausia vertė.

priešinga paieška

Taigi, pakeiskite 12 su 8. Po pirmosios iteracijos 8 atsiras pirmoje surūšiuoto masyvo pozicijoje.

Antroje pozicijoje, kurioje šiuo metu saugomi 29, vėl nuosekliai nuskaitome likusius nerūšiuoto masyvo elementus. Nuskaitę matome, kad 12 yra antras žemiausias elementas masyve, kuris turėtų būti rodomas antroje pozicijoje.

Dabar pakeiskite 29 į 12. Po antrosios iteracijos 12 atsiras antroje surūšiuoto masyvo vietoje. Taigi, po dviejų iteracijų, dvi mažiausios reikšmės pateikiamos pradžioje surūšiuotai.

Tas pats procesas taikomas ir kitiems masyvo elementams. Dabar rodome vaizdinį viso rūšiavimo proceso vaizdą.

Dabar masyvas yra visiškai surūšiuotas.

Pasirinkimo rūšiavimo sudėtingumas

Dabar pažiūrėkime atrankos rūšiavimo sudėtingumą geriausiu, vidutiniu ir blogiausiu atveju. Taip pat pamatysime atrankos rūšiavimo erdvės sudėtingumą.

1. Laiko sudėtingumas

Byla	Laiko sudėtingumas
Geriausias atvejis	O (n²)
Vidutinis atvejis	O (n²)
Blogiausiu atveju	O (n²)

O (n²)

2. Erdvės sudėtingumas

Erdvės sudėtingumas	O(1)
Stabilus	TAIP

Atrankos rūšiavimo erdvės sudėtingumas yra O(1). Taip yra todėl, kad rūšiuojant pasirinkimą, norint pakeisti, reikalingas papildomas kintamasis.

Atrankos rūšiavimo įgyvendinimas

Dabar pažiūrėkime, kaip pasirinkimo programos rūšiuojamos skirtingomis programavimo kalbomis.

Programa: Parašykite programą pasirinkimo rūšiavimui įgyvendinti C kalba.

 #include void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 17 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting elements are - 
'); printarr(a, n); selection(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-7.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C++ language.</p> <pre> #include using namespace std; void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 15 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i cout<< a[i] <<' '; main() a[]="{" 80, 10, 29, 11, 8, 30, }; n="sizeof(a)" sizeof(a[0]); 'before sorting elements are - '<<endl; printarr(a, n); selection(a, '
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-8.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C# language.</p> <pre> using System; class Selection { static void selection(int[] arr) { int i, j, small; int n = arr.Length; for (i = 0; i <n-1; i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } static void printarr(int[] a) * function to print i; n="a.Length;" (i="0;" i console.write(a[i] + ' '); main() int[] a="{" 85, 50, 29, 18, 7, 30, 3}; console.write('before sorting elements are - printarr(a); selection(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-9.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in python.</p> <pre> def selection(a): # Function to implement selection sort for i in range(len(a)): # Traverse through all array elements small = i # minimum element in unsorted array for j in range(i+1, len(a)): if a[small] &gt; a[j]: small = j # Swap the found minimum element with # the first element a[i], a[small] = a[small], a[i] def printArr(a): # function to print the array for i in range(len(a)): print (a[i], end = &apos; &apos;) a = [69, 14, 1, 50, 59] print(&apos;Before sorting array elements are - &apos;) printArr(a) selection(a) print(&apos;
After sorting array elements are - &apos;) selection(a) printArr(a) </pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-10.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in Java.</p> <pre> public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println('
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println('
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo 'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;></pre></n-1;></pre></n-1;></pre></n-1;>

Išvestis:

Programa: Parašykite programą, kuri įdiegtų atrankos rūšiavimą Java.

 public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + \' \'); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println(\'
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println(\'
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo \' \'; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo \'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;>

Išvestis:

Įvykdžius aukščiau pateiktą kodą, išvestis bus -

Taigi, viskas apie straipsnį. Tikimės, kad straipsnis bus jums naudingas ir informatyvus.

Šis straipsnis neapsiribojo tik algoritmu. Taip pat aptarėme atrankos rūšiavimo sudėtingumą, veikimą ir įgyvendinimą skirtingomis programavimo kalbomis.

TechCodeview

Pasirinkimo rūšiavimo algoritmas