Ordenació de la selecció és un algorisme d'ordenació senzill i eficient que funciona seleccionant repetidament l'element més petit (o més gran) de la part no ordenada de la llista i movent-lo a la part ordenada de la llista.

L'algorisme selecciona repetidament l'element més petit (o més gran) de la part no ordenada de la llista i l'intercanvia amb el primer element de la part no ordenada. Aquest procés es repeteix per a la part restant sense ordenar fins que s'ordena tota la llista.

Com funciona l'algoritme d'ordenació de selecció?

Considerem la matriu següent com a exemple: arr[] = {64, 25, 12, 22, 11}

Primera passada:

• Per a la primera posició de la matriu ordenada, tota la matriu es recorre de l'índex 0 al 4 seqüencialment. La primera posició on 64 s'emmagatzema actualment, després de recórrer tota la matriu, queda clar que 11 és el valor més baix.
• Per tant, substituïu 64 per 11. Després d'una iteració 11 , que passa a ser el valor mínim de la matriu, tendeix a aparèixer a la primera posició de la llista ordenada.

Algoritme d'ordenació de selecció | Canvi del primer element amb el mínim de la matriu

Segona passada:

• Per a la segona posició, on hi ha 25, torneu a travessar la resta de la matriu de manera seqüencial.
• Després de recórrer, ho vam trobar 12 és el segon valor més baix de la matriu i hauria d'aparèixer al segon lloc de la matriu, per tant intercanvieu aquests valors.

Algoritme d'ordenació de selecció | intercanviant i=1 amb el següent element mínim

Tercera passada:

• Ara, pel tercer lloc, on 25 està present de nou travessa la resta de la matriu i troba el tercer valor mínim present a la matriu.
• Mentre travessa, 22 va resultar ser el tercer valor menys i hauria d'aparèixer al tercer lloc de la matriu, per tant, intercanvia 22 amb l'element present en la tercera posició.

Algoritme d'ordenació de selecció | intercanviant i=2 amb el següent element mínim

Quarta passada:

• De la mateixa manera, per a la quarta posició recorreu la resta de la matriu i trobeu el quart element mínim de la matriu
• Com 25 és el quart valor més baix, per tant, es col·locarà a la quarta posició.

Algoritme d'ordenació de selecció | intercanviant i=3 amb el següent element mínim

Cinquena passada:

• Finalment, el valor més gran present a la matriu es col·loca automàticament a l'última posició de la matriu
• La matriu resultant és la matriu ordenada.

Algoritme d'ordenació de selecció | Matriu ordenat obligatori

A continuació es mostra la implementació de l'enfocament anterior:

// C++ program for implementation of // selection sort #include  using namespace std; // Function for Selection sort void selectionSort(int arr[], int n) {  int i, j, min_idx;  // One by one move boundary of  // unsorted subarray  for (i = 0; i < n - 1; i++) {  // Find the minimum element in  // unsorted array  min_idx = i;  for (j = i + 1; j < n; j++) {  if (arr[j] < arr[min_idx])  min_idx = j;  }  // Swap the found minimum element  // with the first element  if (min_idx != i)  swap(arr[min_idx], arr[i]);  } } // Function to print an array void printArray(int arr[], int size) {  int i;  for (i = 0; i < size; i++) {  cout << arr[i] << ' ';  cout << endl;  } } // Driver program int main() {  int arr[] = { 64, 25, 12, 22, 11 };  int n = sizeof(arr) / sizeof(arr[0]);  // Function Call  selectionSort(arr, n);  cout << 'Sorted array: 
';  printArray(arr, n);  return 0; } // This is code is contributed by rathbhupendra>

// C program for implementation of selection sort #include  void swap(int *xp, int *yp) {  int temp = *xp;  *xp = *yp;  *yp = temp; } void selectionSort(int arr[], int n) {  int i, j, min_idx;  // One by one move boundary of unsorted subarray  for (i = 0; i < n-1; i++)  {  // Find the minimum element in unsorted array  min_idx = i;  for (j = i+1; j < n; j++)  if (arr[j] < arr[min_idx])  min_idx = j;  // Swap the found minimum element with the first element  if(min_idx != i)  swap(&arr[min_idx], &arr[i]);  } } /* Function to print an array */ void printArray(int arr[], int size) {  int i;  for (i=0; i < size; i++)  printf('%d ', arr[i]);  printf('
'); } // Driver program to test above functions int main() {  int arr[] = {64, 25, 12, 22, 11};  int n = sizeof(arr)/sizeof(arr[0]);  selectionSort(arr, n);  printf('Sorted array: 
');  printArray(arr, n);  return 0; }>

