17. Analyse de l'Efficacité du Bubble Sort

Comme nous l'avons vu, le Bubble Sort utilise des boucles imbriquées, ce qui indique généralement une complexité temporelle quadratique.

Analyse de la Complexité Temporelle

• Pire Cas : O(N²)
  • Se produit lorsque le tableau est trié dans l'ordre inverse. La boucle interne doit effectuer un maximum de comparaisons à chaque passage.
• Meilleur Cas : O(N)
  • Se produit si le tableau est déjà trié. Si nous ajoutons un drapeau pour détecter si des échanges se sont produits lors d'un passage, nous pouvons nous arrêter tôt après le premier passage O(N), atteignant un temps linéaire.
• Cas Moyen : O(N²)

Complexité Spatiale

• Complexité Spatiale : Espace auxiliaire O(1).
  • Le Bubble Sort est un algorithme de tri en place (in-place), ce qui signifie qu'il ne nécessite qu'une quantité minimale et constante de mémoire supplémentaire (généralement juste pour les variables temporaires utilisées dans l'échange).