Introduction aux Algorithmes de Tri

Les algorithmes de tri constituent une pierre angulaire de l'informatique, essentiels pour organiser des collections de données de manière efficace. Leur performance est évaluée selon plusieurs critères fondamentaux.

Critères d'Évaluation

• Efficacité temporelle (Complexité) : Mesure la vitesse d'exécution de l'algorithme en fonction de la taille des données (n).
• Espace mémoire (In-place) : Indique si l'algorithme nécessite une quantité d'espace supplémentaire constante (en place) ou proportionnelle à la taille des données.
• Stabilité : Caractérise la capacité de l'algorithme à préserver l'ordre relatif des éléments de même valeur.

Concepts Clés

Adaptativité (Adaptive Sorting) : Un algorithme de tri est dit adaptatif s'il peut tirer parti de l'ordre existant dans les données d'entrée pour réduire son temps de calcul. Les algorithmes adaptatifs ont souvent une complexité temporelle optimale meilleure que leur complexité moyenne dans certains scénarios.

Tri par comparaison vs. Tri non comparatif : Les algorithmes de tri par comparaison s'appuient sur des opérateurs de comparaison (<, =, >) pour déterminer l'ordre relatif des éléments. Leur borne inférieure théorique est de O(n log n). En revanche, les tris non comparatifs, qui n'utilisent pas de comparaisons directes, peuvent atteindre une complexité de O(n), mais leur applicabilité est souvent plus restreinte (par exemple, entiers dans une certaine plage).

Algorithmes de Tri par Comparaison de Complexité O(n²)

Tri par Sélection (Selection Sort)

Le tri par sélection parcourt le tableau et, à chaque étape, trouve l'élément le plus petit de la sous-liste non triée, puis le place à la fin de la sous-liste triée. Ce processus se répète jusqu'à ce que tout le tableau soit trié.

1. Initialement, tous les éléments sont considérés comme non triés.
2. Dans l'intervalle non trié, l'algorithme cherche l'élément le plus petit et l'échange avec l'élément au début de cet intervalle.
3. L'intervalle trié s'étend d'un élément, et le processus se poursuit pour la nouvelle sous-liste non triée.

#include <vector>
#include <algorithm> // Pour std::swap

void triSelection(std::vector<int>& elements) {
    int taille = elements.size();
    // Boucle externe : itère sur la partie non triée [i, taille - 1]
    for (int i = 0; i < taille - 1; ++i) {
        // Boucle interne : trouve l'indice du plus petit élément dans [i, taille - 1]
        int indexMin = i;
        for (int j = i + 1; j < taille; ++j) {
            if (elements[j] < elements[indexMin]) {
                indexMin = j; // Met à jour l'indice du minimum
            }
        }
        // Échange l'élément minimal avec le premier élément de la partie non triée
        std::swap(elements[i], elements[indexMin]);
    }
}

Analyse

• Complexité temporelle : O(n²). Il effectue n-1 passes, et chaque passe implique de parcourir une sous-liste qui diminue en taille. Non-adaptatif.
• Complexité spatiale : O(1). C'est un tri en place car il n'utilise qu'un nombre constant de variables auxiliaires.
• Stabilité : Non stable. L'échange d'éléments peut modifier l'ordre relatif d'éléments de même valeur si l'élément minimal trouvé est éloigné de sa position cible.

Tri à Bulles (Bubble Sort)

Le tri à bulles compare et échange de manière répétée les éléments adjacents s'ils sont dans le mauvais ordre, faisant "remonter" les plus grands éléments vers la fin du tableau comme des bulles. Chaque passe garantit que le plus grand élément restant est placé à sa position finale.

1. Parcourt le tableau de gauche à droite, comparant les paires adjacentes.
2. Si l'élément de gauche est plus grand que celui de droite, ils sont échangés.
3. Après chaque passe, le plus grand élément "bulle" jusqu'à sa position correcte à la fin du sous-tableau non trié.

#include <vector>
#include <algorithm> // Pour std::swap

void triBulles(std::vector<int>& donnees) {
    int n = donnees.size();
    // Boucle externe : réduit la taille de la partie non triée à chaque itération
    for (int i = 0; i < n - 1; ++i) {
        // Boucle interne : parcourt la partie non triée et échange les éléments adjacents
        for (int j = 0; j < n - 1 - i; ++j) {
            if (donnees[j] > donnees[j + 1]) {
                std::swap(donnees[j], donnees[j + 1]);
            }
        }
    }
}

Optimisation avec un drapeau

Une optimisation courante consiste à introduire un drapeau (flag) pour détecter si des échanges ont eu lieu lors d'une passe. Si aucune paire n'a été échangée, cela signifie que le tableau est déjà trié, et l'algorithme peut s'arrêter prématurément.

#include <vector>
#include <algorithm> // Pour std::swap

void triBullesOptimise(std::vector<int>& elements) {
    int taille = elements.size();
    bool echangeEffectue;
    // La boucle externe continue tant que des échanges sont possibles
    for (int i = 0; i < taille - 1; ++i) {
        echangeEffectue = false; // Réinitialise le drapeau pour chaque passe
        // Parcourt la partie non triée du tableau
        for (int j = 0; j < taille - 1 - i; ++j) {
            if (elements[j] > elements[j + 1]) {
                std::swap(elements[j], elements[j + 1]);
                echangeEffectue = true; // Un échange a eu lieu
            }
        }
        // Si aucun échange n'a été effectué lors de cette passe, le tableau est trié
        if (!echangeEffectue) {
            break;
        }
    }
}

Analyse

• Complexité temporelle : O(n²) en moyenne et dans le pire des cas. Cependant, avec l'optimisation par drapeau, le meilleur cas (tableau déjà trié) atteint O(n). C'est un tri adaptatif.
• Complexité spatiale : O(1). C'est un tri en place.
• Stabilité : Stable. L'algorithme n'échange que des éléments adjacents et utilise une condition stricte (>) pour les échanges, garantissant que l'ordre relatif des éléments égaux est conservé.

