VÝBER ZORADIŤ - NÁVOD DS

V tomto článku budeme diskutovať o algoritme triedenia výberu. Pracovný postup triedenia výberu je tiež jednoduchý. Tento článok bude pre študentov veľmi užitočný a zaujímavý, pretože pri skúškach sa môžu stretnúť s otázkou triedenia výberu. Preto je dôležité diskutovať o téme.

Pri triedení výberu sa v každom prechode vyberie najmenšia hodnota spomedzi nezoradených prvkov poľa a vloží sa na príslušnú pozíciu do poľa. Je to tiež najjednoduchší algoritmus. Je to miestny porovnávací triediaci algoritmus. V tomto algoritme je pole rozdelené na dve časti, prvá je triedená časť a druhá je netriedená časť. Na začiatku je zoradená časť poľa prázdna a nezoradená časť je dané pole. Vytriedená časť je umiestnená vľavo, zatiaľ čo nevytriedená časť je umiestnená vpravo.

Pri triedení výberu sa prvý najmenší prvok vyberie z nezoradeného poľa a umiestni sa na prvé miesto. Potom sa vyberie druhý najmenší prvok a umiestni sa na druhú pozíciu. Proces pokračuje, kým sa pole úplne neroztriedi.

Priemerná a najhoršia zložitosť triedenia výberu je O(n²) , kde n je počet položiek. Z tohto dôvodu nie je vhodný pre veľké súbory údajov.

Triedenie výberu sa vo všeobecnosti používa, keď -

Je potrebné triediť malé pole
Na cene výmeny nezáleží
Je povinné skontrolovať všetky prvky

Teraz sa pozrime na algoritmus triedenia výberu.

Algoritmus

 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

Fungovanie algoritmu triedenia výberu

Teraz sa pozrime na fungovanie algoritmu triedenia výberu.

Aby sme pochopili fungovanie triediaceho algoritmu Selection, zoberme si nezoradené pole. Na príklade bude jednoduchšie pochopiť triedenie výberu.

Nech sú prvky poľa -

Teraz, pre prvú pozíciu v triedenom poli, sa má postupne skenovať celé pole.

v súčasnosti 12 je uložený na prvej pozícii, po prehľadaní celého poľa sa zistí, že 8 je najmenšia hodnota.

min max

Takže zameňte 12 za 8. Po prvej iterácii sa 8 objaví na prvej pozícii v triedenom poli.

Pre druhú pozíciu, kde je momentálne uložená 29, opäť postupne skenujeme zvyšok položiek nezoradeného poľa. Po skenovaní zistíme, že 12 je druhý najnižší prvok v poli, ktorý by sa mal objaviť na druhej pozícii.

Teraz vymeňte 29 za 12. Po druhej iterácii sa 12 objaví na druhej pozícii v triedenom poli. Takže po dvoch iteráciách sa dve najmenšie hodnoty umiestnia na začiatok zoradeným spôsobom.

Rovnaký proces sa aplikuje na zvyšok prvkov poľa. Teraz ukazujeme obrázkové znázornenie celého procesu triedenia.

Teraz je pole úplne zoradené.

Zložitosť triedenia výberu

Teraz sa pozrime na časovú zložitosť triedenia výberu v najlepšom prípade, priemernom prípade a v najhoršom prípade. Uvidíme aj priestorovú náročnosť výberu.

1. Časová zložitosť

Prípad	Časová zložitosť
Najlepší prípad	O(n²)
Priemerný prípad	O(n²)
V najhoršom prípade	O(n²)

O(n²)

2. Zložitosť priestoru

Vesmírna zložitosť	O(1)
Stabilný	ÁNO

Priestorová zložitosť triedenia výberu je O(1). Je to preto, že pri triedení výberu je na výmenu potrebná ďalšia premenná.

Implementácia triedenia výberu

Teraz sa pozrime na výberové programy v rôznych programovacích jazykoch.

Program: Napíšte program na implementáciu triedenia výberu v jazyku C.

 #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;>

Výkon:

Program: Napíšte program na implementáciu triedenia výberu v jazyku 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;>

Výkon:

Po vykonaní vyššie uvedeného kódu bude výstupom -

Tak, to je o článku všetko. Dúfam, že článok bude pre vás užitočný a poučný.

Tento článok nebol obmedzený len na algoritmus. Diskutovali sme aj o zložitosti triedenia výberu, práci a implementácii v rôznych programovacích jazykoch.

TechCodeview

Algoritmus triedenia výberu