Le tri rapide (QuickSort) est un algorithme de tri fondamental en informatique, développé par C. A. R. Hoare en 1960. Cet algorithme repose sur le principe de diviser pour régner, partitionnant les données puis triant récursivement chaque sous-groupe jusqu'à obtenir une séquence entièrement ordonnée.

Principe fondamental

L'essence du tri rapide consiste à sélectionner un élément pivot dans la séquence à trier, puis à réorganiser les éléments de manière à placer tous ceux inférieurs au pivot à sa gauche et tous ceux supérieurs à sa droite. Cette opération positionne correctement le pivot dans son emplacement final, après quoi l'algorithme s'applique récursivement aux sous-séquences gauche et droite.

Processus de tri

L'algorithme effectue des comparaisons et échanges multiples pour atteindre l'ordre final :

1. Sélection du pivot : Choisir un élément comme référence pour la partition.
2. Opération de partitionnement : Diviser la séquence en deux parties distinctes où une partie contient uniquement des valeurs inférieures à celles de l'autre partie, puis appliquer le même processus récursivement.
3. Triage récursif : Appliquer les mêmes opérations aux sous-séquences gauche et droite du pivot jusqu'à ce que leur longueur soit de 1 ou 0.

Étapes détaillées

Considérons un tableau comme exemple, les étapes précises sont :

1. Initialisation des pointeurs : Définir deux pointeurs start et end pointant respectivement vers le début et la fin de la séquence.
2. Choix du pivot : Séletcionner l'élément initial comme pivot, ou adopter d'autres stratégies.
3. Partitionnement :
   • Parcourir de droite à gauche (end--) pour trouver le premier élément inférieur au pivot, puis l'échanger avec l'élément à start.
   • Parcourir de gauche à droite (start++) pour trouver le premier élément supérieur au pivot, puis l'échanger avec l'élément à end.
   • Répéter jusqu'à ce que start et end se rencontrent, plaçant ainsi le pivot à sa position finale.
4. Récursion : Appliquer le tri rapide aux sous-séquences situées de part et d'autre du pivot.

Analyse des performances

• Complexité temporelle : La complexité moyenne est O(n log n), mais dans le pire cas (séquence déjà ordonnée), elle dégénère à O(n²) principalement due à un choix inapproprié du pivot.
• Complexité spatiale : Elle dépend de la profondeur de récursion. Dans le meilleur cas, la profondeur est log n, donnant une complexité spatiale de O(log n). Dans le pire cas, elle peut atteindre O(n). Le tri rapide étant en place, l'espace supplémentaire est principalement dû à la pile de récursion.

Points d'attention

• Le tri rapide n'est pas stable, donc des éléments identiques peuvent changer de position relative après tri.
• Les performances dépendent fortement de la stratégie de sélection du pivot.

Amélioration par sélection aléatoire du pivot

Dans le tri rapide, la stratégie de sélection du pivot influence considérablement les performances. Les implémentations traditionnelles choisissent souvent le premier, dernier ou élément médian, mais ces approches peuvent conduire à une dégradation O(n²) dans certains cas (séquences partiellement ordonnées).

Pour éviter cela, une méthode courante consiste à choisir le pivot aléatoirement, réduisant ainsi significativement la probabilité d'atteindre le pire cas et améliorant les performances moyennes.

Procédure de sélection aléatoire

1. Génération d'un index aléatoire : Créer un nombre aléatoire entre 0 et n-1 (où n est la longueur de la séquence).
2. Sélection du pivot : Échanger l'élément à l'index aléatoire avec un élément fixe (comme le premier ou dernier) pour faciliter la partition.
3. Partitionnement : Réorganiser les éléments autour du pivot sélectionné.
4. Récursion : Appliquer récursivement le processus aux sous-séquences gauche et droite.

Avantages

• Réduction des pires cas : Le choix aléatoire diminue la probabilité de partitions déséquilibrées.
• Meilleure stabilité moyenne : Les performances moyennes deviennent plus robustes face aux variations des données d'entrée.

Considérations importantes

• Qualité du générateur : Assurer un bon générateur aléatoire pour éviter les séquences prévisibles.
• Complexité d'implémentation : L'aléa ajoute de la complexité, particulièrement dans les versions parallèles.
• Compromis mémoire-performance : Les opérations supplémentaires pour générer des nombres aléatoires et échanger des éléments introduisent un coût minimal compensé par les gains de performance.

Problème 912 : Trier un tableau

Étant donné un tableau d'entiers tableau, triez-le par ordre croissant.

Exemple 1 :

<strong>Entrée :</strong>tableau = [5,2,3,1]
<strong>Sortie :</strong>[1,2,3,5]

Exemple 2 :

<strong>Entrée :</strong>tableau = [5,1,1,2,0,0]
<strong>Sortie :</strong>[0,0,1,1,2,5]

Contraintes :

• 1 <= tableau.length <= 5 * 10⁴
• -5 * 10⁴ <= tableau[i] <= 5 * 10⁴

Lorsque le premier élément est utilisé comme pivot, le code échoue (délai dépassé)

class Solution {
public:
    void triRapide(vector<int>& tableau, int debut, int fin) {
        if (debut < fin) {
            int gauche = debut, droite = fin;
            int pivot = tableau[gauche];
            
            while (gauche < droite) {
                while (gauche < droite && tableau[droite] >= pivot) droite--;
                while (gauche < droite && tableau[gauche] <= pivot) gauche++;
                if (gauche < droite) {
                    swap(tableau[gauche], tableau[droite]);
                }
            }
            swap(tableau[gauche], tableau[debut]);
            triRapide(tableau, debut, droite - 1);
            triRapide(tableau, gauche + 1, fin);
        }
    }
    
    vector<int> trierTableau(vector<int>& tableau) {
        int debut = 0;
        int fin = tableau.size() - 1;
        triRapide(tableau, debut, fin);
        return tableau;
    }
};

Avec pivot choisi aléatoirement, le code passe

class Solution {
public:
    void triRapide(vector<int>& tableau, int debut, int fin) {
        if (debut < fin) {
            int gauche = debut, droite = fin;
            int aleatoire = rand() % (droite - gauche + 1) + gauche;
            swap(tableau[debut], tableau[aleatoire]);
            int pivot = tableau[debut];
            
            while (gauche < droite) {
                while (gauche < droite && tableau[droite] >= pivot) droite--;
                while (gauche < droite && tableau[gauche] <= pivot) gauche++;
                if (gauche < droite) {
                    swap(tableau[gauche], tableau[droite]);
                }
            }
            swap(tableau[gauche], tableau[debut]);
            triRapide(tableau, debut, droite - 1);
            triRapide(tableau, gauche + 1, fin);
        }
    }
    
    vector<int> trierTableau(vector<int>& tableau) {
        int debut = 0;
        int fin = tableau.size() - 1;
        srand(time(nullptr)); // Initialiser le générateur aléatoire
        triRapide(tableau, debut, fin);
        return tableau;
    }
};