Tri à bulles

1. Algorithme de tri à bulles
2. Exemple d’algorithme de tri à bulles
3. Implémentation de l’algorithme de tri à bulles
4. Complexité de l’algorithme de tri à bulles

Le tri à bulles est un algorithme de tri simple. Il fonctionne par comparaison répétée d’éléments adjacents et en les échangeant s’ils sont dans le mauvais ordre. Les comparaisons répétées font apparaître l’élément le plus petit/le plus grand vers la fin du tableau, d’où le nom de tri à bulles. Bien qu’il soit inefficace, il représente toujours la base des algorithmes de tri.

Algorithme de tri à bulles

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

L’étape 1 de l’algorithme ci-dessus est également appelée une passe. Pour trier un tableau de taille n, n-1 passes sont nécessaires.

Exemple d’algorithme de tri à bulles

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

• Premier passage :

• Deuxième passage :

• Troisième passage :

• Quatrième passage :

Nous obtenons le tableau trié après la quatrième passe - (1 2 3 4 5)

Implémentation de l’algorithme de tri à bulles

#include <iostream>

using namespace std;
void bubble_sort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
      }
    }
  }
}
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";
  bubble_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 à bulles

Complexité temporelle

• Cas moyen

En moyenne, les comparaisons n-i sont faites dans le cadre du passage de bulles. Donc, s’il y a n passes, alors la complexité temporelle moyenne peut être donnée par

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

La complexité temporelle est donc de l’ordre de 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é.

La complexité temporelle du pire cas est O(n²).

• Meilleur cas

Dans le meilleur des cas, le tableau est déjà trié, et seules N comparaisons sont alors nécessaires.

Le meilleur cas de complexité temporelle est O(n).

Complexité spatiale

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