Tri rapide à deux voies

L'algorithme de tri rapide à deux voies est une version améliorée du tri rapide aléatoire. Le processus de partition utilise deux valeurs d'index (i, j) pour parcourir le tableau, en plaçant<vles éléments à gauche de la position pointée par l'index i, et en plaçant>vles éléments à droite de la position pointée par l'index j,vReprésente la valeur de calibration.

Applicabilité

La complexité temporelle et spatiale est la même que celle du tri rapide aléatoire. Pour les tableaux comportant de nombreux éléments en double, utiliser le tri rapide aléatoire de la section précédente est très inefficace, car les longueurs des sous-tableaux après la partition pour les données supérieures ou inférieures au pivot deviennent extrêmement déséquilibrées, et il peut même dégénérer en un algorithme avecO(n*2)complexité temporelle. Pour cette situation, l'algorithme de tri rapide à deux voies peut être utilisé.

Diagramme du processus

Utilisez deux valeurs d'index (i, j) pour parcourir notre séquence, en plaçant<=vles éléments à gauche de la position pointée par l'index i, et en plaçant>=vles éléments à droite de la position pointée par l'index j, en équilibrant les sous-tableaux gauche et droit.

Exemple de code Java

Téléchargement du paquet de code source :Télécharger

Code du fichier QuickSort2Ways.java :

package example;

/**
* Tri rapide à deux voies
 */
public class QuickSort2Ways {

    // Code principal --- début
    private static int partition(Comparable[] arr, int l, int r){
        // Sélectionne aléatoirement une valeur comme pivot dans la plage arr[l...r]
        swap( arr, l , (int)(Math.random()*(r-l+1))+l );
        Comparable v = arr[l];
        // arr[l+1...i) <= v; arr(j...r] >= v
        int i = l+1, j = r;
        while( true ){
            while( i <= r && arr[i].compareTo(v) < 0 )
                i ++;
            while( j >= l+1 && arr[j].compareTo(v) > 0 )
                j --;
            if( i > j )
                break;
            swap( arr, i, j );
            i ++;
            j --;
        }
        swap(arr, l, j);
        return j;
    }
    // Code principal --- fin

    // Utiliser récursivement le tri rapide pour trier la plage arr[l...r]
    private static void sort(Comparable[] arr, int l, int r){
        if (l >= r) {
            return;
        }
        int p = partition(arr, l, r);
        sort(arr, l, p-1 );
        sort(arr, p+1, r);
    }

    public static void sort(Comparable[] arr){

        int n = arr.length;
        sort(arr, 0, n-1);
    }

    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // Test de QuickSort
    public static void main(String[] args) {

        // L'algorithme de tri rapide bidirectionnel est aussi un algorithme de complexité O(nlogn)
        // Peut facilement traiter des données de l'ordre de 1 million en 1 seconde

        // Le tri rapide est aussi un algorithme de complexité O(n log n)
        // Peut facilement traiter des données de l'ordre de 1 million en 1 seconde
        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        sort(arr);
        SortTestHelper.printArray(arr);

    }
}

Explication détaillée du principe de l'algorithme

Le cœur du tri rapide bidirectionnel réside dans saméthode de partitionnement à deux pointeursContrairement au tri rapide unidirectionnel (qui ne balaie qu'à partir d'une extrémité), il utilise deux pointeurs qui parcourent depuis la tête et la queue du sous-tableau à trier vers le milieu, garantissant que les éléments égaux ne soient pas tous repoussés d'un seul côté.

Cœur : le processus de partitionnement bidirectionnel

Supposons que nous voulions trier le tableauarrindice du milieu à partir deleftàrightportion.

Sélectionner la valeur pivot: parmiarr[left...right]Sélectionner aléatoirement un élément de celui-ci comme valeur pivotpivotLa randomisation est utilisée pour éviter le pire cas sur les tableaux triés.

Initialiser les pointeurs：

  • i = left + 1Un pointeur parcourant de gauche à droite, à la recherche du premiersupérieur ou égal à pivotéléments.
  • j = rightUn pointeur parcourant de droite à gauche, à la recherche du premierinférieur ou égal à pivotéléments.

