Tri par sélection

Harshit Jindal 12 octobre 2023
  1. Algorithme de tri par sélection
  2. Exemple de tri par sélection
  3. Implémentation de l’algorithme de tri par sélection
  4. Complexité de l’algorithme de tri par sélection
Tri par sélection

Le tri par sélection est un algorithme de tri simple. Il fonctionne en divisant le tableau en deux parties : un sous-tableau trié et un sous-tableau non trié. Le tri par sélection trouve le plus petit élément à l’intérieur du sous-réseau non trié et le déplace au dernier index du sous-réseau trié. Il est utilisé lorsque les opérations d’échange sont très coûteuses car, au maximum, seuls n sont nécessaires.

Algorithme de tri par sélection

Supposons que nous ayons un tableau non trié A[] contenant n éléments.

  • Sélectionnez l’index du premier élément du sous-tableau non trié comme index d’élément minimum min.
  • Comparez la valeur à la min avec le reste des éléments et réinitialisez-la à cet élément si un élément plus petit est trouvé.
  • Remplacez l’élément à la min par l’élément du dernier index de sous-réseau trié.
  • Répétez l’étape ci-dessus n-2 fois pour le reste des éléments du sous-réseau non trié.

Exemple de tri par sélection

Supposons que nous ayons le tableau : (5,3,4,2,1,6). Nous allons le trier en utilisant l’algorithme de tri par sélection.

  • Première itération

Élément minimal : A[4] = 1

Échange (A[4], A[0]). Le tableau devient : (1) (3,4,2,5,6)

  • Deuxième tour

Élément minimal : A[3] = 2

Échange (A[3], A[1]). Le tableau devient : (1,2) (4,3,5,6)

  • Troisième tour

Élément minimal : A[3] = 3

Échange (A[3], A[2]). Le tableau devient : (1,2,3) (4,5,6)

  • Quatrième tour

Élément minimal : A[3] = 4

Échange (A[3], A[3]). Le tableau devient : (1,2,3,4) (5,6)

  • Cinquième tour

Élément minimal : A[4] = 5

Échange (A[4], A[4]). Le tableau devient : (1,2,3,4,5) (6)

Le dernier élément est déjà trié. Nous obtenons le tableau trié sous la forme : (1,2,3,4,5,6)

Implémentation de l’algorithme de tri par sélection

#include <bits/stdc++.h>
using namespace std;

void selectionSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    // Find the minimum element for index i
    int min = i;
    for (int j = i + 1; j < n; j++)
      if (arr[j] < arr[min]) min = j;
    // Put element in sorted position
    swap(arr[min], arr[i]);
  }
}
int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  selectionSort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complexité de l’algorithme de tri par sélection

Complexité temporelle

  • Cas moyen

En moyenne, les comparaisons n-i sont faites dans le ième passage du tri par insertion. Ainsi, s’il y a des itérations n, la complexité temporelle moyenne peut être donnée ci-dessous :

(n-1) + (n-2) + (n-3) + ... + 1 = n*(n-1)/2

La complexité temporelle est donc de l’ordre de [Big Theta] : O(n2). Elle peut également être calculée en comptant le nombre de boucles. Il y a un total de deux boucles de n itérations rendant la complexité : n*n = n2

  • Pire cas

La complexité temporelle dans le pire des cas est [Big O] : O(n2).

  • Meilleur cas

Le meilleur exemple de complexité temporelle est [Big Omega] : O(n2). Elle est identique à la complexité temporelle du pire cas.

Complexité spatiale

La complexité spatiale pour l’algorithme de tri de sélection est O(1) car aucune mémoire supplémentaire autre qu’une variable temporaire n’est nécessaire.

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Article connexe - Sort Algorithm