Tri par Insertion (Insertion Sort)

Le tri par insertion construit le tableau trié un élément à la fois. Il prend un élément de la partie non triée et l'insère à sa position correcte dans la partie déjà triée.

1. Le premier élément est considéré comme trié.
2. Pour chaque élément suivant, il est comparé aux éléments de la sous-liste triée.
3. L'élément est inséré à la position où il est plus grand que l'élément précédent et plus petit que l'élément suivant. Les éléments plus grands sont décalés pour faire de la place.

#include <vector>

void triInsertion(std::vector<int>& tableau) {
    int taille = tableau.size();
    // Boucle externe : considère chaque élément à partir du deuxième
    for (int i = 1; i < taille; ++i) {
        int elementCourant = tableau[i];
        int j = i - 1;
        // Boucle interne : décale les éléments plus grands dans la partie triée
        // pour faire de la place à l'elementCourant
        while (j >= 0 && tableau[j] > elementCourant) {
            tableau[j + 1] = tableau[j];
            j--;
        }
        // Insère l'elementCourant à sa position correcte
        tableau[j + 1] = elementCourant;
    }
}

Avantages et Utilisation Hybride

Bien que de complexité O(n²), le tri par insertion est souvent plus rapide que d'autres tris quadratiques en pratique, surtout pour de petits tableaux ou des tableaux presque triés. Son nombre d'opérations élémentaires est faible, et il est adaptatif (O(n) dans le meilleur des cas).

De nombreuses bibliothèques standard (comme Java's Arrays.sort pour les objets, qui utilise TimSort, ou C++'s std::sort en interne) emploient une stratégie hybride : elles utilisent des algorithmes plus complexes (comme le tri rapide ou le tri fusion) pour les grands ensembles de données, mais basculent vers le tri par insertion lorsque la taille des sous-tableaux devient inférieure à un certain seuil (souvent entre 7 et 64 éléments). Cela permet de tirer parti de la faible surcharge du tri par insertion pour les petites listes.

// Extrait conceptuel d'une implémentation hybride (similaire à TimSort/MergeSort)
public static <T extends Comparable<T>> void triHybride(T[] tableau, int debut, int fin, int seuilInsertion) {
    int longueur = fin - debut + 1;

    // Utilise le tri par insertion pour les petits tableaux
    if (longueur <= seuilInsertion) {
        for (int i = debut + 1; i <= fin; ++i) {
            T cle = tableau[i];
            int j = i - 1;
            while (j >= debut && tableau[j].compareTo(cle) > 0) {
                tableau[j + 1] = tableau[j];
                j--;
            }
            tableau[j + 1] = cle;
        }
        return;
    }

    // Sinon, procède avec une approche de type tri fusion ou rapide
    int milieu = debut + (fin - debut) / 2;
    triHybride(tableau, debut, milieu, seuilInsertion);
    triHybride(tableau, milieu + 1, fin, seuilInsertion);

    // Phase de fusion (simplifiée pour l'exemple)
    fusionner(tableau, debut, milieu, fin);
}

// Fonction de fusion (à implémenter)
private static <T extends Comparable<T>> void fusionner(T[] tableau, int debut, int milieu, int fin) {
    // Logique de fusion ici
}

Analyse

• Complexité temporelle : O(n²) en moyenne et dans le pire des cas. O(n) dans le meilleur des cas (tableau déjà trié). C'est un tri adaptatif.
• Complexité spatiale : O(1). C'est un tri en place.
• Stabilité : Stable. Les éléments égaux ne sont pas déplacés si un élément est inséré à leur droite, conservant leur ordre relatif.

Algorithmes de Tri par Comparaison de Complexité O(n log n)

Tri Rapide (Quick Sort)

Le tri rapide est un algorithme de tri très efficace basé sur le principe "diviser pour régner". Son cœur réside dans l'opération de partitionnement, qui réorganise un tableau autour d'un "pivot" de telle sorte que tous les éléments inférieurs au pivot se trouvent à sa gauche, et tous les éléments supérieurs à sa droite.

1. Sélectionne un élément, le "pivot".
2. Réorganise le tableau (partitionnement) de manière que tous les éléments plus petits que le pivot précèdent le pivot, et tous les éléments plus grands suivent le pivot. Le pivot est alors à sa position finale triée.
3. Applique récursivement les étapes 1 et 2 aux sous-tableaux à gauche et à droite du pivot.

#include <vector>
#include <algorithm> // Pour std::swap

// Fonction de partitionnement (schéma de Hoare)
int partitionHoare(std::vector<int>& arr, int gauche, int droite) {
    int pivotVal = arr[gauche]; // Utilise le premier élément comme pivot
    int ptrG = gauche;
    int ptrD = droite;

    while (ptrG <= ptrD) {
        // Incrémente ptrG tant que l'élément est inférieur ou égal au pivot
        while (ptrG <= droite && arr[ptrG] < pivotVal) {
            ptrG++;
        }
        // Décrémente ptrD tant que l'élément est supérieur ou égal au pivot
        while (ptrD >= gauche && arr[ptrD] > pivotVal) {
            ptrD--;
        }

        // Si les pointeurs ne se sont pas croisés, échange les éléments
        if (ptrG < ptrD) {
            std::swap(arr[ptrG], arr[ptrD]);
            ptrG++;
            ptrD--;
        } else {
            // Les pointeurs se sont croisés ou sont égaux, sortie de la boucle
            break;
        }
    }
    // Le pivot est maintenant à la position ptrD
    return ptrD;
}