Boucle de balayage et d'échange：

  • whileLa boucle, avec la condition étanti <= j。
  • internewhileboucle : letiContinuer à se déplacer vers la droite jusqu'àarr[i] >= pivot。
  • internewhileboucle : letjContinuez à vous déplacer vers la gauche jusqu'àarr[j] <= pivot。
  • À ce stade,arr[i]est un élément "grand" qui ne devrait pas être dans la moitié gauche,arr[j]est un élément "petit" qui ne devrait pas être dans la moitié droite.
  • Si à ce stadei <= j, alors échangezarr[i]etarr[j], puisi++, j--puis continuez la boucle externe.

Placez la valeur du pivot et renvoyez le point de partition：

  • Après la fin de la boucle,ietjdéjà croisés (j < i). À ce stadearr[left](c'est-à-dire le pivot) doit être placé à la bonne position.
  • vaarr[left]etarr[j]échanger. Parce quejLa position où il s'arrête finalement, et l'élément vers lequel il pointe estle dernier élément inférieur ou égal à la valeur du pivotéléments.
  • returnjcomme le nouveau point de partition. À ce stade,arr[left...j-1] <= pivot，arr[j+1...right] >= pivot, etarr[j] == pivot。

trier récursivement

obtenir le point de partitionpAprès cela, pour le sous-tableau de gauchearr[left...p-1]et le sous-tableau de droitearr[p+1...right]Répétez le processus ci-dessus de manière récursive jusqu'à ce que la longueur du sous-tableau soit 1.

Implémentation du code

Comprenons concrètement le tri rapide bidirectionnel grâce à une implémentation Java complète.

1. Fonction de tri principale

Exemple

public class TwoWayQuickSort {

    // Interface publique de tri
    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return; // Gérer le cas limite : le tableau est vide ou ne contient qu'un seul élément, aucun tri nécessaire
        }
        quickSort(arr, 0, arr.length - 1); // Appeler la fonction récursive de tri rapide
    }

    // Fonction récursive de tri rapide
    private static void quickSort(int[] arr, int left, int right) {
        // Condition d'arrêt de la récursion : lorsque left >= right, le sous-tableau est déjà trié ou vide
        if (left >= right) {
            return;
        }
       
        // Étape clé : effectuer un partitionnement bidirectionnel et renvoyer l'indice de partition
        int p = partition(arr, left, right);
       
        // Trier récursivement la moitié gauche (left, p-1)
        quickSort(arr, left, p - 1);
        // Trier récursivement la moitié droite (p+1, right)
        quickSort(arr, p + 1, right);
    }
}

2. Cœur : fonction de partitionnement à deux voies

C'est le cœur de l'algorithme. Veuillez le comprendre attentivement avec l'organigramme et les commentaires ci-dessus.

Exemple

    // Fonction de partitionnement à deux voies
    private static int partition(int[] arr, int left, int right) {
        // 1. Sélectionner aléatoirement un pivot et le permuter vers la position de gauche, en évitant le pire cas sur les tableaux triés
        int randomIndex = left + (int)(Math.random() * (right - left + 1));
        swap(arr, left, randomIndex);
        int pivot = arr[left]; // Valeur du pivot
       
        // 2. Initialiser les deux pointeurs
        // i : parcourir de gauche à droite, à la recherche d'éléments >= pivot
        // j : parcourir de droite à gauche, à la recherche d'éléments <= pivot
        int i = left + 1;
        int j = right;
       
        // 3. Boucle principale : tant que i et j ne se sont pas croisés
        while (i <= j) {
            // 3.1 Déplacer le pointeur gauche i : trouver le premier élément >= pivot
            // Remarque : borne i <= right pour éviter un dépassement de tableau
            while (i <= right && arr[i] < pivot) {
                i++;
            }
            // 3.2 Déplacer le pointeur droit j : trouver le premier élément <= pivot
            // Remarque : la borne j >= left+1, car la position de gauche est le pivot lui-même
            while (j >= left + 1 && arr[j] > pivot) {
                j--;
            }
           
            // 3.3 Vérifier l'état des pointeurs
            // Si i > j, le balayage est terminé, les partitions gauche et droite sont prêtes, aucun échange nécessaire
            if (i > j) {
                break;
            }
           
            // 3.4 Échanger arr[i] et arr[j]
            // Maintenant arr[i] >= pivot, arr[j] <= pivot, échangez-les pour que les éléments des deux côtés soient à leur place
            swap(arr, i, j);
            // Après l'échange, déplacez les pointeurs pour continuer le balayage
            i++;
            j--;
        }
       
        // 4. Placer le pivot à sa position finale correcte j
        // Après la fin de la boucle, j pointe vers le dernier élément <= pivot
        swap(arr, left, j);
       
        // 5. Retourner l'indice j du point de partition
        return j;
    }
   
    // Fonction auxiliaire : échanger les positions de deux éléments dans un tableau
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

