VÝBĚR SEŘADIT - VÝUKA DS

V tomto článku se budeme zabývat algoritmem řazení výběru. Pracovní postup třídění výběru je také jednoduchý. Tento článek bude pro studenty velmi užitečný a zajímavý, protože mohou čelit třídění výběru jako otázce při zkouškách. Je tedy důležité o tématu diskutovat.

Při třídění výběru se v každém průchodu vybere nejmenší hodnota mezi neseřazenými prvky pole a vloží se na příslušnou pozici do pole. Je to také nejjednodušší algoritmus. Je to na místě srovnávací třídicí algoritmus. V tomto algoritmu je pole rozděleno na dvě části, první je setříděná část a další je nesetříděná část. Zpočátku je seřazená část pole prázdná a neseřazená část je dané pole. Setříděná část je umístěna vlevo, zatímco nesetříděná část je umístěna vpravo.

Při třídění výběru je první nejmenší prvek vybrán z netříděného pole a umístěn na první pozici. Poté je vybrán druhý nejmenší prvek a umístěn na druhou pozici. Proces pokračuje, dokud není pole zcela seřazeno.

Průměrná a nejhorší složitost třídění výběru je Na²) , kde n je počet položek. Z tohoto důvodu není vhodný pro velké datové sady.

Výběrové řazení se obecně používá, když -

Je třeba třídit malé pole
Na ceně výměny nezáleží
Je nutné zkontrolovat všechny prvky

Nyní se podívejme na algoritmus řazení výběru.

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

Fungování algoritmu řazení výběru

Nyní se podívejme, jak funguje třídicí algoritmus výběru.

Abychom pochopili fungování třídícího algoritmu Selection, vezměme si netříděné pole. Uspořádání výběru bude snazší pochopit na příkladu.

Nechť prvky pole jsou -

Nyní, pro první pozici v seřazeném poli, má být postupně skenováno celé pole.

V současnosti, 12 je uložen na první pozici, po prohledání celého pole se zjistí, že 8 je nejmenší hodnota.

urfi javed

Takže zaměňte 12 za 8. Po první iteraci se 8 objeví na první pozici v seřazeném poli.

Pro druhou pozici, kde je aktuálně uloženo 29, opět postupně skenujeme zbytek položek netříděného pole. Po skenování zjistíme, že 12 je druhý nejnižší prvek v poli, který by se měl objevit na druhé pozici.

Nyní vyměňte 29 za 12. Po druhé iteraci se 12 objeví na druhé pozici v seřazeném poli. Po dvou iteracích se tedy dvě nejmenší hodnoty umístí na začátek seřazeným způsobem.

Stejný proces se aplikuje na zbytek prvků pole. Nyní ukazujeme obrázkové znázornění celého procesu třídění.

Nyní je pole kompletně seřazeno.

Složitost řazení výběru

Nyní se podívejme na časovou složitost řazení výběru v nejlepším případě, průměrném případě a v nejhorším případě. Uvidíme také prostorovou složitost výběru.

1. Časová složitost

Pouzdro	Časová složitost
Nejlepší případ	Na²)
Průměrný případ	Na²)
Nejhorší případ	Na²)

Na²)

2. Prostorová složitost

Vesmírná složitost	O(1)
Stabilní	ANO

Prostorová složitost třídění výběru je O(1). Je to proto, že při třídění výběru je pro výměnu vyžadována další proměnná.

Implementace třídění výběru

Nyní se podívejme na výběrové řazení programů v různých programovacích jazycích.

Program: Napište program pro implementaci třídění výběru v jazyce 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ýstup:

Program: Napište program pro implementaci třídění výběru v Javě.

 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ýstup:

Po provedení výše uvedeného kódu bude výstupem -

Tak to je k článku vše. Doufám, že vám článek bude užitečný a informativní.

Tento článek nebyl omezen pouze na algoritmus. Také jsme diskutovali o složitosti řazení výběru, práci a implementaci v různých programovacích jazycích.

TechCodeview

Algoritmus řazení výběru