// Fonction récursive du tri rapide
void triRapide(std::vector<int>& tableau, int debut, int fin) {
    // Condition d'arrêt : si le sous-tableau a 0 ou 1 élément
    if (debut >= fin) {
        return;
    }
    // Effectue le partitionnement et obtient l'indice du pivot
    int indicePivot = partitionHoare(tableau, debut, fin);

    // Trie récursivement les sous-tableaux
    triRapide(tableau, debut, indicePivot);
    triRapide(tableau, indicePivot + 1, fin);
}

Analyse

• Complexité temporelle : O(n log n) en moyenne. O(n²) dans le pire des cas (par exemple, tableau déjà trié et pivot toujours le min/max). Non-adaptatif.
• Complexité spatiale : O(log n) en moyenne (pour la pile d'appels récursifs). O(n) dans le pire des cas. C'est un tri en place.
• Stabilité : Non stable. Le partitionnement peut échanger des éléments très éloignés, modifiant l'ordre relatif d'éléments égaux.

Optimisations du Tri Rapide

Pour améliorer la robustesse et la performance du tri rapide, plusieurs optimisations peuvent être appliquées :

1. Choix du Pivot (Médiane de trois) : Sélectionner le pivot comme la médiane des éléments au début, au milieu et à la fin du sous-tableau réduit la probabilité d'un pire cas.

// Fonction pour trouver l'indice de la médiane de trois éléments
int selectionMedianeDeTrois(std::vector<int>& donnees, int g, int m, int d) {
   if ((donnees[g] < donnees[m] && donnees[m] < donnees[d]) || (donnees[d] < donnees[m] && donnees[m] < donnees[g]))
       return m; // m est la médiane
   if ((donnees[m] < donnees[g] && donnees[g] < donnees[d]) || (donnees[d] < donnees[g] && donnees[g] < donnees[m]))
       return g; // g est la médiane
   return d; // d est la médiane
}

// Partitionnement amélioré avec médiane de trois
int partitionAvecMediane(std::vector<int>& tableau, int debut, int fin) {
   int milieu = debut + (fin - debut) / 2;
   // Échange la médiane avec le premier élément pour qu'il serve de pivot
   std::swap(tableau[debut], tableau[selectionMedianeDeTrois(tableau, debut, milieu, fin)]);
   
   // Le reste est le même que partitionHoare, avec le pivot en tableau[debut]
   int pivotVal = tableau[debut];
   int i = debut + 1;
   int j = fin;
   while (true) {
       while (i <= j && tableau[i] <= pivotVal) i++;
       while (j >= i && tableau[j] >= pivotVal) j--;
       if (i > j) break;
       std::swap(tableau[i], tableau[j]);
   }
   std::swap(tableau[debut], tableau[j]);
   return j;
}

// triRapide utiliserait partitionAvecMediane

3. Optimisation de la récursivité (Tail Recursion / Boucle) : Pour éviter une profondeur de pile excessive, on peut trier récursivement la plus petite des deux sous-listes et utiliser une boucle pour la plus grande. Ceci réduit la complexité spatiale dans le pire des cas à O(log n).

#include <vector>
#include <algorithm>

// Utilisation de partitionAvecMediane ou une autre partition stable
// int partition(std::vector<int>& tableau, int debut, int fin) { ... }

void triRapideOptimiseRecursif(std::vector<int>& tableau, int debut, int fin) {
   while (debut < fin) {
       int indicePivot = partitionAvecMediane(tableau, debut, fin);

       // Trie la plus petite des deux partitions récursivement
       // La plus grande est traitée par la boucle (tail recursion elimination)
       if (indicePivot - debut < fin - indicePivot) {
           triRapideOptimiseRecursif(tableau, debut, indicePivot - 1);
           debut = indicePivot + 1; // Ajuste 'debut' pour la prochaine itération de la boucle
       } else {
           triRapideOptimiseRecursif(tableau, indicePivot + 1, fin);
           fin = indicePivot - 1; // Ajuste 'fin' pour la prochaine itération de la boucle
       }
   }
}

5. Partitionnement à trois voies (Three-Way Partitioning) : Particulièrement utile lorsque le tableau contient de nombreux éléments dupliqués. Il divise le tableau en trois parties : éléments plus petits que le pivot, éléments égaux au pivot, et éléments plus grands que le pivot.

#include <vector>
#include <algorithm> // Pour std::swap

// Fonction de partitionnement à trois voies (similaire à Dijkstra)
// Les éléments sont regroupés en < pivot, = pivot, > pivot
void partitionTroisVoies(std::vector<int>& arr, int& lt, int& gt, int debut, int fin) {
   if (debut >= fin) {
       lt = debut; gt = fin;
       return;
   }

   int pivot = arr[debut];
   lt = debut; // lt pointe vers le dernier élément < pivot
   int i = debut + 1; // i pointe vers l'élément courant
   gt = fin; // gt pointe vers le premier élément > pivot

   while (i <= gt) {
       if (arr[i] < pivot) {
           std::swap(arr[lt++], arr[i++]);
       } else if (arr[i] > pivot) {
           std::swap(arr[i], arr[gt--]);
       } else {
           i++; // arr[i] == pivot, le laisse en place pour le moment
       }
   }
   // À la fin, les éléments de debut à lt-1 sont < pivot
   // Les éléments de lt à gt sont = pivot
   // Les éléments de gt+1 à fin sont > pivot
}

// Fonction de tri rapide avec partitionnement à trois voies
void triRapideTroisVoies(std::vector<int>& tableau, int debut, int fin) {
   if (debut >= fin) return;

   int lt, gt; // lt sera l'indice de fin de la zone < pivot, gt l'indice de début de la zone > pivot
   partitionTroisVoies(tableau, lt, gt, debut, fin);

   triRapideTroisVoies(tableau, debut, lt - 1); // Trie la partie < pivot
   triRapideTroisVoies(tableau, gt + 1, fin); // Trie la partie > pivot
}

Des tests comparatifs montrent que le tri rapide standard est souvent plus rapide pour des données aléatoires, mais le tri rapide à trois voies brille par sa performance lorsqu'il y a une forte proportion d'éléments dupliqués, avec des gains significatifs pouvant aller jusqu'à 15 fois la vitesse pour des ensembles de données de taille moyenne. Cette optimisation devient d'autant plus avantageuse que la taille des données et la quantité de répétitions augmentent.

Tri Fusion (Merge Sort)

Le tri fusion est un algorithme de tri "diviser pour régner" qui divise un tableau en deux moitiés, trie récursivement chaque moitié, puis fusionne les deux moitiés triées pour former un tableau complètement trié.

1. Phase de Division : Le tableau est récursivement divisé en deux moitiés jusqu'à ce que chaque sous-tableau contienne un seul élément (qui est par définition trié).
2. Phase de Fusion : Les sous-tableaux sont ensuite fusionnés par paires, dans un ordre trié, jusqu'à ce que le tableau entier soit reconstitué et trié.

#include <vector>
#include <algorithm> // Pour std::min et std::max

// Fonction pour fusionner deux sous-tableaux triés
void fusionner(std::vector<int>& arr, int debut, int milieu, int fin) {
    // Crée un tableau temporaire pour stocker les éléments fusionnés
    std::vector<int> temp;
    temp.reserve(fin - debut + 1);

    int ptrG = debut;      // Pointeur pour le sous-tableau gauche
    int ptrD = milieu + 1; // Pointeur pour le sous-tableau droit

    // Compare et ajoute les éléments au tableau temporaire
    while (ptrG <= milieu && ptrD <= fin) {
        if (arr[ptrG] <= arr[ptrD]) { // Utilise <= pour la stabilité
            temp.push_back(arr[ptrG++]);
        } else {
            temp.push_back(arr[ptrD++]);
        }
    }
    // Ajoute les éléments restants du sous-tableau gauche
    while (ptrG <= milieu) {
        temp.push_back(arr[ptrG++]);
    }
    // Ajoute les éléments restants du sous-tableau droit
    while (ptrD <= fin) {
        temp.push_back(arr[ptrD++]);
    }

    // Copie les éléments fusionnés du tableau temporaire vers le tableau original
    for (int k = 0; k < temp.size(); ++k) {
        arr[debut + k] = temp[k];
    }
}

// Fonction récursive du tri fusion
void triFusion(std::vector<int>& tableau, int debut, int fin) {
    // Condition d'arrêt : sous-tableau de 0 ou 1 élément
    if (debut >= fin) {
        return;
    }
    int milieu = debut + (fin - debut) / 2; // Calcule le point médian

    // Phase de division : trie récursivement les deux moitiés
    triFusion(tableau, debut, milieu);
    triFusion(tableau, milieu + 1, fin);

    // Phase de fusion : fusionne les moitiés triées
    fusionner(tableau, debut, milieu, fin);
}

Tri Fusion pour Listes Chaînées

Le tri fusion est particulièrement adapté aux listes chaînées, car l'opération de fusion peut être réalisée sans tableau auxiliaire et sans les coûts de déplacement d'éléments associés aux tableaux. Cela permet une complexité spatiale de O(1) pour les listes chaînées, en ne modifiant que les pointeurs.

#include <iostream> // Pour std::cout

// Définition d'un nœud de liste chaînée
struct NoeudListe {
    int valeur;
    NoeudListe* suivant;
    NoeudListe(int x) : valeur(x), suivant(nullptr) {}
};

// Fonction pour fusionner deux listes chaînées triées
NoeudListe* fusionnerDeuxListes(NoeudListe* liste1, NoeudListe* liste2) {
    NoeudListe fictif(0); // Nœud factice pour simplifier l'ajout au début
    NoeudListe* queue = &fictif; // Pointeur pour la queue de la liste fusionnée

    while (liste1 != nullptr && liste2 != nullptr) {
        if (liste1->valeur <= liste2->valeur) { // Pour la stabilité, prend de liste1 en cas d'égalité
            queue->suivant = liste1;
            liste1 = liste1->suivant;
        } else {
            queue->suivant = liste2;
            liste2 = liste2->suivant;
        }
        queue = queue->suivant;
    }
    // Ajoute les nœuds restants (s'il y en a)
    queue->suivant = (liste1 != nullptr) ? liste1 : liste2;
    return fictif.suivant; // Retourne le début de la liste fusionnée
}

// Fonction pour diviser une liste en deux moitiés
// Retourne la seconde moitié, et la première est modifiée pour se terminer
NoeudListe* diviserListe(NoeudListe* tete) {
    if (tete == nullptr || tete->suivant == nullptr) {
        return nullptr;
    }
    NoeudListe* lent = tete;
    NoeudListe* rapide = tete->suivant;
    while (rapide != nullptr && rapide->suivant != nullptr) {
        lent = lent->suivant;
        rapide = rapide->suivant->suivant;
    }
    NoeudListe* secondeMoitie = lent->suivant;
    lent->suivant = nullptr; // Coupe la liste en deux
    return secondeMoitie;
}

// Tri fusion récursif pour les listes chaînées
NoeudListe* triFusionListe(NoeudListe* tete) {
    if (tete == nullptr || tete->suivant == nullptr) {
        return tete; // Cas de base : liste vide ou avec un seul élément
    }

    // Divise la liste en deux
    NoeudListe* milieu = diviserListe(tete);

    // Trie récursivement les deux moitiés
    NoeudListe* gaucheTriee = triFusionListe(tete);
    NoeudListe* droiteTriee = triFusionListe(milieu);

    // Fusionne les moitiés triées
    return fusionnerDeuxListes(gaucheTriee, droiteTriee);
}

// Fonction utilitaire pour imprimer une liste
void afficherListe(NoeudListe* tete) {
    NoeudListe* courant = tete;
    while (courant != nullptr) {
        std::cout << courant->valeur;
        if (courant->suivant != nullptr) {
            std::cout << " -> ";
        }
        courant = courant->suivant;
    }
    std::cout << std::endl;
}

int main() {
    NoeudListe* maListe = new NoeudListe(4);
    maListe->suivant = new NoeudListe(2);
    maListe->suivant->suivant = new NoeudListe(1);
    maListe->suivant->suivant->suivant = new NoeudListe(3);
    maListe->suivant->suivant->suivant->suivant = new NoeudListe(2);

    std::cout << "Liste originale: ";
    afficherListe(maListe);

    NoeudListe* listeTriee = triFusionListe(maListe);

    std::cout << "Liste triée: ";
    afficherListe(listeTriee);

    // Nettoyage de la mémoire (non montré pour la concision)
    return 0;
}

Analyse

• Complexité temporelle : O(n log n). La division en log n niveaux et la fusion de n éléments à chaque niveau. Non-adaptatif.
• Complexité spatiale : O(n) pour les tableaux (en raison du tableau temporaire). O(1) pour les listes chaînées.
• Stabilité : Stable. L'algorithme préserve l'ordre relatif des éléments égaux lors de la fusion.

Tri par Tas (Heap Sort)

Le tri par tas utilise la structure de données "tas" (heap), qui est un arbre binaire presque complet où chaque nœud parent est plus grand (ou plus petit) que ses enfants. Pour un tri ascendant, on construit un tas max.

1. Construire un tas max à partir du tableau d'entrée. Le plus grand élément est alors à la racine (premier élément du tableau).
2. Échanger le plus grand élément (racine) avec le dernier élément du tableau. Le tableau est maintenant partiellement trié.
3. Réduire la taille du tas d'un élément et "tasser" la nouvelle racine pour restaurer la propriété de tas.
4. Répéter les étapes 2 et 3 jusqu'à ce que le tas soit vide.

#include <vector>
#include <algorithm> // Pour std::swap

// Fonction pour "tasser" un sous-arbre enraciné à l'indice 'racineIndex'
// dans un tableau de taille 'tailleTas'.
void tasserVersLeBas(std::vector<int>& arr, int tailleTas, int racineIndex) {
    int plusGrand = racineIndex; // Initialise le plus grand comme la racine
    int enfantGauche = 2 * racineIndex + 1;
    int enfantDroit = 2 * racineIndex + 2;

    // Si l'enfant gauche est plus grand que la racine
    if (enfantGauche < tailleTas && arr[enfantGauche] > arr[plusGrand]) {
        plusGrand = enfantGauche;
    }
    // Si l'enfant droit est plus grand que le courant le plus grand
    if (enfantDroit < tailleTas && arr[enfantDroit] > arr[plusGrand]) {
        plusGrand = enfantDroit;
    }

    // Si le plus grand n'est pas la racine, échanger et continuer de tasser
    if (plusGrand != racineIndex) {
        std::swap(arr[racineIndex], arr[plusGrand]);
        tasserVersLeBas(arr, tailleTas, plusGrand); // Appel récursif
    }
}

// Fonction principale de tri par tas
void triParTas(std::vector<int>& elements) {
    int n = elements.size();

    // Phase 1 : Construire le tas max (réarranger le tableau)
    // Commence du dernier nœud parent non feuille et remonte
    for (int i = n / 2 - 1; i >= 0; --i) {
        tasserVersLeBas(elements, n, i);
    }

    // Phase 2 : Extraire les éléments un par un du tas
    for (int i = n - 1; i > 0; --i) {
        // Déplace l'élément courant de la racine du tas à la fin du tableau
        std::swap(elements[0], elements[i]);
        // Appelle tasserVersLeBas sur le tas réduit
        tasserVersLeBas(elements, i, 0); // La taille du tas diminue à chaque étape
    }
}

Analyse

• Complexité temporelle : O(n log n). La construction du tas prend O(n), et chaque extraction/tassage prend O(log n) sur n-1 éléments. Non-adaptatif.
• Complexité spatiale : O(1). C'est un tri en place.
• Stabilité : Non stable. Les échanges d'éléments lors du tassage et de l'extraction peuvent modifier l'ordre relatif d'éléments égaux.

Algorithmes de Tri Non Comparatifs (Complexité O(n))

Tri par Seaux (Bucket Sort)

Le tri par seaux est un algorithme de tri non comparatif qui distribue les éléments dans un nombre fini de seaux, trie chaque seau individuellement, puis concatène les seaux triés. Il est efficace lorsque les données d'entrée sont uniformément réparties dans une plage donnée.

1. Initialiser k seaux.
2. Distribuer les n éléments du tableau d'entrée dans les seaux appropriés. Un mappage est utilisé pour déterminer le seau de chaque élément (par exemple, pour des nombres dans [0, 1), index_seau = floor(valeur * k)).
3. Trier chaque seau individuellement (par exemple, avec un tri par insertion ou un tri rapide).
4. Concaténer les éléments de tous les seaux dans l'ordre pour obtenir le tableau trié final.

#include <vector>
#include <algorithm> // Pour std::sort

void triParSeaux(std::vector<float>& nombres) {
    int n = nombres.size();
    if (n == 0) return;

    // Le nombre de seaux est souvent choisi comme sqrt(n) ou n/2
    int nombreSeaux = n / 2;
    if (nombreSeaux == 0) nombreSeaux = 1; // Au moins un seau

    // Créer les seaux (vecteurs de floats)
    std::vector<std::vector<float>> seaux(nombreSeaux);

    // 1. Distribuer les éléments dans les seaux
    // Assumons que les nombres sont dans la plage [0, 1) pour un mappage simple
    for (float nb : nombres) {
        int indexSeau = static_cast<int>(nb * nombreSeaux);
        // Assure que l'indice reste dans les limites [0, nombreSeaux - 1]
        if (indexSeau >= nombreSeaux) indexSeau = nombreSeaux - 1; 
        seaux[indexSeau].push_back(nb);
    }

    // 2. Trier chaque seau individuellement
    for (std::vector<float>& seau : seaux) {
        std::sort(seau.begin(), seau.end()); // Utilise un tri interne (ex: Introsort)
    }

    // 3. Concaténer les résultats des seaux
    int indexGlobal = 0;
    for (const std::vector<float>& seau : seaux) {
        for (float nb : seau) {
            nombres[indexGlobal++] = nb;
        }
    }
}

Analyse

• Complexité temporelle : O(n+k) en moyenne, où k est le nombre de seaux. Si les éléments sont uniformément distribués et chaque seau est trié en O(1) (par exemple, tri par insertion pour de très petits seaux), la complexité est linéaire. Dans le pire des cas (tous les éléments dans un seul seau), elle peut être O(n²).
• Complexité spatiale : O(n+k). Non en place.
• Stabilité : Dépend de l'algorithme de tri utilisé pour les seaux. Si le tri des seaux est stable, alors le tri par seaux est stable.

Tri par Comptage (Counting Sort)

Le tri par comptage est un algorithme de tri non comparatif qui est efficace pour trier des entiers lorsque leur plage (maximum - minimum) n'est pas trop grande. Il compte la fréquence de chaque élément distinct, puis utilise ces comptes pour déterminer les positions finales des éléments dans le tableau trié.

1. Trouver le plus grand élément (m) dans le tableau.
2. Créer un tableau comptes de taille m+1, initialisé à zéro.
3. Parcourir le tableau d'entrée et incrémenter comptes[valeur] pour chaque occurrence de valeur.
4. Construire le tableau trié en parcourant comptes de 0 à m et en ajoutant chaque valeur à la liste finale autant de fois qu'elle est apparue.

#include <vector>
#include <algorithm> // Pour std::max_element

// Implémentation simple du tri par comptage, non stable et ne gère pas les nombres négatifs
void triComptageSimple(std::vector<int>& nombres) {
    int n = nombres.size();
    if (n == 0) return;

    // 1. Trouver le maximum (m) dans le tableau
    int maxVal = 0;
    for (int nb : nombres) {
        if (nb > maxVal) {
            maxVal = nb;
        }
    }

    // 2. Créer un tableau de comptage et compter les occurrences
    // La taille est maxVal + 1 pour inclure 0
    std::vector<int> compteurs(maxVal + 1, 0);
    for (int nb : nombres) {
        compteurs[nb]++;
    }

    // 3. Reconstruire le tableau original à partir des compteurs
    int indexActuel = 0;
    for (int val = 0; val <= maxVal; ++val) {
        while (compteurs[val] > 0) {
            nombres[indexActuel++] = val;
            compteurs[val]--;
        }
    }
}

Analyse

• Complexité temporelle : O(n+m), où n est le nombre d'éléments et m est la plage des valeurs (max - min). Non-adaptatif.
• Complexité spatiale : O(n+m). Non en place.
• Stabilité : Stable avec une implémentation légèrement plus complexe utilisant un tableau de résultats et un parcours inverse. L'implémentation simple ci-dessus n'est pas stable.

Tri par Base (Radix Sort)

Le tri par base est un algorithme de tri non comparatif qui trie les nombres en traitant les chiffres individuels, de la position la moins significative à la plus significative, en utilisant un algorithme de tri stable (comme le tri par comptage) à chaque étape.

1. Déterminer le nombre maximal de chiffres (ou bits) dans le plus grand nombre.
2. Pour chaque position de chiffre (de droite à gauche, de la moins significative à la plus significative) :
   1. Effectuer un tri par comptage (ou autre tri stable) sur le tableau en se basant sur le chiffre à la position actuelle.

#include <vector>
#include <algorithm> // Pour std::max_element

// Fonction pour obtenir le chiffre à une position donnée (exp) d'un nombre
// exp représente 10^(k-1) pour le k-ième chiffre (ex: exp=1 pour unités, exp=10 pour dizaines)
int obtenirChiffre(int nombre, int exp) {
    return (nombre / exp) % 10;
}

// Tri par comptage stable basé sur un chiffre spécifique (exp)
void triParComptageParChiffre(std::vector<int>& arr, int exp) {
    int n = arr.size();
    std::vector<int> sortie(n); // Tableau de sortie temporaire
    std::vector<int> compteurs(10, 0); // Pour les chiffres de 0 à 9

    // Compter les occurrences de chaque chiffre à la position 'exp'
    for (int i = 0; i < n; ++i) {
        compteurs[obtenirChiffre(arr[i], exp)]++;
    }

    // Convertir les comptes en indices cumulatifs (préfixe sum)
    // compteurs[i] contient maintenant la position de l'élément suivant pour le chiffre i
    for (int i = 1; i < 10; ++i) {
        compteurs[i] += compteurs[i - 1];
    }

    // Placer les éléments dans le tableau de sortie de manière stable
    // Parcourir le tableau d'entrée de droite à gauche est crucial pour la stabilité
    for (int i = n - 1; i >= 0; --i) {
        int chiffre = obtenirChiffre(arr[i], exp);
        sortie[compteurs[chiff] - 1] = arr[i];
        compteurs[chiff]--;
    }

    // Copier le tableau de sortie dans le tableau original
    for (int i = 0; i < n; ++i) {
        arr[i] = sortie[i];
    }
}

// Fonction principale du tri par base
void triParBase(std::vector<int>& nombres) {
    int n = nombres.size();
    if (n == 0) return;

    // Trouver le maximum pour déterminer le nombre de passes (chiffres)
    int maxVal = *std::max_element(nombres.begin(), nombres.end());

    // Effectuer le tri par comptage pour chaque position de chiffre
    // de la moins significative (unités) à la plus significative
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        triParComptageParChiffre(nombres, exp);
    }
}

