ORDENACIÓ DE LA SELECCIÓ

En aquest article, parlarem de l'algoritme d'ordenació de selecció. El procediment de treball de selecció també és senzill. Aquest article serà molt útil i interessant per als estudiants, ja que podrien enfrontar-se a la selecció com a pregunta en els seus exàmens. Per tant, és important parlar del tema.

En l'ordenació per selecció, el valor més petit entre els elements no ordenats de la matriu es selecciona a cada passada i s'insereix a la posició adequada a la matriu. També és l'algoritme més senzill. És un algorisme d'ordenació de comparació in situ. En aquest algorisme, la matriu es divideix en dues parts, la primera és la part ordenada i una altra és la part no ordenada. Inicialment, la part ordenada de la matriu està buida i la part no ordenada és la matriu donada. La part ordenada es col·loca a l'esquerra, mentre que la part no ordenada es col·loca a la dreta.

En l'ordenació per selecció, el primer element més petit es selecciona de la matriu sense ordenar i es col·loca a la primera posició. Després d'aquest segon element més petit es selecciona i es col·loca a la segona posició. El procés continua fins que la matriu està completament ordenada.

La complexitat mitjana i del pitjor dels casos de l'ordenació de selecció és O (n²) , on n és el nombre d'elements. Per això, no és adequat per a grans conjunts de dades.

L'ordenació de selecció s'utilitza generalment quan -

S'ha d'ordenar una petita matriu
El cost del canvi no importa
És obligatori comprovar tots els elements

Ara, vegem l'algorisme d'ordenació de selecció.

Algorisme

 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

Funcionament de l'algorisme d'ordenació de selecció

Ara, vegem el funcionament de l'algoritme d'ordenació de selecció.

Per entendre el funcionament de l'algorisme d'ordenació de selecció, prenem una matriu sense ordenar. Serà més fàcil entendre l'ordenació de la selecció mitjançant un exemple.

Siguin els elements de la matriu -

Ara, per a la primera posició de la matriu ordenada, la matriu sencera s'ha d'escanejar seqüencialment.

Al present, 12 s'emmagatzema a la primera posició, després de cercar tota la matriu, es troba que 8 és el valor més petit.

mineria de dades

Per tant, intercanvieu 12 amb 8. Després de la primera iteració, 8 apareixerà a la primera posició de la matriu ordenada.

Per a la segona posició, on s'emmagatzema 29 actualment, tornem a escanejar seqüencialment la resta d'elements de la matriu no ordenada. Després d'escanejar, trobem que 12 és el segon element més baix de la matriu que hauria d'aparèixer a la segona posició.

Ara, intercanvieu 29 amb 12. Després de la segona iteració, 12 apareixerà a la segona posició de la matriu ordenada. Així, després de dues iteracions, els dos valors més petits es col·loquen al principi de manera ordenada.

El mateix procés s'aplica a la resta d'elements de la matriu. Ara, estem mostrant una representació pictòrica de tot el procés de classificació.

Ara, la matriu està completament ordenada.

Complexitat de l'ordenació de la selecció

Ara, vegem la complexitat temporal de l'ordenació de la selecció en el millor dels casos, en el cas mitjà i en el pitjor dels casos. També veurem la complexitat espacial de l'ordenació de selecció.

1. Complexitat temporal

Caixa	Complexitat temporal
Millor cas	O (n²)
Cas mitjà	O (n²)
Pitjor dels casos	O (n²)

O (n²)

2. Complexitat espacial

Complexitat espacial	O(1)
Estable	SÍ

La complexitat espacial de l'ordenació de selecció és O(1). És perquè, en l'ordenació per selecció, es requereix una variable addicional per a l'intercanvi.

Implementació de l'ordenació de selecció

Ara, vegem els programes de selecció ordenats en diferents llenguatges de programació.

Programa: Escriu un programa per implementar l'ordenació de selecció en llenguatge 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;>

Sortida:

Programa: Escriu un programa per implementar l'ordenació de selecció a 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;>

Sortida:

Després de l'execució del codi anterior, la sortida serà -

Per tant, això és tot sobre l'article. Espero que l'article us sigui útil i informatiu.

Aquest article no es limitava només a l'algorisme. També hem parlat de la complexitat, el funcionament i la implementació de l'ordenació de la selecció en diferents llenguatges de programació.

TechCodeview

Algorisme d'ordenació de selecció