3. Tests et vérification

Testons notre implémentation avec un tableau contenant des éléments en double.

Exemple

public class Main {
    public static void main(String[] args) {
        // Cas de test 1 : tableau contenant de nombreux éléments en double
        int[] arr1 = {4, 2, 2, 8, 3, 3, 1, 5, 3, 2};
        System.out.println("Avant le tri : " + Arrays.toString(arr1));
        TwoWayQuickSort.sort(arr1);
        System.out.println("Après le tri : " + Arrays.toString(arr1));
       
        // Cas de test 2 : grand tableau généré aléatoirement
        int[] arr2 = new int[20];
        Random rand = new Random();
        for (int i = 0; i < arr2.longueur; i++) {
            arr2[i] = rand.nextInt(50); // Générer des nombres aléatoires de 0-49, doublons probables
        }
        System.out.println("\n"Avant le tri du tableau aléatoire : " + Arrays.toString(arr2));
        TwoWayQuickSort.sort(arr2);
        System.out.println("Après le tri du tableau aléatoire : " + Arrays.toString(arr2));
       
        // Vérifier si le résultat du tri est correct
        for (int i = 1; i < arr2.longueur; i++) {
            if (arr2[i] < arr2[i-1]) {
                System.out.println("Erreur de tri !");
                return;
            }
        }
        System.out.println("Vérification du résultat du tri réussie !");
    }
}

Exemple de sortie de données de test：

排序前: [4, 2, 2, 8, 3, 3, 1, 5, 3, 2]
排序后: [1, 2, 2, 2, 3, 3, 3, 4, 5, 8]

随机数组排序前: [17, 33, 12, 48, 8, 2, 41, ...]
随机数组排序后: [2, 8, 12, 17, 33, 33, 41, 48, ...]
排序结果验证通过！

Analyse et comparaison des algorithmes

Complexité temporelle

  • Cas moyen: $O(n \log n)$. Le tri rapide à deux voies maintient l'arbre de récursion relativement équilibré en répartissant uniformément les éléments en double.
  • Pire cas: $O(n^2)$. Bien que la sélection aléatoire du pivot réduise grandement la probabilité, le pire cas peut encore se produire lorsque chaque partition est extrêmement déséquilibrée (par exemple, lorsque le pivot est toujours la valeur minimale ou maximale actuelle).
  • Meilleur cas: $O(n \log n)$. Chaque partition divise le tableau de manière équilibrée.

Complexité spatiale

  • Il s'agit principalement de l'espace occupé par la pile des appels récursifs.
  • La profondeur moyenne est $O(\log n)$, et la profondeur dans le pire cas est $O(n)$.
  • Par conséquent,La complexité spatiale moyenne est $O(\log n)$, et celle dans le pire cas est $O(n)$.。

Stabilité

Le tri rapide (y compris le tri rapide à deux voies) n'est pas un algorithme de tri stable, car pendant le partitionnement, les échanges d'éléments non adjacents peuvent perturber l'ordre relatif d'origine des éléments égaux.

Comparaison des tris rapides à une, deux et trois voies

Fonctionnalités Tri rapide à une voie (Lomuto) Tri rapide à deux voies Tri rapide à trois voies
Méthode de partition Un pointeur unique balaie de gauche à droite Deux pointeurs balaient depuis les deux extrémités vers le milieu Trois pointeurs, divisant le tableau en<pivot, =pivot, >pivotTrois parties
Gestion des éléments en double Médiocre, peut conduire à un partitionnement déséquilibré Bon, peut répartir uniformément les éléments en double Optimal, peut traiter d'un coup tous les éléments égaux au pivot
Complexité du code Simple Moyenne Légèrement complexe
Scénarios applicables Pédagogique, aucun/peu d'éléments en double Usage général, particulièrement adapté aux scénarios où des éléments en double peuvent exister Scénarios avec un grand nombre d'éléments en double

Plus d'exemples de code

autres extensions