Analyse

• Complexité temporelle : O(nk), où n est le nombre d'éléments, et k est le nombre maximal de chiffres (ou bits) des nombres. Si k est petit et constant, la complexité est linéaire O(n). Non-adaptatif.
• Complexité spatiale : O(n+d), où d est la base numérique (souvent 10 pour les chiffres décimaux). Non en place.
• Stabilité : Stable, car il utilise un tri par comptage stable à chaque passe.

Facteurs Clés de la Stabilité des Algorithmes de Tri

La stabilité d'un algorithme de tri est déterminée par la manière dont il gère les éléments ayant des valeurs égales. Un tri stable garantit que l'ordre relatif des éléments égaux est maintenu. Plusieurs facteurs influencent cette propriété :

1. Logique de comparaison et d'échange :
   • Un algorithme est stable si, lors de la comparaison de deux éléments égaux, il ne les échange pas ou ne modifie pas leur ordre relatif.
   • Il est instable si des éléments égaux peuvent voir leur ordre relatif modifié.
2. Mécanisme de déplacement des éléments :
   • Les algorithmes qui effectuent des échanges sur de longues distances sont plus susceptibles d'être instables.
   • Ceux qui procèdent par insertions ou fusions ordonnées sont généralement stables.
3. Détails d'implémentation : La stabilité peut souvent être influencée par des choix subtils dans le code, comme l'utilisation de < vs <= dans les comparaisons.

