Algorithmes de tri

Définitions fondamentales

Mot trié

Un mot est dit trié (ou classé, ordonné, monotone) lorsqu'il est croissant ou décroissant relativement à la relation d'ordre total définie sur l'alphabet.

Permutation, recomposition, tri, classement

• Une permutation p sur {0, ..., n-1} est une bijection.
• La recomposition de x selon p est ⟨x[p(k)]⟩ pour 0 ≤ k < n.
• Un tri est une recomposition triée. Un classement est la permutation qui donne ce tri.

Stabilité

Un tri est stable s'il préserve l'ordre relatif des éléments égaux :
x[j] = x[k] ∧ j < k ⇒ p(j) < p(k)

Vérifier qu'un tableau est trié — en C avec pointeurs

#include <stdbool.h>

bool est_croissant(const int *x, size_t n) {
    if (n <= 1) return true;
    const int *fin = x + n - 1;
    while (x < fin) {
        if (*x > *(x + 1)) return false;
        x++;
    }
    return true;
}

Échange de deux éléments pointés

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

Tri par insertion croissante (Insertion Sort)

Principe

On insère chaque nouvel élément à sa place dans le préfixe déjà trié, en décalant les éléments plus grands vers la droite. Le préfixe déjà traité est toujours trié.

Implémentation C avec pointeurs exclusivement

#include <stddef.h>

// @pre:  x pointe vers un tableau de n éléments
// @post: le tableau est trié en ordre croissant (tri stable)
void tri_insertion(int *x, size_t n) {
    for (size_t i = 1; i < n; i++) {
        int cle = x[i];
        int *prec = x + i - 1;   // pointe vers le dernier du préfixe trié

        // @invariant: x[0..prec-x] trié, x[prec-x+2..i] décalé à droite
        // @variant:   prec - x + 1
        while (prec >= x && *prec > cle) {
            *(prec + 1) = *prec;  // décalage à droite
            prec--;
        }
        *(prec + 1) = cle;        // insertion à sa place
    }
}

Analyse

• Complexité temporelle : Ω(n), O(n²), Θ(n²) en moyenne
• Stable : Oui (condition *prec > cle, non ≥)
• En place : Oui (espace constant)

Version avec sentinelle

Si l'on place d'abord le minimum en première position, on économise le test prec >= x dans la boucle interne :

void tri_insertion_sentinelle(int *x, size_t n) {
    if (n <= 1) return;
    // Placer le minimum en première position (sentinelle)
    int *min = x;
    for (int *p = x + 1; p < x + n; p++)
        if (*p < *min) min = p;
    echanger(x, min);

    for (size_t i = 2; i < n; i++) {
        int cle = x[i];
        int *prec = x + i - 1;
        while (*prec > cle) {     // plus besoin de prec >= x
            *(prec + 1) = *prec;
            prec--;
        }
        *(prec + 1) = cle;
    }
}

Tri par fusion croissante (Merge Sort)

Principe

On divise le tableau en deux moitiés, on trie chacune récursivement, puis on fusionne les deux moitiés triées en un seul tableau trié. C'est l'archétype du paradigme « diviser pour régner ».

Fusion de deux sous-tableaux — avec pointeurs

#include <stdlib.h>
#include <string.h>

// Fusionne x[lo..mid] et x[mid+1..hi] (supposés triés)
static void fusionner(int *x, int *tmp, size_t lo, size_t mid, size_t hi) {
    size_t i = lo, j = mid + 1, k = lo;

    // Copie dans le tableau temporaire
    memcpy(tmp + lo, x + lo, (hi - lo + 1) * sizeof(int));

    // Fusion des deux moitiés
    while (i <= mid && j <= hi) {
        if (tmp[i] <= tmp[j]) x[k++] = tmp[i++];
        else                  x[k++] = tmp[j++];
    }
    while (i <= mid) x[k++] = tmp[i++];
    while (j <= hi)  x[k++] = tmp[j++];
}

static void tri_fusion_r(int *x, int *tmp, size_t lo, size_t hi) {
    if (lo >= hi) return;
    size_t mid = lo + (hi - lo) / 2;
    tri_fusion_r(x, tmp, lo, mid);
    tri_fusion_r(x, tmp, mid + 1, hi);
    fusionner(x, tmp, lo, mid, hi);
}

// @pre:  x pointe vers un tableau de n éléments
// @post: le tableau est trié en ordre croissant (tri stable)
void tri_fusion(int *x, size_t n) {
    if (n <= 1) return;
    int *tmp = malloc(n * sizeof(int));
    if (tmp == NULL) return;
    tri_fusion_r(x, tmp, 0, n - 1);
    free(tmp);
}

Analyse

