Tri à bulles récursivement

1. Algorithme récursif de tri à bulles
2. Exemple d’algorithme récursif de tri à base de bulles
3. Implémentation d’algorithme récursif 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 récursif de tri à bulles

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

Exemple d’algorithme récursif de tri à base de 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 d’algorithme récursif de tri à bulles

#include <bits/stdc++.h>
using namespace std;
void bubbleSort(int arr[], int n) {
  if (n == 1) return;

  for (int i = 0; i < n - 1; i++) {
    if (arr[i] > arr[i + 1]) {
      swap(arr[i], arr[i + 1]);
    }
  }

  bubbleSort(arr, n - 1);
}
int main() {
  int n = 8;
  int arr[8] = {9, 8, 3, 7, 5, 6, 4, 1};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  bubbleSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  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 de O(n) en raison des appels récursifs stockés dans la pile.