UTVALGSSORTERING - DS VEILEDNING

I denne artikkelen vil vi diskutere algoritmen for valgsortering. Arbeidsprosedyren for valgsort er også enkel. Denne artikkelen vil være svært nyttig og interessant for studenter, da de kan møte utvalgssortering som et spørsmål i eksamenene deres. Så det er viktig å diskutere temaet.

I utvalgssortering velges den minste verdien blant de usorterte elementene i matrisen i hver pass og settes inn i den passende posisjonen i matrisen. Det er også den enkleste algoritmen. Det er en på stedet sammenligningssorteringsalgoritme. I denne algoritmen er matrisen delt inn i to deler, først er den sorterte delen, og en annen er den usorterte delen. Til å begynne med er den sorterte delen av matrisen tom, og usortert del er den gitte matrisen. Sortert del er plassert til venstre, mens den usorterte delen er plassert til høyre.

I utvalgssortering velges det første minste elementet fra den usorterte matrisen og plasseres på den første posisjonen. Etter det er det nest minste elementet valgt og plassert i den andre posisjonen. Prosessen fortsetter til matrisen er helt sortert.

Den gjennomsnittlige og verste fall-kompleksiteten av utvalg sort er På²) , hvor n er antall varer. På grunn av dette er den ikke egnet for store datasett.

Utvalgssortering brukes vanligvis når -

En liten matrise skal sorteres
Byttekostnaden spiller ingen rolle
Det er obligatorisk å kontrollere alle elementer

La oss nå se algoritmen for utvalgssortering.

Algoritme

 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

Working of Selection sort Algoritme

La oss nå se hvordan sorteringsalgoritmen for utvalg fungerer.

For å forstå hvordan sorteringsalgoritmen for utvalg fungerer, la oss ta en usortert matrise. Det vil være lettere å forstå utvalgssorteringen via et eksempel.

La elementene i array være -

Nå, for den første posisjonen i den sorterte matrisen, skal hele matrisen skannes sekvensielt.

Akkurat nå, 12 er lagret i den første posisjonen, etter å ha søkt i hele arrayet, finner det ut at 8 er den minste verdien.

hei verden med java

Så bytt 12 med 8. Etter den første iterasjonen vil 8 vises på den første posisjonen i den sorterte matrisen.

For den andre posisjonen, hvor 29 er lagret for øyeblikket, skanner vi igjen sekvensielt resten av elementene i usortert array. Etter skanning finner vi at 12 er det nest laveste elementet i matrisen som skal vises i andre posisjon.

Bytt nå 29 med 12. Etter den andre iterasjonen vil 12 vises på den andre posisjonen i den sorterte matrisen. Så, etter to iterasjoner, plasseres de to minste verdiene i begynnelsen på en sortert måte.

Den samme prosessen brukes på resten av array-elementene. Nå viser vi en billedlig fremstilling av hele sorteringsprosessen.

Nå er matrisen fullstendig sortert.

Utvalgssorteringskompleksitet

La oss nå se tidskompleksiteten til utvalgssortering i beste fall, gjennomsnittlig tilfelle og i verste fall. Vi vil også se plasskompleksiteten til utvalgssorten.

1. Tidskompleksitet

Sak	Tidskompleksitet
Beste sak	På²)
Gjennomsnittlig sak	På²)
Worst Case	På²)

På²)

2. Romkompleksitet

Plass kompleksitet	O(1)
Stabil	JA

Romkompleksiteten til utvalgssortering er O(1). Det er fordi, i utvalgssortering, kreves det en ekstra variabel for å bytte.

Gjennomføring av utvalgssortering

La oss nå se de utvalgte programmene sortere på forskjellige programmeringsspråk.

Program: Skriv et program for å implementere utvalgssortering i C-språk.

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

Produksjon:

Program: Skriv et program for å implementere utvalgssortering i 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;>

Produksjon:

Etter utførelse av koden ovenfor, vil utgangen være -

Så det handler om artikkelen. Håper artikkelen vil være nyttig og informativ for deg.

Denne artikkelen var ikke bare begrenset til algoritmen. Vi har også diskutert utvalgets kompleksitet, arbeid og implementering i forskjellige programmeringsspråk.

TechCodeview

Valg sorteringsalgoritme