Tri par sélection

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

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.

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(n²). 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 = n²

• Pire cas

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

• Meilleur cas

Le meilleur exemple de complexité temporelle est [Big Omega] : O(n²). 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.