• Niveaux de récursion : ⌈lg n⌉
• Comparaisons : Θ(n lg n) dans tous les cas
• Transferts : Θ(n lg n) (copies vers/depuis le tampon)
• Complexité temporelle : Θ(n lg n) — optimal pour les tris par comparaisons
• Complexité spatiale : Θ(n) (tableau temporaire)
• Stable : Oui (condition ≤ dans la fusion, pas <)

Version itérative (bottom-up, sans récursivité)

void tri_fusion_iteratif(int *x, size_t n) {
    int *tmp = malloc(n * sizeof(int));
    if (!tmp) return;

    // @invariant: les facteurs de pas 'pas' sont triés
    // @variant:   n - pas
    for (size_t pas = 1; pas < n; pas *= 2) {
        for (size_t lo = 0; lo < n - pas; lo += 2 * pas) {
            size_t mid = lo + pas - 1;
            size_t hi = (lo + 2 * pas - 1 < n) ? lo + 2 * pas - 1 : n - 1;
            fusionner(x, tmp, lo, mid, hi);
        }
    }
    free(tmp);
}

Tri par sélection du minimum (Selection Sort)

Principe

À chaque itération, on sélectionne le minimum du suffixe non encore trié et on l'échange avec la première position de ce suffixe. La zone triée grandit d'un élément à gauche à chaque tour.

Implémentation C avec pointeurs exclusivement

#include <stddef.h>

// @pre:  x pointe vers un tableau de n éléments
// @post: le tableau est trié en ordre croissant (tri instable)
void tri_selection(int *x, size_t n) {
    int *fin = x + n;                    // adresse après le dernier élément

    // @invariant: x[0..cur-x-1] est trié et ≤ x[cur-x..n-1]
    // @variant:   fin - cur
    for (int *cur = x; cur < fin - 1; cur++) {
        // Recherche du minimum dans le suffixe
        int *min = cur;
        for (int *p = cur + 1; p < fin; p++) {
            if (*p < *min) min = p;
        }
        // Échange si nécessaire
        if (min != cur) {
            int tmp = *cur;
            *cur = *min;
            *min = tmp;
        }
    }
}

Analyse

