Tri de sélection est un algorithme de tri simple et efficace qui fonctionne en sélectionnant à plusieurs reprises l'élément le plus petit (ou le plus grand) de la partie non triée de la liste et en le déplaçant vers la partie triée de la liste.

L'algorithme sélectionne à plusieurs reprises l'élément le plus petit (ou le plus grand) de la partie non triée de la liste et l'échange avec le premier élément de la partie non triée. Ce processus est répété pour la partie restante non triée jusqu'à ce que la liste entière soit triée.

Comment fonctionne l’algorithme de tri par sélection ?

Considérons le tableau suivant à titre d'exemple : arr[] = {64, 25, 12, 22, 11}

Premier passage:

• Pour la première position du tableau trié, l'ensemble du tableau est parcouru séquentiellement de l'index 0 à 4. La première position où 64 est actuellement stocké, après avoir parcouru tout le tableau, il est clair que onze est la valeur la plus basse.
• Ainsi, remplacez 64 par 11. Après une itération onze , qui se trouve être la plus petite valeur du tableau, a tendance à apparaître en première position de la liste triée.

Algorithme de tri par sélection | Échanger le 1er élément avec le minimum dans le tableau

Deuxième passage :

• Pour la deuxième position, où 25 est présent, parcourez à nouveau le reste du tableau de manière séquentielle.
• Après avoir traversé, nous avons constaté que 12 est la deuxième valeur la plus basse du tableau et elle doit apparaître à la deuxième place du tableau, échangez donc ces valeurs.

Algorithme de tri par sélection | échanger i=1 avec l'élément minimum suivant

Troisième passage :

• Maintenant, pour la troisième place, où 25 est à nouveau présent, parcourez le reste du tableau et trouvez la troisième plus petite valeur présente dans le tableau.
• En traversant, 22 s'est avéré être la troisième plus petite valeur et elle devrait apparaître à la troisième place du tableau, échangez donc 22 avec élément présent en troisième position.

Algorithme de tri par sélection | échanger i = 2 avec l'élément minimum suivant

Quatrième passage :

• De même, pour la quatrième position, parcourez le reste du tableau et trouvez le quatrième plus petit élément du tableau.
• Comme 25 est la 4ème valeur la plus basse, elle se placera donc à la quatrième position.

Algorithme de tri par sélection | échanger i = 3 avec l'élément minimum suivant

Cinquième passe :

• Enfin, la plus grande valeur présente dans le tableau est automatiquement placée à la dernière position du tableau.
• Le tableau obtenu est le tableau trié.

Algorithme de tri par sélection | Tableau trié requis

Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :

// 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 # Échangez l'élément minimum trouvé avec # le premier élément A[i], A[min_idx] = A[min_idx], A[i] # Code du pilote à tester ci-dessus, impression ('Tableau trié ') pour i dans range(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[$low]) { $tmp = $arr[$i]; $arr[$i] = $arr[$faible]; $arr[$low] = $tmp; } } } // Code du pilote $arr = array(64, 25, 12, 22, 11); $len = compte($arr); sélection_sort($arr, $len); echo 'Tableau trié : 
'; pour ($i = 0; $i< $len; $i++) echo $arr[$i] . ' '; // This code is contributed  // by Deepika Gupta.  ?>>

Sorted array: 11 12 22 25 64>

Analyse de complexité du tri par sélection

Complexité temporelle : La complexité temporelle du tri par sélection est SUR ² ) car il y a deux boucles imbriquées :

• Une boucle pour sélectionner un élément du tableau un par un = O(N)
• Une autre boucle pour comparer cet élément avec tous les autres éléments du tableau = O(N)
• Donc complexité globale = O(N) * O(N) = O(N*N) = O(N²)

Espace auxiliaire : O(1) car la seule mémoire supplémentaire utilisée est destinée aux variables temporaires lors de l'échange de deux valeurs dans le tableau. Le tri par sélection n'effectue jamais plus d'échanges O(N) et peut être utile lorsque l'écriture en mémoire est coûteuse.

cout

Avantages de l'algorithme de tri par sélection

• Simple et facile à comprendre.
• Fonctionne bien avec de petits ensembles de données.

Inconvénients de l'algorithme de tri par sélection

• Le tri par sélection a une complexité temporelle de O(n^2) dans le pire des cas et dans le cas moyen.
• Ne fonctionne pas bien sur de grands ensembles de données.
• Ne préserve pas l'ordre relatif des éléments avec des clés égales, ce qui signifie qu'il n'est pas stable.

Foire aux questions sur le tri par sélection

T1. L’algorithme de tri par sélection est-il stable ?

L'implémentation par défaut de l'algorithme de tri par sélection est instable . Cependant, il peut être rendu stable. Veuillez consulter le stable Sélection Tri pour plus de détails.

Q2. L’algorithme de tri par sélection est-il en place ?

Oui, l'algorithme de tri par sélection est un algorithme sur place, car il ne nécessite pas d'espace supplémentaire.