SELECTIE SORTEREN - DS-ZELFSTUDIE

In dit artikel bespreken we het selectiesorteeralgoritme. De werkwijze van selectiesortering is ook eenvoudig. Dit artikel zal zeer nuttig en interessant zijn voor studenten, aangezien zij tijdens hun examens te maken kunnen krijgen met selectievragen. Het is dus belangrijk om het onderwerp te bespreken.

Bij selectiesortering wordt bij elke doorgang de kleinste waarde van de ongesorteerde elementen van de array geselecteerd en op de juiste positie in de array ingevoegd. Het is ook het eenvoudigste algoritme. Het is een in-place vergelijkingssorteeralgoritme. In dit algoritme wordt de array in twee delen verdeeld: het eerste is een gesorteerd deel en een ander deel is het ongesorteerde deel. Aanvankelijk is het gesorteerde deel van de array leeg en is het ongesorteerde deel de gegeven array. Het gesorteerde deel wordt links geplaatst, het ongesorteerde deel rechts.

Bij selectiesortering wordt het eerste kleinste element uit de ongesorteerde array geselecteerd en op de eerste positie geplaatst. Daarna wordt het op een na kleinste element geselecteerd en op de tweede positie geplaatst. Het proces gaat door totdat de array volledig is gesorteerd.

De gemiddelde en slechtst mogelijke complexiteit van selectiesoort is Op²) , waar N is het aantal artikelen. Hierdoor is het niet geschikt voor grote datasets.

Selectie sorteren wordt over het algemeen gebruikt wanneer -

Een kleine array moet worden gesorteerd
De kosten voor het wisselen maken niet uit
Het is verplicht om alle elementen te controleren

Laten we nu eens kijken naar het algoritme van selectiesortering.

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

Werking van selectie-sorteeralgoritme

Laten we nu eens kijken naar de werking van het selectie-sorteeralgoritme.

Om de werking van het selectie-sorteeralgoritme te begrijpen, nemen we een ongesorteerde array. Het zal gemakkelijker zijn om de selectiesortering te begrijpen aan de hand van een voorbeeld.

Laat de elementen van array zijn -

Nu moet voor de eerste positie in de gesorteerde array de gehele array opeenvolgend worden gescand.

Momenteel, 12 is opgeslagen op de eerste positie, na het doorzoeken van de hele array blijkt dat 8 is de kleinste waarde.

1 miljard tot miljoen

Vervang dus 12 door 8. Na de eerste iteratie verschijnt 8 op de eerste positie in de gesorteerde array.

Voor de tweede positie, waar momenteel 29 is opgeslagen, scannen we opnieuw opeenvolgend de rest van de items van de ongesorteerde array. Na het scannen ontdekken we dat 12 het op een na laagste element in de array is dat op de tweede positie zou moeten verschijnen.

Verwissel nu 29 door 12. Na de tweede iteratie verschijnt 12 op de tweede positie in de gesorteerde array. Na twee iteraties worden de twee kleinste waarden dus gesorteerd aan het begin geplaatst.

Hetzelfde proces wordt toegepast op de rest van de array-elementen. Nu laten we een grafische weergave zien van het hele sorteerproces.

Nu is de array volledig gesorteerd.

Complexiteit van selectiesortering

Laten we nu eens kijken naar de tijdscomplexiteit van de selectie, in het beste geval, het gemiddelde geval en in het slechtste geval. We zullen ook de ruimtelijke complexiteit van de selectiesoort zien.

1. Tijdcomplexiteit

Geval	Tijdcomplexiteit
Beste geval	Op²)
Gemiddeld geval	Op²)
Het slechtste geval	Op²)

Op²)

2. Ruimtecomplexiteit

Ruimtecomplexiteit	O(1)
Stal	JA

De ruimtecomplexiteit van selectiesortering is O(1). De reden hiervoor is dat bij selectiesortering een extra variabele nodig is voor het wisselen.

Implementatie van selectiesortering

Laten we nu eens kijken naar de selectieprogramma's in verschillende programmeertalen.

Programma: Schrijf een programma om selectiesortering in C-taal te implementeren.

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

Uitgang:

Programma: Schrijf een programma om selectiesortering in Java te implementeren.

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

Uitgang:

Na de uitvoering van bovenstaande code zal de uitvoer zijn:

Dus dat is alles over het artikel. Ik hoop dat het artikel nuttig en informatief voor u zal zijn.

Dit artikel beperkte zich niet alleen tot het algoritme. We hebben ook de complexiteit, werking en implementatie van Selectie in verschillende programmeertalen besproken.

TechCodeview

Selectie Sorteeralgoritme