Bubble Sort expliqué simplement : L’algorithme décrypté avec une équipe de foot ⚽

Développement web
Algorithmie Programmation
Tim
February 17th, 2025
image description

Tri à bulles (Bubble Sort) : Comprendre l'algorithme avec une équipe de foot ⚽

En tant qu'autodidacte, je reprends les algorithmes depuis le début, et je documente cela, pour moi mais aussi pour ceux qui seraient intéressés. Aujourd'hui, plongeons dans le tri à bulles (Bubble Sort) !

🎯 Introduction

Imaginez que vous soyez l'entraîneur d'une équipe de foot à 7 joueurs et que vous deviez les aligner dans l'ordre de leur numéro de maillot pour une photo d'équipe. Vos joueurs sont éparpillés et vous devez les réorganiser. Le tri à bulles tire son nom de la façon dont les éléments "remontent" dans la liste, comme des bulles dans l'eau !

Principe de base

L'objectif est simple : ranger les joueurs du plus petit au plus grand numéro. Voici comment procéder :

  1. Vous commencez par le premier joueur

  2. Vous le comparez avec son voisin de droite

  3. Si son numéro est plus grand, ils échangent leur place

  4. Vous continuez ainsi jusqu'au bout de la ligne

  5. Vous recommencez depuis le début jusqu'à ce que tout soit ordonné

💻 Première implémentation

Voici une première version du code, simple mais fonctionnelle :

javascript 
export default function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n - 1; j++) {
// Si le joueur actuel a un numéro plus grand que son voisin
            if (arr[j] > arr[j + 1]) {
// On les échange de place
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

1. Détection précoce du tri complet

Première amélioration : si pendant un tour complet aucun joueur n'a bougé, c'est que l'équipe est déjà bien alignée !

javascript 
export default function bubbleSort(arr) {
    const n = arr.length;

    for (let i = 0; i < n; i++) {
        let swapped = false;// Notre indicateur d'échange

// Notez le n - i - 1 : on sait que les i derniers éléments sont déjà triés !
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }

// Si aucun échange n'a eu lieu, c'est que tout est trié
        if (!swapped) break;
    }
    return arr;
}

2. Optimisation de la zone de tri

Une autre amélioration : à chaque passage, le plus grand numéro "remonte" à sa position finale. Nous n'avons donc plus besoin de vérifier cette partie déjà triée lors des passages suivants (d'où le n - i - 1 dans la boucle interne).

📊 Visualisation

Pour mieux comprendre, prenons un exemple avec les numéros [5, 1, 4, 2, 8] :

markdown 
Tour 1 : [5, 1, 4, 2, 8] → [1, 5, 4, 2, 8] → [1, 4, 5, 2, 8] → [1, 4, 2, 5, 8]
Tour 2 : [1, 4, 2, 5, 8] → [1, 2, 4, 5, 8]
Tour 3 : [1, 2, 4, 5, 8] → Terminé !

⚖️ Performances et cas d'utilisation