Analyse de Stabilité pour Divers Algorithmes

Algorithmes de Tri Stables

• Tri à Bulles (Bubble Sort) :

  • Raison : Échange uniquement si l'élément courant est strictement plus grand que le suivant (arr[j] > arr[j+1]). Deux éléments égaux ne sont jamais échangés.

  if (arr[j] > arr[j+1]) { // Condition stricte pour l'échange
      std::swap(arr[j], arr[j+1]);
  }
  
  

• Tri par Insertion (Insertion Sort) :

  • Raison : Lors de la recherche de la position d'insertion, si un élément est égal à l'élément courant, l'insertion se fait après cet élément, préservant ainsi l'ordre relatif.

  while (j >= 0 && arr[j] > cle) { // Décalage tant que l'élément est STRICTEMENT plus grand
      arr[j + 1] = arr[j];
      j--;
  }
  arr[j + 1] = cle; // Insertion après les éléments égaux
  
  

• Tri Fusion (Merge Sort) :

  • Raison : Pendant la phase de fusion, lorsque deux éléments sont égaux (un de chaque sous-tableau), l'élément du sous-tableau gauche est toujours choisi en premier.

  if (arr[ptrG] <= arr[ptrD]) { // Priorise l'élément du sous-tableau gauche en cas d'égalité
      temp.push_back(arr[ptrG++]);
  } else {
      temp.push_back(arr[ptrD++]);
  }
  
  

