Tri par insertion

1. Algorithme de tri par insertion
2. Exemple de tri par insertion
3. Implémentation de l’algorithme de tri par insertion
4. Complexité de l’algorithme de tri par insertion

Le tri par insertion est un algorithme de tri simple basé sur la comparaison. Dans cet algorithme, nous maintenons deux sous-réseaux : un sous-réseau trié et un sous-réseau non trié. Un élément du sous-réseau non trié trouve sa position correcte dans le sous-réseau trié et y est inséré. Cette méthode est analogue à celle utilisée lorsque quelqu’un trie un jeu de cartes dans sa main. Elle est appelée tri d’insertion car elle fonctionne en insérant un élément à sa position correcte. Cet algorithme est efficace pour les petits ensembles de données mais ne convient pas aux grands ensembles de données.

Algorithme de tri par insertion

Supposons que nous ayons un tableau non trié A[] contenant n éléments. Le premier élément, A[0], est déjà trié et se trouve dans le sous-tableau trié.

Exemple de tri par insertion

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

• Premier tour

Clé : A[1] = 3

• Deuxième tour

Clé : A[2] = 4

• Troisième tour

Clé : A[3] = 2

• Quatrième tour

Clé : A[4] = 1

Implémentation de l’algorithme de tri par insertion

#include <iostream>
using namespace std;

void insertion_sort(int arr[], int n) {
  for (int i = 1; i < n; i++) {
    int j = i;
    while (j > 0 && arr[j - 1] > arr[j]) {
      int key = arr[j];
      arr[j] = arr[j - 1];
      arr[j - 1] = key;
      j--;
    }
  }
}

int main() {
  int n = 5;
  int arr[5] = {5, 3, 4, 2, 1};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  insertion_sort(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 insertion

Complexité temporelle

• Cas moyen

En moyenne, les comparaisons i sont effectuées dans la passe i du tri par insertion. Donc, s’il y a n itérations, alors la complexité temporelle moyenne peut être donnée ci-dessous.

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

La complexité temporelle est donc de l’ordre du [Big Theta] : O(n²).

• Pire cas

Le cas le plus défavorable se produit lorsque le tableau est trié à l’envers, et que le nombre maximum de comparaisons et d’échanges doit être effectué.

Le pire cas de complexité temporelle est le [Big O] : O(n²).

• Meilleur cas

Dans le meilleur des cas, le tableau est déjà trié, et seule la boucle extérieure est exécutée n fois.

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

Complexité spatiale

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