IZBOR RAZVRSTI - VADNICA ZA DS

V tem članku bomo razpravljali o algoritmu za razvrščanje izbire. Enostaven je tudi delovni postopek izbirnega sortiranja. Ta članek bo zelo koristen in zanimiv za študente, saj se lahko soočijo z izbirno vrsto vprašanja pri svojih izpitih. Zato je pomembno razpravljati o temi.

Pri izbirnem razvrščanju je najmanjša vrednost med nerazvrščenimi elementi matrike izbrana v vsakem prehodu in vstavljena na ustrezno mesto v matriki. Je tudi najpreprostejši algoritem. Je algoritem za razvrščanje s primerjavo na mestu. V tem algoritmu je niz razdeljen na dva dela, prvi je razvrščeni del, drugi pa nesortirani del. Na začetku je razvrščeni del matrike prazen, nesortirani del pa je dana matrika. Razvrščeni del je postavljen na levo, nerazvrščen del pa na desno.

Pri izbirnem razvrščanju je iz nerazvrščenega niza izbran prvi najmanjši element in postavljen na prvo mesto. Po tem je izbran drugi najmanjši element in postavljen na drugo mesto. Postopek se nadaljuje, dokler matrika ni v celoti razvrščena.

Povprečna in najslabša zapletenost izbirnega razvrščanja je O(n²) , kje n je število predmetov. Zaradi tega ni primeren za velike nabore podatkov.

Izbirno razvrščanje se običajno uporablja, ko -

Majhen niz je treba razvrstiti
Cena menjave ni pomembna
Obvezno je treba preveriti vse elemente

Zdaj pa si oglejmo algoritem izbirnega razvrščanja.

Algoritem

 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

Delovanje algoritma za razvrščanje izbire

Zdaj pa si oglejmo delovanje algoritma za razvrščanje izbire.

Da bi razumeli delovanje algoritma za razvrščanje izbire, vzemimo nerazvrščeno matriko. Razvrščanje izbire bo lažje razumeti na primeru.

Naj so elementi matrike -

Zdaj je treba za prvo pozicijo v razvrščeni matriki zaporedno pregledati celotno matriko.

Trenutno, 12 je shranjen na prvem mestu, po iskanju celotnega niza se ugotovi, da 8 je najmanjša vrednost.

10 ml je koliko

Torej, zamenjajte 12 z 8. Po prvi ponovitvi se bo 8 pojavilo na prvem mestu v razvrščeni matriki.

Za drugo pozicijo, kjer je trenutno shranjeno 29, spet zaporedno skeniramo preostale elemente nerazvrščenega niza. Po skeniranju ugotovimo, da je 12 drugi najnižji element v nizu, ki bi moral biti prikazan na drugem mestu.

Zdaj zamenjajte 29 z 12. Po drugi ponovitvi se bo 12 pojavilo na drugem mestu v razvrščeni matriki. Torej sta po dveh ponovitvah dve najmanjši vrednosti razvrščeni na začetek.

Enak postopek se uporabi za preostale elemente matrike. Zdaj prikazujemo slikovno predstavitev celotnega postopka sortiranja.

Sedaj je niz popolnoma urejen.

Kompleksnost razvrščanja izbire

Zdaj pa poglejmo časovno zahtevnost razvrščanja izbire v najboljšem primeru, povprečnem primeru in v najslabšem primeru. Videli bomo tudi prostorsko zahtevnost izbirne sorte.

1. Časovna zapletenost

Ovitek	Časovna zapletenost
Najboljši primer	O(n²)
Povprečen primer	O(n²)
V najslabšem primeru	O(n²)

O(n²)

2. Kompleksnost prostora

Kompleksnost prostora	O(1)
Stabilen	DA

Prostorska kompleksnost izbirnega razvrščanja je O(1). To je zato, ker je pri izbirnem razvrščanju za zamenjavo potrebna dodatna spremenljivka.

Izvedba izbirnega razvrščanja

Zdaj pa si oglejmo programe izbirnega razvrščanja v različnih programskih jezikih.

Program: Napišite program za izvajanje izbirnega razvrščanja v jeziku 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;>

Izhod:

Program: Napišite program za izvajanje izbirnega razvrščanja v Javi.

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

Izhod:

Po izvedbi zgornje kode bo rezultat -

Torej, to je vse o članku. Upam, da vam bo članek koristen in informativen.

Ta članek ni bil omejen le na algoritem. Razpravljali smo tudi o kompleksnosti sortiranja izbire, delovanju in implementaciji v različnih programskih jezikih.

TechCodeview

Algoritem za razvrščanje izbire