Résumé complet : Tri simple (échange, sélection)

Tri par échange (bulles)

Tri_{bulles}(n) = O(n^2)

Comparaison et échange successifs

Définition :

            Tri à bulles : algorithme de tri qui compare les éléments adjacents et les échange s'ils sont dans le mauvais ordre, faisant "remonter" progressivement les éléments plus grands.

Principe :

🔁 Comparer couples adjacents
↔️ Échanger si nécessaire
🔄 Répéter jusqu'à tri complet
📈 Plus grand élément remonte

Complexité :

✅ Meilleur cas : O(n)
❌ Pire cas : O(n²)
📊 Moyen : O(n²)

Tri par sélection

🔍

Sélection : trouver le minimum

🔄

Échange : placer au bon endroit

✅

Itération : pour chaque position

📊

Complexité : O(n²) constante

Étapes du tri par sélection

1️⃣

Trouver le minimum dans le reste

2️⃣

Échanger avec la position actuelle

3️⃣

Répéter pour les positions restantes

Implémentation

🔄

Tri à bulles

🔍

Tri par sélection

🎯

Comparaison des algorithmes

💡

Optimisations possibles

Code des algorithmes

# Tri à bulles
def tri_bulles(L):
    n = len(L)
    for i in range(n):
        for j in range(0, n-i-1):
            if L[j] > L[j+1]:
                L[j], L[j+1] = L[j+1], L[j]
    return L

# Tri par sélection
def tri_selection(L):
    n = len(L)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if L[j] < L[min_idx]:
                min_idx = j
        L[i], L[min_idx] = L[min_idx], L[i]
    return L
        

Comparaison des tris

🔄

Tri à bulles : stable

🔍

Tri sélection : instable

📊

Les deux : O(n²)

Erreurs fréquentes

Erreur 1 :

Bornes incorrectes dans les boucles
for j in range(n-i): # Trop loin!
for j in range(0, n-i-1): # Correct

Erreur 2 :

Confusion entre échange et assignation
L[i] = L[j] # Assignation
L[i], L[j] = L[j], L[i] # Échange

Erreur 3 :

Comparaison avec mauvais opérateur
if L[j] < L[j+1]: # Ordre décroissant
if L[j] > L[j+1]: # Ordre croissant