SORTARE SELECȚIE - TUTORIAL DS

În acest articol, vom discuta despre algoritmul de sortare a selecției. Procedura de lucru de sortare de selecție este, de asemenea, simplă. Acest articol va fi foarte util și interesant pentru studenți, deoarece s-ar putea confrunta cu sortarea selecției ca întrebare în examenele lor. Deci, este important să discutăm subiectul.

În sortarea prin selecție, cea mai mică valoare dintre elementele nesortate ale matricei este selectată la fiecare trecere și inserată în poziția corespunzătoare în matrice. Este, de asemenea, cel mai simplu algoritm. Este un algoritm de sortare prin comparație în loc. În acest algoritm, matricea este împărțită în două părți, prima este o parte sortată, iar alta este partea nesortată. Inițial, partea sortată a matricei este goală, iar partea nesortată este matricea dată. Piesa sortată este plasată în stânga, în timp ce partea nesortată este plasată în dreapta.

În sortarea prin selecție, primul element cel mai mic este selectat din matricea nesortată și plasat la prima poziție. După aceea, al doilea cel mai mic element este selectat și plasat în a doua poziție. Procesul continuă până când matricea este sortată complet.

Complexitatea medie și cel mai rău caz a sortării selecției este Pe²) , Unde n este numărul de articole. Din acest motiv, nu este potrivit pentru seturi mari de date.

Sortarea selecției este utilizată în general atunci când -

O matrice mică trebuie sortată
Costul de schimb nu contează
Este obligatorie verificarea tuturor elementelor

Acum, să vedem algoritmul de sortare a selecției.

Algoritm

 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

Funcționarea algoritmului de sortare a selecției

Acum, să vedem funcționarea algoritmului de sortare a selecției.

Pentru a înțelege funcționarea algoritmului de sortare a selecției, să luăm o matrice nesortată. Va fi mai ușor de înțeles sortarea Selecție printr-un exemplu.

Fie elementele matricei sunt -

Acum, pentru prima poziție în matricea sortată, întreaga matrice trebuie scanată secvenţial.

În prezent, 12 este stocat la prima pozitie, dupa cautarea intregii matrice, se constata ca 8 este cea mai mică valoare.

clasa abstractă

Deci, schimbați 12 cu 8. După prima iterație, 8 va apărea la prima poziție în matricea sortată.

Pentru a doua poziție, în care 29 este stocat în prezent, scanăm din nou secvenţial restul elementelor din matricea nesortată. După scanare, constatăm că 12 este al doilea cel mai jos element din matrice care ar trebui să apară la a doua poziția.

Acum, schimbați 29 cu 12. După a doua iterație, 12 va apărea la a doua poziție în matricea sortată. Deci, după două iterații, cele mai mici două valori sunt plasate la început într-un mod sortat.

Același proces este aplicat pentru restul elementelor matricei. Acum, arătăm o reprezentare picturală a întregului proces de sortare.

Acum, matricea este complet sortată.

Complexitatea sortării selecției

Acum, să vedem complexitatea de timp a sortării selecției în cel mai bun caz, mediu și în cel mai rău caz. Vom vedea, de asemenea, complexitatea spațială a sortării selecției.

1. Complexitatea timpului

Caz	Complexitatea timpului
Cel mai bun caz	Pe²)
Caz mediu	Pe²)
Cel mai rău caz	Pe²)

Pe²)

2. Complexitatea spațială

Complexitatea spațială	O(1)
Grajd	DA

Complexitatea spațială a sortării selecției este O(1). Se datorează faptului că, în sortarea prin selecție, este necesară o variabilă suplimentară pentru schimbare.

Implementarea sortării de selecție

Acum, să vedem sortarea programelor de selecție în diferite limbaje de programare.

Program: Scrieți un program pentru a implementa sortarea de selecție în limbajul 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;>

Ieșire:

Program: Scrieți un program pentru a implementa sortarea de selecție în 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;>

Ieșire:

După executarea codului de mai sus, rezultatul va fi -

Deci, asta e totul despre articol. Sper că articolul vă va fi util și informativ.

Acest articol nu sa limitat doar la algoritm. De asemenea, am discutat despre complexitatea sortării selecției, funcționarea și implementarea în diferite limbaje de programare.

TechCodeview

Algoritmul de sortare a selecției