// Java program for implementation of Selection Sort import java.io.*; public class SelectionSort {  void sort(int arr[])  {  int n = arr.length;  // One by one move boundary of unsorted subarray  for (int i = 0; i < n-1; i++)  {  // Find the minimum element in unsorted array  int min_idx = i;  for (int j = i+1; j < n; j++)  if (arr[j] < arr[min_idx])  min_idx = j;  // Swap the found minimum element with the first  // element  int temp = arr[min_idx];  arr[min_idx] = arr[i];  arr[i] = temp;  }  }  // Prints the array  void printArray(int arr[])  {  int n = arr.length;  for (int i=0; i

# Python program for implementation of Selection # Sort A = [64, 25, 12, 22, 11] # Traverse through all array elements for i in range(len(A)-1): # Find the minimum element in remaining  # unsorted array min_idx = i for j in range(i+1, len(A)): if A[min_idx]>A[j]: min_idx = j # Canvia l'element mínim trobat amb # el primer element A[i], A[min_idx] = A[min_idx], A[i] # Codi del controlador per provar a sobre d'imprimir ('Matriu ordenat ') per a i a l'interval(len(A)): print(A[i],end=' ')>

// C# program for implementation  // of Selection Sort using System; class GFG {   static void sort(int []arr)  {  int n = arr.Length;  // One by one move boundary of unsorted subarray  for (int i = 0; i < n - 1; i++)  {  // Find the minimum element in unsorted array  int min_idx = i;  for (int j = i + 1; j < n; j++)  if (arr[j] < arr[min_idx])  min_idx = j;  // Swap the found minimum element with the first  // element  int temp = arr[min_idx];  arr[min_idx] = arr[i];  arr[i] = temp;  }  }  // Prints the array  static void printArray(int []arr)  {  int n = arr.Length;  for (int i=0; i

>

 // PHP program for implementation  // of selection sort  function selection_sort(&$arr, $n) { for($i = 0; $i < $n ; $i++) { $low = $i; for($j = $i + 1; $j < $n ; $j++) { if ($arr[$j] < $arr[$low]) { $low = $j; } } // swap the minimum value to $ith node if ($arr[$i]>$arr[$baix]) { $tmp = $arr[$i]; $arr[$i] = $arr[$baix]; $arr[$baix] = $tmp; } } } // Codi del controlador $arr = array(64, 25, 12, 22, 11); $len = comptar ($arr); selection_sort($arr, $len); echo 'Matriu ordenat: 
'; per ($i = 0; $i< $len; $i++) echo $arr[$i] . ' '; // This code is contributed  // by Deepika Gupta.  ?>>

Sorted array: 11 12 22 25 64>

Anàlisi de complexitat de l'ordenació de la selecció

Complexitat temporal: La complexitat temporal de l'ordenació de selecció és O(N ² ) ja que hi ha dos bucles imbricats:

• Un bucle per seleccionar un element de la matriu un per un = O (N)
• Un altre bucle per comparar aquest element amb tots els altres elements Array = O (N)
• Per tant complexitat global = O (N) * O (N) = O (N * N) = O (N²)

Espai auxiliar: O(1), ja que l'única memòria addicional que s'utilitza és per a variables temporals mentre s'intercanvien dos valors a Array. L'ordenació de selecció mai fa més que intercanvis O(N) i pot ser útil quan l'escriptura de memòria és costosa.

cadena adjunta java

Avantatges de l'algoritme d'ordenació de selecció

• Simple i fàcil d'entendre.
• Funciona bé amb conjunts de dades petits.

Inconvenients de l'algoritme d'ordenació de selecció

• L'ordenació de selecció té una complexitat temporal de O(n^2) en el pitjor i mitjà dels casos.
• No funciona bé en grans conjunts de dades.
• No conserva l'ordre relatiu dels elements amb claus iguals, la qual cosa significa que no és estable.

Preguntes freqüents sobre l'ordenació de selecció

Q1. És estable l'algoritme d'ordenació de selecció?

La implementació predeterminada de l'algoritme d'ordenació de selecció és no estable . Tanmateix, es pot fer estable. Si us plau, mireu el Ordenació de selecció estable per als detalls.

P2. L'algoritme d'ordenació de selecció està al seu lloc?

Sí, l'algoritme d'ordenació de selecció és un algorisme in situ, ja que no requereix espai addicional.