• Tri par Comptage (Counting Sort) :

  • Raison : En parcourant le tableau original de droite à gauche pour construire le tableau de sortie, les éléments égaux sont placés dans l'ordre inverse de leur apparition dans le tableau original. Cela préserve leur ordre relatif si les indices cumulatifs sont calculés correctement.

  // Construction du tableau de sortie de droite à gauche pour la stabilité
  for (int i = n - 1; i >= 0; --i) {
      sortie[compteurs[arr[i]] - 1] = arr[i];
      compteurs[arr[i]]--;
  }
  
  

Algorithmes de Tri Instables

• Tri par Sélection (Selection Sort) :

  • Raison : L'algorithme peut échanger un élément min/max (souvent éloigné) avec un élément au début de la sous-liste non triée, ce qui peut inverser l'ordre d'éléments égaux.

  // Si arr = [4, 2a, 3, 2b, 1]
  // min_idx sera 4 (pour 1). Swap arr[0] (4) et arr[4] (1).
  // arr devient [1, 2a, 3, 2b, 4].
  // Puis pour la sous-liste [2a, 3, 2b, 4], min_idx est 1 (pour 2a).
  // Swap arr[1] (2a) et arr[3] (2b). L'ordre relatif de 2a et 2b est inversé.
  std::swap(arr[i], arr[indexMin]);
  
  

