Algorithmes de tri élémentaires (Tri sélection, tri par insertion et tri à bulles)

Algorithmes de tri élémentaires

Définition — Problème du tri Étant donné un tableau T[0..n-1] de n éléments comparables, trier consiste à réorganiser les éléments de façon à obtenir T[0] ≤ T[1] ≤ … ≤ T[n-1].

Les trois algorithmes présentés ici sont dits élémentaires : simples à comprendre et à implémenter, mais de complexité O(n²) dans le pire cas — à utiliser sur de petits tableaux ou comme base pédagogique.

Algorithme	Idée principale	Meilleur	Pire	Espace	Stable
Tri à bulles	Échanges d'adjacents répétés	O(n)	O(n²)	O(1)	✅
Tri par insertion	Insérer chaque élément à sa place	O(n)	O(n²)	O(1)	✅
Tri par sélection	Sélectionner le minimum et l'échanger	O(n²)	O(n²)	O(1)	❌

1. Tri à bulles — Bubble Sort

Principe On parcourt le tableau en comparant chaque paire d'éléments adjacents. Si deux voisins sont dans le mauvais ordre, on les échange. On répète ces passes jusqu'à ce que le tableau soit trié.

À chaque passe complète, le plus grand élément non trié « remonte » (comme une bulle) à sa position finale.

Trace — tableau [5, 3, 8, 1, 2]

Passe	État du tableau	Échanges	Élément placé
Départ	`[5, 3, 8, 1, 2]`	—	—
Passe 1	`[3, 5, 1, 2, 8]`	3 échanges	8 en pos. 4
Passe 2	`[3, 1, 2, 5, 8]`	2 échanges	5 en pos. 3
Passe 3	`[1, 2, 3, 5, 8]`	2 échanges	3 en pos. 2
Passe 4	`[1, 2, 3, 5, 8]`	0 échanges	Tableau trié ✓

Pseudocode

Procédure triBulles(T[0..n-1]) :
    Pour i de n-1 à 1 (décroissant) :
        echange ← Faux
        Pour j de 0 à i-1 :
            Si T[j] > T[j+1] alors
                échanger T[j] et T[j+1]
                echange ← Vrai
        Si echange = Faux alors sortir   ← optimisation : déjà trié

def tri_bulles(T):
    n = len(T)
    for i in range(n - 1, 0, -1):      # i : limite de la zone non triée
        echange = False
        for j in range(i):
            if T[j] > T[j + 1]:
                T[j], T[j + 1] = T[j + 1], T[j]   # échange Pythonique
                echange = True
        if not echange:                 # optimisation : déjà trié
            break


# Test avec affichage des passes
def tri_bulles_verbose(T):
    n = len(T)
    passe = 1
    for i in range(n - 1, 0, -1):
        echange = False
        for j in range(i):
            if T[j] > T[j + 1]:
                T[j], T[j + 1] = T[j + 1], T[j]
                echange = True
        print(f"Passe {passe} : {T}")
        passe += 1
        if not echange:
            print("  → Aucun échange : tableau trié !")
            break


T = [5, 3, 8, 1, 2]
print("Départ :", T)
tri_bulles_verbose(T)
print("Résultat :", T)

#include <stdio.h>

