ODABIR SORTIRAJ - VODIČ ZA DS

U ovom ćemo članku raspravljati o algoritmu sortiranja odabirom. Radni postupak odabira sortiranja je također jednostavan. Ovaj će članak biti vrlo koristan i zanimljiv studentima jer bi se mogli suočiti s odabirom kao pitanjem na svojim ispitima. Dakle, važno je razgovarati o temi.

U selekcijskom sortiranju, najmanja vrijednost među nesortiranim elementima niza odabire se u svakom prolazu i umeće na odgovarajuće mjesto u nizu. To je ujedno i najjednostavniji algoritam. To je algoritam za sortiranje usporedbe na mjestu. U ovom algoritmu, niz je podijeljen na dva dijela, prvi je sortirani dio, a drugi je nesortirani dio. U početku je sortirani dio niza prazan, a nesortirani dio je zadani niz. Sortirani dio nalazi se lijevo, dok se nesortirani dio nalazi desno.

U selekcijskom sortiranju, prvi najmanji element odabire se iz nesortiranog niza i postavlja na prvo mjesto. Nakon toga odabire se drugi najmanji element i postavlja na drugu poziciju. Proces se nastavlja sve dok niz nije u potpunosti sortiran.

Prosječna i najgora složenost odabira sortiranja je Na²) , gdje n je broj predmeta. Zbog toga nije prikladan za velike skupove podataka.

Sortiranje odabira općenito se koristi kada -

Mali niz treba sortirati
Cijena zamjene nije bitna
Obavezna je provjera svih elemenata

Pogledajmo sada algoritam selekcijskog sortiranja.

Algoritam

 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

Rad algoritma sortiranja selekcije

Pogledajmo sada kako radi algoritam sortiranja selekcije.

Da bismo razumjeli rad algoritma sortiranja selekcije, uzmimo nesortirani niz. Lakše ćete razumjeti sortiranje odabira putem primjera.

Neka su elementi niza -

Sada, za prvu poziciju u sortiranom nizu, cijeli niz treba skenirati uzastopno.

Trenutno, 12 je pohranjen na prvoj poziciji, nakon pretraživanja cijelog niza, ustanovljeno je da 8 je najmanja vrijednost.

apstraktna klasa

Dakle, zamijenite 12 s 8. Nakon prve iteracije, 8 će se pojaviti na prvom mjestu u sortiranom nizu.

Za drugu poziciju, gdje je 29 trenutno pohranjeno, ponovno sekvencijalno skeniramo ostatak stavki nesortiranog niza. Nakon skeniranja, nalazimo da je 12 drugi najniži element u nizu koji bi se trebao pojaviti na drugom mjestu.

Sada zamijenite 29 s 12. Nakon druge iteracije, 12 će se pojaviti na drugom mjestu u sortiranom nizu. Dakle, nakon dvije iteracije, dvije najmanje vrijednosti se postavljaju na početak sortirano.

Isti se postupak primjenjuje na ostale elemente niza. Sada prikazujemo slikovni prikaz cijelog procesa sortiranja.

Sada je niz potpuno sortiran.

Složenost sortiranja selekcije

Sada, da vidimo vremensku složenost sortiranja odabira u najboljem slučaju, prosječnom slučaju iu najgorem slučaju. Vidjet ćemo i prostornu složenost sortiranja selekcije.

1. Vremenska složenost

Slučaj	Vremenska složenost
Najbolji slučaj	Na²)
Prosječan slučaj	Na²)
Najgori slučaj	Na²)

Na²)

2. Složenost prostora

Složenost prostora	O(1)
Stabilan	DA

Prostorna složenost selekcijskog sortiranja je O(1). To je zato što je u izbornom sortiranju dodatna varijabla potrebna za zamjenu.

Implementacija selekcijskog sortiranja

Sada, pogledajmo programe sortiranja selekcije u različitim programskim jezicima.

Program: Napišite program za implementaciju selekcijskog sortiranja u C jeziku.

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

Izlaz:

Program: Napišite program za implementaciju selekcijskog sortiranja u 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;>

Izlaz:

Nakon izvršenja gornjeg koda, izlaz će biti -

Dakle, to je sve o članku. Nadamo se da će vam članak biti koristan i informativan.

Ovaj članak nije bio ograničen samo na algoritam. Također smo razgovarali o složenosti selekcije, radu i implementaciji u različitim programskim jezicima.

TechCodeview

Algoritam sortiranja odabirom