• Tri Rapide (Quick Sort) :

  • Raison : Le processus de partitionnement peut échanger des éléments de part et d'autre du pivot sans tenir compte de leur ordre relatif original s'ils sont égaux.

  // Dans une partition typique, des éléments comme arr[i] et arr[j]
  // peuvent être échangés même s'ils sont égaux au pivot ou à d'autres éléments égaux,
  // modifiant leur ordre initial.
  std::swap(arr[i], arr[j]);
  
  

• Tri par Tas (Heap Sort) :

  • Raison : Les opérations de "tassage" (sift-down) et d'échange de la racine avec le dernier élément peuvent placer des éléments égaux dans des positions arbitraires, brisant leur ordre original.

  // Échange d'éléments dans tasserVersLeBas ou lors de l'extraction
  std::swap(arr[racineIndex], arr[plusGrand]);
  std::swap(arr[0], arr[i]);
  
  

Techniques pour Rendre un Tri Instable Stable

Il est possible de modifier certains algorithmes de tri instables pour les rendre stables, souvent au prix d'une légère augmentation de la complexité temporelle ou spatiale.

1. Attacher des Indices Originaux : En couplant chaque élément avec son indice d'origine et en utilisant cet indice comme critère de bris d'égalité dans les comparaisons. Cela rend la comparaison stable pour n'importe quel algorithme de tri.

   #include <vector>
   #include <algorithm> // Pour std::sort
   
   // Structure pour stocker la valeur et l'indice original
   struct ElementIndexe {
       int valeur;
       int indexOriginal;
   
       // Surcharge de l'opérateur < pour une comparaison stable
       bool operator<(const ElementIndexe& autre) const {
           if (valeur == autre.valeur) {
               return indexOriginal < autre.indexOriginal; // Maintient l'ordre original
           }
           return valeur < autre.valeur;
       }
   };
   
   void triStableGenerique(std::vector<int>& arr) {
       int n = arr.size();
       std::vector<ElementIndexe> elementsIndexe(n);
   
       // Initialise les éléments indexés
       for (int i = 0; i < n; ++i) {
           elementsIndexe[i] = {arr[i], i};
       }
   
       // Utilise n'importe quel algorithme de tri (même potentiellement instable)
       // std::sort est souvent un Introsort, qui est instable pour les paires
       // mais devient stable grâce à notre opérateur de comparaison.
       std::sort(elementsIndexe.begin(), elementsIndexe.end());
   
       // Copie les valeurs triées dans le tableau original
       for (int i = 0; i < n; ++i) {
           arr[i] = elementsIndexe[i].valeur;
       }
   }
   
   