void echanger(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void tri_bulles(int T[], int n) {
    for (int i = n - 1; i > 0; i--) {
        int echange = 0;
        for (int j = 0; j < i; j++) {
            if (T[j] > T[j + 1]) {
                echanger(&T[j], &T[j + 1]);
                echange = 1;
            }
        }
        if (!echange) break;   /* déjà trié */
    }
}

void afficher(int T[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", T[i]);
    printf("\n");
}

int main() {
    int T[] = {5, 3, 8, 1, 2};
    int n = 5;
    printf("Avant : "); afficher(T, n);
    tri_bulles(T, n);
    printf("Après : "); afficher(T, n);
    return 0;
}

import java.util.Arrays;

public class TriBulles {

    static void triBulles(int[] T) {
        int n = T.length;
        for (int i = n - 1; i > 0; i--) {
            boolean echange = false;
            for (int j = 0; j < i; j++) {
                if (T[j] > T[j + 1]) {
                    int tmp = T[j];
                    T[j]     = T[j + 1];
                    T[j + 1] = tmp;
                    echange = true;
                }
            }
            if (!echange) break;
        }
    }

    public static void main(String[] args) {
        int[] T = {5, 3, 8, 1, 2};
        System.out.println("Avant : " + Arrays.toString(T));
        triBulles(T);
        System.out.println("Après : " + Arrays.toString(T));
    }
}

Sortie

Départ : [5, 3, 8, 1, 2]
Passe 1 : [3, 5, 1, 2, 8]
Passe 2 : [3, 1, 2, 5, 8]
Passe 3 : [1, 2, 3, 5, 8]
Passe 4 : [1, 2, 3, 5, 8]
  → Aucun échange : tableau trié !
Résultat : [1, 2, 3, 5, 8]

Optimisation — drapeau d'échange Sans optimisation, le tri à bulles effectue toujours n(n-1)/2 comparaisons. En ajoutant un drapeau echange, si aucun échange n'est effectué lors d'une passe, le tableau est déjà trié et on peut s'arrêter. Cela donne une complexité O(n) dans le meilleur cas (tableau déjà trié).

2. Tri par insertion — Insertion Sort

Principe On maintient une partie gauche triée du tableau. À chaque étape, on prend le premier élément de la partie non triée (clé) et on l'insère à sa bonne position dans la partie gauche en décalant les éléments plus grands vers la droite.

Analogie : trier des cartes à jouer dans la main — on prend une carte et on la glisse à sa place parmi les cartes déjà triées.

Trace — tableau [5, 3, 8, 1, 2]

i	Clé	Partie triée avant	État après insertion
—	—	`[5]`	`[5, 3, 8, 1, 2]`
1	3	`[5]`	`[3, 5, 8, 1, 2]`
2	8	`[3, 5]`	`[3, 5, 8, 1, 2]`
3	1	`[3, 5, 8]`	`[1, 3, 5, 8, 2]`
4	2	`[1, 3, 5, 8]`	`[1, 2, 3, 5, 8]`

Pseudocode

Procédure triInsertion(T[0..n-1]) :
    Pour i de 1 à n-1 :
        clé ← T[i]
        j ← i - 1
        Tant que j ≥ 0 ET T[j] > clé :
            T[j+1] ← T[j]      ← décaler vers la droite
            j ← j - 1
        T[j+1] ← clé           ← insérer la clé à sa place

def tri_insertion(T):
    for i in range(1, len(T)):
        cle = T[i]          # élément à insérer
        j   = i - 1
        # Décaler vers la droite tous les éléments plus grands que clé
        while j >= 0 and T[j] > cle:
            T[j + 1] = T[j]
            j -= 1
        T[j + 1] = cle      # insérer à la bonne position


# Version avec affichage étape par étape
def tri_insertion_verbose(T):
    for i in range(1, len(T)):
        cle = T[i]
        j   = i - 1
        while j >= 0 and T[j] > cle:
            T[j + 1] = T[j]
            j -= 1
        T[j + 1] = cle
        print(f"i={i}, clé={cle} → {T}")


T = [5, 3, 8, 1, 2]
print("Départ :", T)
tri_insertion_verbose(T)
print("Résultat :", T)

#include <stdio.h>

void tri_insertion(int T[], int n) {
    for (int i = 1; i < n; i++) {
        int cle = T[i];
        int j   = i - 1;
        /* Décaler vers la droite les éléments plus grands que clé */
        while (j >= 0 && T[j] > cle) {
            T[j + 1] = T[j];
            j--;
        }
        T[j + 1] = cle;
    }
}

void afficher(int T[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", T[i]);
    printf("\n");
}

int main() {
    int T[] = {5, 3, 8, 1, 2};
    int n = 5;
    printf("Avant : "); afficher(T, n);
    tri_insertion(T, n);
    printf("Après : "); afficher(T, n);
    return 0;
}

import java.util.Arrays;

public class TriInsertion {

    static void triInsertion(int[] T) {
        for (int i = 1; i < T.length; i++) {
            int cle = T[i];
            int j   = i - 1;
            while (j >= 0 && T[j] > cle) {
                T[j + 1] = T[j];
                j--;
            }
            T[j + 1] = cle;
        }
    }

    public static void main(String[] args) {
        int[] T = {5, 3, 8, 1, 2};
        System.out.println("Avant : " + Arrays.toString(T));
        triInsertion(T);
        System.out.println("Après : " + Arrays.toString(T));
    }
}

Sortie

Départ : [5, 3, 8, 1, 2]
i=1, clé=3 → [3, 5, 8, 1, 2]
i=2, clé=8 → [3, 5, 8, 1, 2]
i=3, clé=1 → [1, 3, 5, 8, 2]
i=4, clé=2 → [1, 2, 3, 5, 8]
Résultat : [1, 2, 3, 5, 8]

Cas d'utilisation — quasi-trié Le tri par insertion est très efficace sur les tableaux déjà presque triés : complexité O(n) si chaque élément est à au plus k positions de sa place finale. C'est pourquoi il est utilisé en pratique pour finaliser des tableaux quasi-triés (ex : dans Timsort, l'algorithme utilisé par Python et Java).

3. Tri par sélection — Selection Sort

Principe À chaque itération, on sélectionne le minimum de la partie non triée et on l'échange avec le premier élément de cette partie. Après i itérations, les i premiers éléments sont triés définitivement.

Contrairement aux deux autres algorithmes, le tri par sélection effectue toujours exactement n-1 échanges, quel que soit l'ordre initial.

Trace — tableau [5, 3, 8, 1, 2]

i	Zone non triée	Min trouvé	Échange	État après
0	[5,3,8,1,2]	1 (pos 3)	T[0]↔T[3]	`[1, 3, 8, 5, 2]`
1	[3,8,5,2]	2 (pos 4)	T[1]↔T[4]	`[1, 2, 8, 5, 3]`
2	[8,5,3]	3 (pos 4)	T[2]↔T[4]	`[1, 2, 3, 5, 8]`
3	[5,8]	5 (pos 3)	T[3]=T[3] (déjà place)	`[1, 2, 3, 5, 8]`
4	[8]	—	Dernier élément	`[1, 2, 3, 5, 8]` ✓

Pseudocode

Procédure triSelection(T[0..n-1]) :
    Pour i de 0 à n-2 :
        i_min ← i
        Pour j de i+1 à n-1 :
            Si T[j] < T[i_min] alors
                i_min ← j          ← mémoriser la position du minimum
        Si i_min ≠ i alors
            échanger T[i] et T[i_min]

def tri_selection(T):
    n = len(T)
    for i in range(n - 1):
        i_min = i
        # Trouver la position du minimum dans T[i..n-1]
        for j in range(i + 1, n):
            if T[j] < T[i_min]:
                i_min = j
        # Échanger le minimum avec T[i]
        if i_min != i:
            T[i], T[i_min] = T[i_min], T[i]


# Version avec affichage
def tri_selection_verbose(T):
    n = len(T)
    for i in range(n - 1):
        i_min = i
        for j in range(i + 1, n):
            if T[j] < T[i_min]:
                i_min = j
        if i_min != i:
            print(f"i={i} : min={T[i_min]} trouvé en pos {i_min}, échange T[{i}]↔T[{i_min}]")
            T[i], T[i_min] = T[i_min], T[i]
        else:
            print(f"i={i} : min={T[i]} déjà en place")
        print(f"       → {T}")


T = [5, 3, 8, 1, 2]
print("Départ :", T)
tri_selection_verbose(T)
print("Résultat :", T)

#include <stdio.h>

void tri_selection(int T[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int i_min = i;
        for (int j = i + 1; j < n; j++) {
            if (T[j] < T[i_min])
                i_min = j;
        }
        if (i_min != i) {
            int tmp   = T[i];
            T[i]      = T[i_min];
            T[i_min]  = tmp;
        }
    }
}

void afficher(int T[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", T[i]);
    printf("\n");
}

int main() {
    int T[] = {5, 3, 8, 1, 2};
    int n = 5;
    printf("Avant : "); afficher(T, n);
    tri_selection(T, n);
    printf("Après : "); afficher(T, n);
    return 0;
}

import java.util.Arrays;

public class TriSelection {

    static void triSelection(int[] T) {
        int n = T.length;
        for (int i = 0; i < n - 1; i++) {
            int iMin = i;
            for (int j = i + 1; j < n; j++) {
                if (T[j] < T[iMin])
                    iMin = j;
            }
            if (iMin != i) {
                int tmp  = T[i];
                T[i]     = T[iMin];
                T[iMin]  = tmp;
            }
        }
    }

    public static void main(String[] args) {
        int[] T = {5, 3, 8, 1, 2};
        System.out.println("Avant : " + Arrays.toString(T));
        triSelection(T);
        System.out.println("Après : " + Arrays.toString(T));
    }
}

Sortie

Départ : [5, 3, 8, 1, 2]
i=0 : min=1 trouvé en pos 3, échange T[0]↔T[3]
       → [1, 3, 8, 5, 2]
i=1 : min=2 trouvé en pos 4, échange T[1]↔T[4]
       → [1, 2, 8, 5, 3]
i=2 : min=3 trouvé en pos 4, échange T[2]↔T[4]
       → [1, 2, 3, 5, 8]
i=3 : min=5 déjà en place
       → [1, 2, 3, 5, 8]
Résultat : [1, 2, 3, 5, 8]

Avantage — Nombre d'échanges minimal Le tri par sélection effectue au plus n−1 échanges, quel que soit l'entrée. C'est un avantage si les échanges sont coûteux (ex : objets lourds en mémoire). En revanche, il effectue toujours n(n-1)/2 comparaisons même si le tableau est déjà trié — pas d'optimisation possible pour le meilleur cas.

Tri par sélection — non stable Le tri par sélection n'est pas stable : l'échange peut modifier l'ordre relatif d'éléments de même valeur.
Exemple : [3a, 3b, 1] → après i=0, échange de 3a avec 1 → [1, 3b, 3a] (3b et 3a ont été inversés).

Analyse comparative

Critère	Tri à bulles	Tri par insertion	Tri par sélection
Meilleur cas	O(n) avec drapeau	O(n) quasi-trié	O(n²) toujours
Pire cas	O(n²)	O(n²)	O(n²)
Nb échanges (pire)	O(n²)	O(n²) décalages	O(n) au maximum
Espace	O(1)	O(1)	O(1)
Stable	Oui	Oui	Non
En place	Oui	Oui	Oui
Usage recommandé	Pédagogique	Quasi-trié, petits n	Échanges coûteux

Points clés à retenir

Les trois algorithmes sont en place (O(1) mémoire supplémentaire) et de complexité O(n²) dans le pire cas.
Le tri par insertion est le plus efficace en pratique parmi les trois : O(n) sur tableau quasi-trié et peu de déplacements en moyenne.
Le tri à bulles est le moins performant en général (nombreux échanges), mais reste simple à comprendre.
Le tri par sélection minimise le nombre d'échanges (≤ n−1) mais n'a pas de meilleur cas en O(n).
Pour n > 1000, préférer le tri par fusion O(n log n) ou le tri rapide O(n log n) en moyenne.
En Python, sorted() et list.sort() utilisent Timsort (hybride insertion + fusion) — O(n log n) garanti.

Sortie

// La sortie apparaîtra ici…

Prêt · Ctrl+Entrée pour exécuter

Précédent Introduction et terminologies des algorithmes de tri

Suivant algorithme de tri par fusion

Algorithmes de tri élémentaires (Tri sélection, tri par insertion et tri à bulles)