Tri à bulles récursivement

Harshit Jindal 12 octobre 2023
  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
Tri à bulles récursivement

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.

  • Si la taille du tableau A est de 1, alors le tableau est déjà trié. Donc, revenez.
  • Sinon, effectuez un passage de [tri à bulles](/fr/tutorial/algorithm/bubble-sort/ itératif sur le sous-tableau donné. Il placera le dernier élément à sa position correcte.
  • Utilisez l’appel de récursion pour effectuer à nouveau les étapes ci-dessus sur un sous-réseau plus petit dont la taille est réduite de un.

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 :
(5 3 4 2 1) (3 5 4 2 1) (3 < 5 échangés)
(3 5 4 2 1) (3 4 5 2 1) (4 < 5 échangés)
(3 4 5 2 1) (3 4 2 5 1) (2 < 5 échangés)
(3 4 2 5 1) (3 4 2 1 5) (1 < 5 échangés)
  • Deuxième passage :
(3 4 2 1 5) (3 4 2 1 5)
(3 4 2 1 5) (3 2 4 1 5) (2 < 4 échangés)
(3 2 4 1 5) (3 2 1 4 5) (1 < 4 échangés)
  • Troisième passage :
(3 2 1 4 5) (2 3 1 4 5) (2 < 3 échangés)
(2 3 1 4 5) (2 1 3 4 5) (1 < 3 échangés)
  • Quatrième passage :
(2 1 3 4 5) (1 2 3 4 5) (1 < 2 échangés)

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(n2).

  • 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(n2).

  • 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.

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