2. Modifier la Logique de Comparaison/Partitionnement : Pour des algorithmes comme le tri rapide, une partition à trois voies peut être implémentée pour gérer les éléments égaux de manière à préserver la stabilité (bien que la version standard du tri rapide à trois voies ne soit pas intrinsèquement stable, des ajsutements sont nécessaires).

   // Exemple conceptuel pour une modification interne du tri rapide
   void triRapideStablePartiel(std::vector<int>& arr, int debut, int fin) {
       if (debut >= fin) return;
   
       int pivot = arr[debut];
       int i = debut + 1;
       int j = fin;
   
       // Déplace les éléments < pivot à gauche, > pivot à droite
       // Conserve les éléments = pivot au centre temporairement
       while (i <= j) {
           while (i <= j && arr[i] < pivot) i++;
           while (i <= j && arr[j] > pivot) j--;
           if (i <= j) {
               std::swap(arr[i], arr[j]);
               i++; j--;
           }
       }
   
       // Après cette phase, tous les éléments < pivot sont à gauche de j,
       // tous les éléments > pivot sont à droite de i.
       // Les éléments entre j+1 et i-1 sont potentiellement égaux au pivot ou non encore déplacés.
       // Pour une vraie stabilité, une phase de fusion ou des règles d'échange plus strictes sont nécessaires.
       // L'échange du pivot avec arr[j] pourrait briser la stabilité si arr[j] est égal au pivot.
       std::swap(arr[debut], arr[j]);
   
       triRapideStablePartiel(arr, debut, j - 1); // Trie la partie gauche
       triRapideStablePartiel(arr, j + 1, fin); // Trie la partie droite
   }
   
   

Applications Pratiques de la Stabilité

La stabilité est une propriété précieuse dans plusieurs contextes :

1. Tri Multi-critères : Lorsque les données doivent être triées sur plusieurs colonnes (par exemple, trier par ville, puis par nom). Si un tri stable est utilisé pour la clé principale après un tri sur une clé secondaire, l'ordre de la clé secondaire est conservé pour les éléments ayant la même clé principale.
2. Conservation de l'Ordre Utilisateur : Dans les interfaces utilisateur, si des éléments ont la même priorité, il est souvent souhaitable de conserver l'ordre dans lequel l'utilisateur les a saisis ou visualisés, améliorant ainsi l'expérience utilisateur.
3. Rapports et Visualisations : Pour des données groupées, la stabilité peut garantir une présentation cohérente où l'ordre interne des groupes n'est pas aléatoirement perturbé.

Implémentations des Bibliothèques de Tri Modernes

Les bibliothèques de tri industrielles emploient souvent des stratégies hybrides pour maximiser la performance et la robustesse, combinant les forces de différents algorithmes :

• Tri par Insertion pour les Petits Ensembles : Pour les tableaux de petite taille (en dessous d'un seuil typique de 7 à 64 éléments), le tri par insertion est privilégié. Sa surcharge est minime, et son adaptativité le rend très rapide pour les données déjà presque triées. Il évite la surcharge des appels récursifs pour de très petits problèmes.
• Tri Fusion et ses Variantes : Le tri fusion est valorisé pour sa complexité temporelle garantie de O(n log n) et sa stabilité. Il est souvent la base d'implémentations stables (comme std::stable_sort en C++). Des variantes comme TimSort (utilisé par Java et Python) améliorent le tri fusion en identifiant et en fusionnant intelligemment les séquences déjà triées ("runs") présentes dans les données, ce qui le rend très performant sur de nombreux jeux de données réels.
• Tri Rapide (Introsort) : Pour des performances moyennes optimales, le tri rapide est souvent le choix par défaut (comme std::sort en C++). Pour atténuer son pire cas de O(n²), les implémentations modernes utilisent souvent l'Introsort, une approche hybride qui commence par un tri rapide. Si la profondeur de récursion devient trop importante (indiquant un risque de pire cas), elle bascule vers un tri par tas pour garantir une complexité O(n log n). Pour les très petits sous-tableaux, elle bascule vers le tri par insertion.
• Pourquoi d'autres algorithmes sont moins courants dans les implémentations génériques :
  • Tri par Tas : Bien que O(n log n) et en place, il a une constante multiplicative plus élevée et une mauvaise localité de référence, le rendant souvent plus lent en pratique que le tri rapide ou fusion.
  • Tri par Base/Comptage : Très rapides (O(n)) pour des types spécifiques (entiers dans une plage limitée), mais non génériques et nécessitent une mémoire auxiliaire importante.

En résumé, les bibliothèques de tri de production utilisent des combinaisons astucieuses d'algorithmes pour offrir le meilleur des mondes : des performances rapides sur des données variées, une garantie de complexité dans le pire des cas, et la stabilité lorsque c'est requis.