Cet article développe une implémentation courante de l'algorithme de tri rapide, en se concentrant sur sa stratégie principale de ? partitionnement sur place ?. En sélectionnant une valeur pivot et en utilisant des techniques de double pointeur pour diviser le tableau en régions inférieures, égales et supérieures à la valeur pivot, la valeur pivot est finalement placée à sa position triée finale. L'algorithme trie ensuite les sous-tableaux gauche et droit de manière récursive, ce qui permet d'obtenir un tri global efficace.

Introduction?: aper?u du tri rapide

QuickSort est un algorithme de tri efficace basé sur la comparaison proposé par CAR Hoare en 1960. Il adopte l'idée de ??Divide and Conquer??. Son principe est de diviser les données à trier en deux parties indépendantes grace à un seul tri. Toutes les données d'une partie sont plus petites que toutes les données de l'autre partie. Les deux parties des données sont ensuite rapidement triées de cette manière. L'ensemble du processus de tri peut être effectué de manière récursive, de sorte que l'ensemble des données devienne une séquence ordonnée.

Les principales étapes du tri rapide comprennent?:

1. Sélection pivot?: sélectionnez un élément du tableau comme valeur pivot.
2. Partitionnement?: réorganisez le tableau de sorte que tous les éléments plus petits que la valeur pivot soient déplacés vers la gauche de la valeur pivot et que tous les éléments supérieurs à la valeur pivot soient déplacés vers la droite de la valeur pivot. Au cours de ce processus, la valeur de base est déplacée vers sa position de tri finale.
3. Tri récursif?: triez de manière récursive et rapide les sous-tableaux sur les c?tés gauche et droit de la valeur de référence.

Mécanisme de base?: partitionnement sur place

L'opération de partitionnement est l'ame de l'algorithme de tri rapide. L'objectif est de choisir une valeur pivot et, grace à une série d'opérations d'échange, de diviser le tableau en deux parties?: l'une contenant tous les éléments inférieurs à la valeur pivot, et l'autre contenant tous les éléments supérieurs à la valeur pivot, et de placer la valeur pivot dans sa position correcte dans le tableau trié final. Cet article présentera une stratégie courante de partitionnement sur place, mise en ?uvre à l'aide de la technologie à double pointeur.

Explication détaillée de la fonction de partition?: getPivotIndex

La fonction getPivotIndex effectue l'opération de partitionnement réelle et renvoie l'index final de la valeur pivot dans le sous-tableau trié.

1. Sélection de la valeur pivot?: dans cette implémentation, nous sélectionnons simplement le premier élément arg[startIndex] du sous-tableau actuel comme valeur pivot (pivotVal). Bien que cette méthode de sélection soit simple, elle peut entra?ner une dégradation des performances dans certains cas (par exemple lorsque le tableau est partiellement ordonné ou inversé).
2. Initialisation du double pointeur?:
   • Le pointeur gauche i est initialisé à startIndex.
   • Le pointeur droit j est initialisé à endIndex (remarque?: endIndex est une limite exclusive).