Points forts

  • Simple à comprendre et à implémenter

  • Stable (préserve l'ordre relatif des éléments égaux)

  • Efficace pour les petits tableaux

  • Peu de mémoire supplémentaire requise (tri en place)

Points faibles

  • Complexité quadratique O(n²) dans le pire et le cas moyen

  • Inefficace sur de grandes quantités de données

  • Nombre élevé d'échanges même pour des tableaux presque triés

🎓 Applications pédagogiques

Le tri à bulles est excellent pour :

  • Introduire les concepts de base du tri

  • Comprendre les notions de complexité algorithmique

  • S'exercer à l'optimisation d'algorithmes

  • Visualiser concrètement le processus de tri

🧪 Implémentation en Python

Pour bien comprendre comment fonctionne notre tri à bulles en pratique, et si vous connaissez un minimum le langage Python, voici une version plus détaillée avec des tests unitaires et des messages de débogage. Cette version est particulièrement utile pour l'apprentissage, car elle montre chaque échange en temps réel :

python 
import unittest
from random import shuffle

def bubble_sort(arr):
    n = len(arr)
    
    # Optimisation : sortie rapide pour les listes vides ou à un élément
    if n <= 1:
        return arr
    
    for i in range(n):
        swapped = False
        # On parcourt jusqu'à n-i-1 car les i derniers éléments sont déjà triés
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                # Échange des joueurs
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
                # Affichage pédagogique des échanges
                print(f'{arr[j]} <=> {arr[j+1]}')
        
        print(f'Tour : {i + 1}')
        
        # Optimisation : arrêt si aucun échange n'a été nécessaire
        if not swapped:
            break
            
    return arr

# Tests unitaires pour vérifier notre implémentation
class TestBubbleSort(unittest.TestCase):
    def test_bubble_sort(self):
        players = [1, 2, 3, 4, 5, 6, 7]
        shuffled_players = players[:]
        shuffle(shuffled_players)
        
        sorted_players = bubble_sort(shuffled_players)
        self.assertEqual(sorted_players, sorted(players))

if __name__ == '__main__':
    # Exemple avec une équipe de 7 joueurs
    players = [1, 2, 3, 4, 5, 6, 7]
    shuffle(players)
    print(f'Équipe non ordonnée : {players}')
    
    # Tri de l'équipe
    sorted_team = bubble_sort(players)
    print(f'Équipe ordonnée : {sorted_team}')
    
    # Lancement des tests unitaires
    unittest.main()

🔍 Points clés de cette implémentation

  1. Optimisations intégrées :

    • Détection des listes déjà triées avec swapped

    • Sortie rapide pour les listes vides ou à un élément

    • Réduction de la zone à trier à chaque passage (n - i - 1)

  2. Débogage visuel :

    • Affichage de chaque échange de joueurs

    • Suivi du progrès tour par tour

    • Visualisation de l'état initial et final

  3. Tests unitaires :

    • Vérification automatique du bon fonctionnement

    • Test avec une équipe complète

    • Comparaison avec la fonction sorted() de Python

📝 Exemple d'exécution

Voici ce que vous pourriez voir lors de l'exécution :

python 
Équipe non ordonnée : [5, 2, 7, 1, 4, 3, 6]
2 <=> 5
1 <=> 7
3 <=> 4
Tour : 1
2 <=> 7
1 <=> 4
3 <=> 6
Tour : 2
2 <=> 4
1 <=> 3
Tour : 3
1 <=> 2
Tour : 4
Équipe ordonnée : [1, 2, 3, 4, 5, 6, 7]

🎭 Conclusion : Premier tacle réussi sur les algorithmes !

En tant qu'autodidacte, le tri à bulles a été mon premier "tacle" dans le monde des algorithmes, et je suis ravi de partager cette expérience avec vous. Comme un joueur qui apprend d'abord les bases avant de tenter des gestes techniques plus complexes, j'ai choisi de commencer par cet algorithme simple mais instructif.

🎓 Ce que j'ai appris

  • La visualisation est clé : transformer un concept abstrait en équipe de foot m'a aidé à mieux comprendre

  • L'optimisation n'est pas réservée aux experts : même un débutant peut améliorer son code pas à pas

  • Les tests sont nos amis : ils nous donnent confiance dans notre code

📚 Mon prochain match

Ce premier algorithme n'est que le début. Dans les prochains articles, nous explorerons ensemble des algorithmes plus avancés, toujours avec cette approche concrète et accessible.

💡 À suivre...

Restez à l'écoute pour découvrir :

  • Le tri fusion (Merge Sort)

  • Le tri rapide (Quick Sort)

  • Et d'autres algorithmes fondamentaux !

🤝 Un dernier mot

Cette plongée dans le tri à bulles marque le coup d'envoi de ma série sur les algorithmes. Comme un joueur qui progresse match après match, je compte bien continuer à explorer et partager mes apprentissages avec vous. Rendez-vous dans le prochain article pour tacler un nouvel algorithme ensemble !