• Comparaisons : toujours n(n−1)/2, soit Θ(n²) — indépendant des données
• Échanges : au plus n−1 (linéaire, contraste avec l'insertion)
• Complexité temporelle : Θ(n²) dans tous les cas
• Stable : Non. Contre-exemple : ⟨b₁, b₂, a⟩ avec a < b donne ⟨a, b₂, b₁⟩
• En place : Oui

Comparaison Sélection vs Insertion

qsort

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

Tri instable base sur le tri rapide de Hoare.

Fonctions de copie

void *memcpy(void *dest, const void *src, size_t n);
void *memmove(void *dest, const void *src, size_t n);

Tri à bulles (Bubble Sort)

Principe

On parcourt le tableau en comparant chaque paire d'éléments adjacents. Si deux éléments ne sont pas dans le bon ordre, on les échange. Après chaque passe complète, le plus grand élément restant « remonte » (comme une bulle) à sa position définitive.

Implémentation C avec pointeurs

#include <stddef.h>
#include <stdbool.h>

// @pre:  x pointe vers un tableau de n éléments
// @post: le tableau est trié en ordre croissant (tri stable)
void tri_bulles(int *x, size_t n) {
    if (n <= 1) return;
    bool echange;

    // @invariant: après k passes, les k derniers éléments sont triés
    // @variant:   i (décroît de n-1 à 1)
    for (size_t i = n - 1; i > 0; i--) {
        echange = false;
        int *cur = x;
        int *fin = x + i;
        while (cur < fin) {
            if (*cur > *(cur + 1)) {
                int tmp = *cur;
                *cur = *(cur + 1);
                *(cur + 1) = tmp;
                echange = true;
            }
            cur++;
        }
        if (!echange) break;  // aucune permutation → déjà trié
    }
}

Analyse

• Complexité temporelle : Ω(n), O(n²), Θ(n²) en moyenne
• Stable : Oui (échange uniquement si *cur > *(cur+1))
• En place : Oui
• Remarque : La variable echange permet une sortie anticipée si une passe n'effectue aucun échange.

Tri cocktail (Cocktail Shaker Sort)

Principe

Variante du tri à bulles qui alterne les directions de parcours :

1. Une passe gauche → droite : les grands éléments remontent (comme le tri à bulles)
2. Une passe droite → gauche : les petits éléments descendent

Les extrémités déjà triées sont exclues des passes suivantes. Ce balayage bidirectionnel évoque l'agitation d'un shaker.

Avantage sur le tri à bulles

Un petit élément situé en fin de tableau ne remonte que d'une position par passe dans le tri à bulles classique. Avec le cocktail, la passe retour le fait redescendre immédiatement.

Implémentation C avec pointeurs

#include <stddef.h>
#include <stdbool.h>

// @pre:  x pointe vers un tableau de n éléments
// @post: le tableau est trié en ordre croissant (tri stable)
void tri_cocktail(int *x, size_t n) {
    if (n <= 1) return;
    bool echange = true;
    int *debut = x;              // début de la zone non triée
    int *fin = x + n - 1;        // fin de la zone non triée

    while (echange && debut < fin) {
        echange = false;

        // --- Passe gauche → droite (les grands remontent) ---
        for (int *p = debut; p < fin; p++) {
            if (*p > *(p + 1)) {
                int tmp = *p;
                *p = *(p + 1);
                *(p + 1) = tmp;
                echange = true;
            }
        }
        fin--;  // le plus grand de cette passe est en place

        if (!echange) break;

        // --- Passe droite → gauche (les petits descendent) ---
        for (int *p = fin; p > debut; p--) {
            if (*p < *(p - 1)) {
                int tmp = *p;
                *p = *(p - 1);
                *(p - 1) = tmp;
                echange = true;
            }
        }
        debut++;  // le plus petit de cette passe est en place
    }
}

Analyse

• Meilleur cas : n−1 comparaisons, 0 échange (tableau déjà trié)
• Pire cas : Θ(n²) comparaisons et échanges
• Stable : Oui
• En place : Oui

Comparaison Cocktail vs Bulles

Tri du drapeau néerlandais (Dutch National Flag)

Contexte

Proposé par Edsger W. Dijkstra, ce problème doit son nom aux trois bandes du drapeau des Pays-Bas. Il s'agit de trier un tableau ne contenant que c valeurs distinctes (typiquement 0, 1, 2 pour les trois couleurs) en un seul parcours, sans utiliser de mémoire auxiliaire.

Cas c = 3 — Trois couleurs

L'algorithme maintient trois pointeurs :

• lo : frontière de la zone des 0 (tout ce qui est avant est 0)
• mid : élément en cours d'examen
• hi : frontière de la zone des 2 (tout ce qui est après est 2)

La zone entre lo et mid-1 contient les 1 (déjà examinés et classés).

#include <stddef.h>

// Trie un tableau ne contenant QUE les valeurs 0, 1, 2
// @pre:  pour tout i, x[i] ∈ {0, 1, 2}
// @post: x est trié en ordre croissant
void drapeau_neerlandais_3(int *x, size_t n) {
    int *lo = x;           // frontière des 0 (tout ce qui est < lo est 0)
    int *mid = x;          // élément courant
    int *hi = x + n - 1;   // frontière des 2 (tout ce qui est > hi est 2)

    // @invariant: [x, lo)   = 0
    //             [lo, mid) = 1
    //             [mid, hi] = zone non examinée
    //             (hi, x+n) = 2
    // @variant:   hi - mid + 1
    while (mid <= hi) {
        switch (*mid) {
        case 0:
            // échanger avec lo, les deux avancent
            { int t = *lo; *lo = *mid; *mid = t; }
            lo++;
            mid++;
            break;
        case 1:
            // déjà à sa place
            mid++;
            break;
        case 2:
            // échanger avec hi, seul hi recule
            // (ne pas avancer mid : la nouvelle valeur doit être examinée)
            { int t = *mid; *mid = *hi; *hi = t; }
            hi--;
            break;
        }
    }
}

Trace d'exécution (exemple)

Tableau initial : [2, 0, 2, 1, 1, 0]

Analyse pour c = 3

• Comparaisons : exactement n (un switch par élément)
• Échanges : au plus n (chaque élément est échangé au plus une fois)
• Complexité temporelle : Θ(n)
• Complexité spatiale : O(1)
• Stable : Non (les échanges avec hi brisent la stabilité)

Généralisation à c quelconque

Pour c valeurs quelconques, on peut trier en appliquant récursivement le partitionnement :

// Trie un tableau de n entiers ∈ [0, c-1]
void drapeau_neerlandais(int *x, size_t n, int c) {
    if (c <= 1 || n <= 1) return;

    // Partition : 0 à gauche, {1..c-1} à droite
    int *lo = x, *hi = x + n - 1;
    while (lo <= hi) {
        if (*lo == 0) lo++;
        else { int t = *lo; *lo = *hi; *hi = t; hi--; }
    }
    // Récurrence sur le suffixe pour les couleurs 1..c-1
    if (lo < x + n)
        drapeau_neerlandais(lo, x + n - lo, c - 1);
}

• Complexité : Θ(c·n) comparaisons et échanges
• Efficace quand c ≪ n ; si c est grand, préférer un tri Θ(n lg n).