VALINTA LAJITTELE - DS OPETUSOHJELMA

Tässä artikkelissa käsittelemme valintalajittelualgoritmia. Myös valintalajittelun toimintatapa on yksinkertainen. Tämä artikkeli on erittäin hyödyllinen ja mielenkiintoinen opiskelijoille, koska he saattavat kohdata valintalajittelun kysymyksenä kokeissaan. Joten on tärkeää keskustella aiheesta.

Valintalajittelussa taulukon lajittelemattomien elementtien joukosta valitaan pienin arvo jokaisessa ajossa ja lisätään sopivaan paikkaan taulukossa. Se on myös yksinkertaisin algoritmi. Se on paikallaan oleva vertailulajittelualgoritmi. Tässä algoritmissa matriisi on jaettu kahteen osaan, ensin on lajiteltu osa ja toinen on lajittelematon osa. Aluksi taulukon lajiteltu osa on tyhjä ja lajittelematon osa on annettu taulukko. Lajiteltu osa sijoitetaan vasemmalle, kun taas lajittelematon osa sijoitetaan oikealle.

Valintalajittelussa ensimmäinen pienin elementti valitaan lajittelemattomasta taulukosta ja sijoitetaan ensimmäiseen paikkaan. Tämän jälkeen valitaan toiseksi pienin elementti ja asetetaan se toiseen asentoon. Prosessi jatkuu, kunnes taulukko on lajiteltu kokonaan.

Valintalajittelun keskimääräinen ja pahimman tapauksen monimutkaisuus on Päällä²) , missä n on kohteiden lukumäärä. Tästä johtuen se ei sovellu suurille tietojoukoille.

Valintalajittelua käytetään yleensä, kun -

Pieni joukko on lajiteltava
Vaihtohinnalla ei ole väliä
Kaikkien elementtien tarkistaminen on pakollista

Katsotaanpa nyt valintalajittelun algoritmia.

Algoritmi

 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

Valintalajittelualgoritmin työskentely

Katsotaanpa nyt valintalajittelualgoritmin toimintaa.

Ymmärtääksesi valintalajittelualgoritmin toiminnan, otetaan lajittelematon matriisi. Valintalajittelu on helpompi ymmärtää esimerkin avulla.

Olkoon taulukon elementit -

Nyt lajitellun taulukon ensimmäistä sijaintia varten koko taulukko on tarkistettava peräkkäin.

Nykyisessä, 12 on tallennettu ensimmäiseen paikkaan, kun koko taulukko on haettu, havaitaan, että 8 on pienin arvo.

osoitin kohdassa c

Joten vaihda 12 8:lla. Ensimmäisen iteraation jälkeen 8 ilmestyy lajitellun taulukon ensimmäiseen paikkaan.

Toista sijaintia varten, jossa 29 on tällä hetkellä tallennettu, skannaamme jälleen peräkkäin loput lajittelemattoman taulukon kohteet. Skannauksen jälkeen huomaamme, että 12 on taulukon toiseksi alin elementti, jonka pitäisi esiintyä toisessa paikassa.

Vaihda nyt 29 12:een. Toisen iteraation jälkeen 12 ilmestyy lajitellun taulukon toiseen paikkaan. Joten kahden iteroinnin jälkeen kaksi pienintä arvoa sijoitetaan alkuun lajiteltuna.

Samaa prosessia sovelletaan muihin taulukon elementteihin. Nyt näytämme kuvallisen esityksen koko lajitteluprosessista.

Nyt matriisi on täysin lajiteltu.

Valinnan lajittelun monimutkaisuus

Katsotaan nyt valintalajittelun aikamonimutkaisuus parhaassa tapauksessa, keskimääräisessä tapauksessa ja pahimmassa tapauksessa. Näemme myös valintalajin monimutkaisuuden.

1. Aika monimutkaisuus

Asia	Aika monimutkaisuus
Paras tapaus	Päällä²)
Keskimääräinen tapaus	Päällä²)
Pahimmassa tapauksessa	Päällä²)

Päällä²)

2. Tilan monimutkaisuus

Avaruuden monimutkaisuus	O(1)
Vakaa	JOO

Valintalajittelun monimutkaisuus on O(1). Tämä johtuu siitä, että valintalajittelussa vaihtoon tarvitaan ylimääräinen muuttuja.

Valintalajittelun toteutus

Katsotaanpa nyt valintaohjelmien lajittelua eri ohjelmointikielillä.

Ohjelmoida: Kirjoita ohjelma valintalajittelun toteuttamiseksi C-kielellä.

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

Lähtö:

Ohjelmoida: Kirjoita ohjelma valintalajittelun toteuttamiseksi Javassa.

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

Lähtö:

Yllä olevan koodin suorittamisen jälkeen tulos on -

Eli siinä kaikki artikkelista. Toivottavasti artikkeli on hyödyllinen ja informatiivinen sinulle.

Tämä artikkeli ei rajoittunut vain algoritmiin. Olemme myös keskustelleet valintalajittelun monimutkaisuudesta, toiminnasta ja toteutuksesta eri ohjelmointikielillä.