Triage à bulles

5.1 Définition du triage à bulles

Le triage à bulles (Bubble Sort) est un algorithme de triage simple qui parcourt à plusieurs reprises une liste, compare des éléments voisins et les échange s'ils sont dans le mauvais ordre. Ce processus continue jusqu'à ce que la liste soit entièrement triée.

Principe de fonctionnement :

1. L'algorithme parcourt la liste et compare chaque paire d'éléments voisins.
2. Si les éléments sont dans le mauvais ordre (le premier est plus grand que le second pour un tri croissant) — ils sont échangés.
3. Ce processus se répète pour toutes les paires d'éléments de la liste.
4. Après chaque passage complet, l'élément le plus grand "remonte" à sa place (comme une bulle à la surface de l'eau), et donc il n'est plus impliqué dans les passages suivants.
5. Le processus se répète jusqu'à ce que la liste soit triée.

Complexité temporelle et spatiale du triage à bulles

Complexité temporelle :

• Dans le pire des cas : O(n^2) — cela se produit lorsque les éléments sont initialement disposés dans l'ordre inverse.
• En moyenne : O(n^2) — cela se produit pour une disposition aléatoire des éléments.
• Dans le meilleur des cas : O(n) — cela se produit lorsque les éléments sont déjà triés (l'algorithme peut être optimisé pour ce cas en ajoutant une vérification pour savoir si un échange a eu lieu lors du passage).

Complexité spatiale :

O(1) — car l'algorithme utilise une quantité constante de mémoire supplémentaire (seulement quelques variables pour stocker des valeurs temporaires).

5.2 Implémentation de l'algorithme

L'algorithme de triage à bulles est le plus simple et le plus primitif des algorithmes de tri d'une liste/tableau d'éléments. Il compare simplement les éléments par paires et les échange si nécessaire.

Version 1 :

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1):
        if array[j] > array[j + 1]:
            array[j], array[j + 1] = array[j + 1], array[j]  # Échange des éléments

print("Tableau trié:", array)
# Résultat : Tableau trié: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

La boucle interne (en vert) compare l'élément avec son voisin de droite. Et si nécessaire, échange les éléments.

Version 2 :

On peut immédiatement ajouter une optimisation à notre algorithme : après le premier passage de l'algorithme, l'élément le plus grand se retrouve à l'extrême droite, donc il n'est plus nécessaire de le prendre en compte lors du cycle suivant.

Après la deuxième itération, il y aura déjà 2 éléments maximum à droite, donc la boucle interne peut se faire jusqu'à n - 1 - i. Où i est le nombre d'itérations effectuées par la boucle externe.

La nouvelle version sera comme suit :

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1 - i):
        if array[j] > array[j + 1]:
            array[j], array[j + 1] = array[j + 1], array[j]  # Échange des éléments

print("Tableau trié:", array)
# Résultat : Tableau trié: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

Version 3 :

De plus, le tableau peut déjà être presque trié. On peut donc ajouter une optimisation : si la boucle interne a parcouru tous les éléments mais n'a effectué aucun échange, alors le tri est terminé.

Dans cette version, on utilise une variable swapped qui suit s'il y a eu un échange d'éléments lors du dernier passage. Si après le passage dans le tableau aucun échange n'a eu lieu, cela signifie que le tableau est déjà trié, et poursuivre les itérations est inutile — elles n'amélioreront pas le tri. Ainsi, la variable swapped permet d'accélérer considérablement l'algorithme sur les tableaux presque triés, en terminant son exécution prématurément.

Implémentation du triage à bulles en Python :

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        swapped = False  # Optimisation : vérification s'il y a eu échange
        for j in range(0, n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]  # Échange des éléments
                swapped = True
        if not swapped:
            break  # Si aucun échange, le tableau est déjà trié
    return array

# Exemple d'utilisation :
array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = bubble_sort(array)
print("Tableau trié :", sorted_array)
# Résultat : Tableau trié: [11, 12, 22, 25, 34, 64, 90]