Optimisation du Tri Rapide pour les petits intervalles

Dans l'algorithme du Tri Rapide (Quick Sort), les derniers niveaux de la récursion traitent une multitude de petits segments. Ces appels génèrent une surcharge importante par rapport à la taille des données traitées. Pour améliorer les performances, on utilise souvent un seuil (généralement 10 à 15 éléments) en dessous duquel on bascule vers un tri par insertion.

// Partitionnement par la méthode du curseur
int partitionner_tableau(int* tab, int gauche, int droite) {
    int milieu = (gauche + droite) / 2;
    // Échange simple pour choisir un pivot médian (logique simplifiée)
    int temp_piv = tab[gauche];
    tab[gauche] = tab[milieu];
    tab[milieu] = temp_piv;

    int pivot_idx = gauche;
    int precedent = gauche;
    int courant = gauche + 1;

    while (courant <= droite) {
        if (tab[courant] < tab[pivot_idx]) {
            precedent++;
            int tmp = tab[precedent];
            tab[precedent] = tab[courant];
            tab[courant] = tmp;
        }
        courant++;
    }

    int final_tmp = tab[precedent];
    tab[precedent] = tab[pivot_idx];
    tab[pivot_idx] = final_tmp;
    
    return precedent;
}

// Tri rapide avec optimisation hybride
void tri_rapide_hybride(int* tab, int debut, int fin) {
    if (debut >= fin) return;

    // Seuil d'optimisation : 10 éléments
    if ((fin - debut + 1) > 10) {
        int pivot = partitionner_tableau(tab, debut, fin);
        tri_rapide_hybride(tab, debut, pivot - 1);
        tri_rapide_hybride(tab, pivot + 1, fin);
    } else {
        // Tri par insertion pour les petits segments
        for (int i = debut + 1; i <= fin; i++) {
            int cible = tab[i];
            int j = i - 1;
            while (j >= debut && tab[j] > cible) {
                tab[j + 1] = tab[j];
                j--;
            }
            tab[j + 1] = cible;
        }
    }
}

Le Tri Rapide non récursif (Approche par Pile)

Bien que le risque de saturation de la pile d'exécution (stack overflow) soit faible avec le tri rapide grâce à sa division logarithmique, l'implémentation itérative est un excellent exerccie de gestion des structures de données. On utilise ici une pile explicite pour stocker les bornes des sous-tableaux à traiter.

void tri_rapide_iteratif(int* tab, int debut, int fin) {
    // Structure de pile supposée définie (Pile st)
    Pile st;
    initialiser_pile(&st);
    
    // Empiler les bornes initiales
    empiler(&st, fin);
    empiler(&st, debut);

    while (!pile_vide(&st)) {
        int gauche = depiler(&st);
        int droite = depiler(&st);

        int pivot = partitionner_tableau(tab, gauche, droite);

        // Traitement du segment droit
        if (pivot + 1 < droite) {
            empiler(&st, droite);
            empiler(&st, pivot + 1);
        }

        // Traitement du segment gauche
        if (gauche < pivot - 1) {
            empiler(&st, pivot - 1);
            empiler(&st, gauche);
        }
    }
    detruire_pile(&st);
}

Tri Fusion Récursif : Division et Conquête

Le Tri Fusion (Merge Sort) nécessite l'usage d'un tableau auxiliaire pour fusionner les séquences triées sans écraser les données en cours de traitement. L'algorithme divise récursivement le tableau en deux jusqu'à obtenir des éléments unitaires, puis remonte en fusionnant.

void fusionner_segments(int* source, int* temporaire, int debut, int fin) {
    if (debut >= fin) return;

    int milieu = (debut + fin) / 2;
    
    fusionner_segments(source, temporaire, debut, milieu);
    fusionner_segments(source, temporaire, milieu + 1, fin);

    int curseur1 = debut, borne1 = milieu;
    int curseur2 = milieu + 1, borne2 = fin;
    int k = debut;

    while (curseur1 <= borne1 && curseur2 <= borne2) {
        if (source[curseur1] <= source[curseur2]) {
            temporaire[k++] = source[curseur1++];
        } else {
            temporaire[k++] = source[curseur2++];
        }
    }

    while (curseur1 <= borne1) temporaire[k++] = source[curseur1++];
    while (curseur2 <= borne2) temporaire[k++] = source[curseur2++];

    // Recopie vers le tableau d'origine
    for (int i = debut; i <= fin; i++) {
        source[i] = temporaire[i];
    }
}

void tri_fusion_principal(int* tab, int n) {
    int* auxiliaire = (int*)malloc(sizeof(int) * n);
    if (auxiliaire == NULL) return;

    fusionner_segments(tab, auxiliaire, 0, n - 1);
    free(auxiliaire);
}

Tri Fusion Itératif : Approche Ascendante

L'implémentation non récursive du tri fusion, également appelée "Bottom-Up", commence par fusionner des segments de taille 1, puis 2, puis 4, et ainsi de suite. Cette méthode est particulièrement stable et évite totalement la récursion.

void tri_fusion_iteratif(int* tab, int n) {
    int* temporaire = (int*)malloc(sizeof(int) * n);
    if (!temporaire) return;

    int pas = 1;
    while (pas < n) {
        for (int i = 0; i < n; i += 2 * pas) {
            int d1 = i, f1 = i + pas - 1;
            int d2 = i + pas, f2 = i + 2 * pas - 1;

            // Gestion des débordements pour les tailles de tableaux non puissances de 2
            if (f1 >= n) f1 = n - 1;
            if (d2 >= n) {
                d2 = n; // Segment 2 vide
                f2 = n - 1;
            }
            if (f2 >= n) f2 = n - 1;

            int k = i;
            int ptr1 = d1, ptr2 = d2;
            while (ptr1 <= f1 && ptr2 <= f2) {
                temporaire[k++] = (tab[ptr1] < tab[ptr2]) ? tab[ptr1++] : tab[ptr2++];
            }

            while (ptr1 <= f1) temporaire[k++] = tab[ptr1++];
            while (ptr2 <= f2) temporaire[k++] = tab[ptr2++];

            // Mise à jour du segment dans le tableau original
            for (int j = i; j <= f2; j++) {
                tab[j] = temporaire[j];
            }
        }
        pas *= 2;
    }
    free(temporaire);
}