3. Logique de traversée et d'échange : la boucle while (i
4. Le pointeur droit j se déplace?: while (i = pivotVal));
   • Le pointeur droit j se déplace de droite à gauche (en se décrémentant d'abord), à la recherche du premier élément plus petit que pivotVal.
   • Si un élément inférieur à pivotVal est trouvé et que i
5. Le pointeur gauche i se déplace : while (i
6. Le pointeur gauche i se déplace de gauche à droite (en incrémentant d'abord), à la recherche du premier élément supérieur à pivotVal.
7. Si un élément supérieur à pivotVal est trouvé et que i
8. Ce processus se poursuit jusqu'à ce que i et j se rencontrent ou se croisent. Lorsqu'ils se rencontreront, i et j indiqueront l'emplacement final correct de la donnée.
9. Retour de la valeur de référence?: une fois la boucle terminée, la position où i et j se rencontrent est la position finale correcte de la valeur de référence. Nous pla?ons le pivotVal initialement sélectionné dans arg[j].
10. Renvoie l'index de la valeur de base : La fonction renvoie j comme index final de la valeur de base. à l'heure actuelle, tous les éléments du c?té gauche de arg[j] sont inférieurs ou égaux à pivotVal, et tous les éléments du c?té droit sont supérieurs ou égaux à pivotVal.

Fonction de tri principale?: quickSort

La fonction quickSort est le point d'entrée pour le tri rapide et est responsable de la gestion des appels récursifs.

1. Condition de base récursive?: if (endIndex - startIndex
2. Lorsque la longueur du sous-tableau est inférieure à 2 (c'est-à-dire que le sous-tableau ne contient que 0 ou 1 élément), cela signifie que le sous-tableau est déjà ordonné et ne peut pas être partitionné. Il s'agit de la condition de terminaison de la récursivité et du retour direct.
3. Appel de partition : int pivotIndex = getPivotIndex(arg, startIndex, endIndex);
   • Appelez la fonction getPivotIndex pour partitionner le sous-tableau actuel et obtenir l'index de position finale de la valeur de référence dans le tableau.
4. Appel récursif :
   • quickSort(arg, startIndex, pivotIndex);?: trier de manière récursive le sous-tableau à gauche de la valeur pivot (de startIndex à pivotIndex, à l'exclusion de la valeur pivot à pivotIndex).
   • quickSort(arg, pivotIndex 1, endIndex);?: trier de manière récursive le sous-tableau sur le c?té droit de la valeur pivot (de pivotIndex 1 à endIndex, à l'exclusion de endIndex).

Exemple de code complet (Java)

Voici l'implémentation Java complète de l'algorithme de tri rapide ci-dessus?:

 classe publique QuickSort_Impl {

    public static void main (String[] arguments) {
        int[] unsortedArray = {12, 3, 45, 23, 6, -4, -6, 10, 1, 8}?;

        System.out.println("Tableau d'origine?:");
        pour (int i?:?unsortedArray)
            System.out.print(i " ");
        System.out.println();

        // Appelez le tri rapide pour trier l'ensemble du tableau // endIndex utilise la longueur du tableau car il s'agit d'un quickSort exclusif (unsortedArray, 0, unsortedArray.length);

        System.out.println("tableau trié?:");
        pour (int i?:?unsortedArray)
            System.out.print(i " ");
        System.out.println();
    }

    /**
     * La fonction principale de tri rapide utilise la stratégie diviser pour régner pour trier le tableau.
     * @param arg Tableau à trier * @param startIndex Index de départ du sous-tableau (inclus)
     * @param endIndex L'index de fin du sous-tableau (non inclus)
     */
    static void quickSort(int[] arg, int startIndex, int endIndex) {
        // Condition de base récursive?: si la longueur du sous-tableau est inférieure à 2, aucun partitionnement supplémentaire n'est requis et il est renvoyé directement.
        // Par exemple, il ne reste qu'un seul élément ou aucun élément.
        si (endIndex - startIndex = pivotVal));
            // S'il est trouvé, déplace l'élément vers la position pointée par i.
            si (i <h3> Analyse des performances et précautions</h3><ol>
<li> <strong>Complexité temporelle</strong> :<ul>
<li> <strong>Cas moyen</strong> : O(n log n). Il s’agit de la manifestation de performance la plus courante du tri rapide et elle est très efficace.</li>
<li> <strong>Dans le pire des cas</strong> : O(n^2). Lorsque la valeur de base est mal sélectionnée, ce qui entra?ne un sous-tableau vide pour chaque partition (par exemple, en sélectionnant à chaque fois l'élément le plus grand ou le plus petit comme valeur de base, alors que le tableau est déjà trié ou inversé), les performances du tri rapide se dégraderont pour ressembler à celles du tri à bulles.</li>
</ul>
</li>
<li> <strong>Complexité spatiale</strong> :<ul>
<li> <strong>Cas moyen</strong> : O(log n). Cela dépend principalement de la profondeur de pile de l'appel récursif.</li>
<li> <strong>Dans le pire des cas</strong> : O(n). Dans le pire des cas, la profondeur de récursion peut atteindre n.</li>
</ul>
</li>
<li> <strong>Sélection de la valeur de base</strong>?:<ul>
<li> Le choix de la valeur de référence est essentiel à la performance du tri rapide. Dans cet exemple, le premier élément est sélectionné comme valeur de base, ce qui peut conduire au pire des cas pour certaines entrées.</li>
<li> <strong>Les stratégies d'optimisation</strong> comprennent?:<ul>
<li> <strong>Sélection aléatoire</strong>?: la sélection aléatoire d'un élément comme valeur de base peut effectivement éviter le pire des cas.</li>
<li> <strong>Méthode médiane à trois nombres</strong>?: sélectionnez le premier, le milieu et le dernier éléments du sous-tableau et prenez leur médiane comme valeur de base. Cela conduit généralement à un meilleur choix d’une valeur de base ? moyenne ?.</li>
</ul>
</li>
</ul>
</li>
<li> <strong>Stabilité</strong> : Quicksort n’est généralement pas un algorithme de tri stable. Cela signifie que l'ordre relatif des éléments ayant la même valeur peut changer après le tri.</li>
<li> <strong>Comparaison avec la partition Lomuto/Hoare</strong> :<ul>
<li> La stratégie de partitionnement mise en ?uvre dans cet article est courante et efficace dans le tri rapide, et son c?ur est de placer la valeur de référence à la position finale. Elle est similaire à la méthode de partitionnement Lomuto dans la mesure où elle complète le partitionnement et détermine la position de base en un seul parcours.</li>
<li> Le partitionnement Hoare est un autre schéma de partitionnement classique, généralement considéré comme plus efficace en pratique que le partitionnement Lomuto car il nécessite moins d'échanges. La méthode de partitionnement Hoare ne garantit pas que la valeur pivot finira dans sa position de tri précise, mais elle garantit que les éléments à gauche de la valeur pivot sont inférieurs ou égaux à la valeur pivot, et les éléments à droite sont supérieurs ou égaux à la valeur pivot.</li>
</ul>
</li>
</ol><h3> Résumer</h3><p> Le tri rapide est un tri puissant et largement utilisé</p>

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!