Algorithme de tri à trois voies

L'algorithme de tri à trois voies(partitionnement à trois voies) est une variante spéciale du tri rapide, optimisée spécifiquement pour les tableaux contenant de nombreux éléments en double. Son idée centrale est de diviser le tableau en trois parties en une seule passe de partitionnement, plutôt qu'en deux parties traditionnelles.

Le tri rapide à trois voies est une version encore améliorée du tri rapide à deux voies. L'algorithme de tri à trois voies divise les données à trier en trois parties : inférieures à v, égales à v et supérieures à v, où v est le pivot. Ainsi, parmi les trois parties, les données égales à v n'ont plus besoin d'être triées dans la récursion suivante, et les données inférieures à v ou supérieures à v ne se retrouveront pas dans une situation où un côté est particulièrement grand. Avec cette approche, l'algorithme de tri rapide à trois voies offre de meilleures performances.

Imaginez que vous avez un grand seau de billes de trois couleurs mélangées : rouge, blanc et bleu. Votre tâche est de les séparer rapidement pour que toutes les billes rouges soient à gauche, les blanches au milieu et les bleues à droite. L'algorithme de partitionnement à trois voies est le maître du tri pour résoudre ce genre de problème.

Tri rapide traditionnel vs tri rapide à trois voies

Utilisons un tableau simple pour comparer les différences entre les deux :

Fonctionnalités Tri rapide traditionnel Tri rapide à trois voies
Nombre de partitions 2 (inférieur au pivot, supérieur au pivot) 3 (inférieur au pivot, égal au pivot, supérieur au pivot)
Gestion des éléments en double Moins efficace ; les éléments dupliqués peuvent être comparés et échangés plusieurs fois Extrêmement efficace, les éléments dupliqués sont traités ensemble
Complexité temporelle En moyenne O(n log n), dans le pire O(n²) En moyenne O(n log n), dans le pire O(n²)
Complexité spatiale O(log n) (pile de récursion) O(log n) (pile de récursion)
Scénarios applicables Tri polyvalent, faible taux de duplication des éléments Forte duplication des éléments, comme le tri par couleur et la segmentation de scores

Applicabilité

La complexité temporelle et spatiale est la même que celle du tri rapide randomisé.

L'algorithme de tri rapide à trois voies partitionne le tableau à l'aide d'une stratégie de partitionnement à trois voies, qui est très efficace pour les tableaux comportant de nombreux éléments en double et améliore le processus de tri rapide. Il ajoute une logique pour gérer les éléments égaux à la valeur de partition, en regroupant toutes les valeurs égales à l'élément de partition.

Diagramme du processus

Nous discutons du processus de partitionnement en trois cas, où i représente la position d'index de parcours actuelle :

(1) L'élément courant e = V est directement placé dans l'intervalle bleu, et i se déplace d'une position vers la droite.

(2) L'élément courant e < v : échangez e avec la valeur à la première position de l'intervalle des éléments égaux à V, et déplacez à la fois lt et i d'une position vers la droite.

(3) L'élément courant e > v : échangez e avec la valeur à l'index gt-1, et déplacez l'index gt d'une position vers la gauche.

Enfin, lorsquei=gtLorsque le parcours se termine, échangez v avec la valeur pointée par l'index lt, et cela termine le processus de partitionnement. Ensuite, utilisez la même méthode pour trier récursivement les parties <V et >V.

Exemple de code Java

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

Code du fichier QuickSort3Ways.java :

package example;

/**
* Tri rapide à trois voies
 */
public class QuickSort3Ways {
    // Code principal --- début
    // 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;
        }
        // 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];
        int lt = l;     // arr[l+1...lt] < v
        int gt = r + 1; // arr[gt...r] > v
        int i = l+1;    // arr[lt+1...i) == v
        while( i < gt ){
            if( arr[i].compareTo(v) < 0 ){
                swap( arr, i, lt+1);
                i ++;
                lt ++;
            }
            else if( arr[i].compareTo(v) > 0 ){
                swap( arr, i, gt-1);
                gt --;
            }
            else{ // arr[i] == v
                i ++;
            }
        }
        swap( arr, l, lt );
        sort(arr, l, lt-1);
        sort(arr, gt, r);
    }
    // Code principal --- fin

    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 QuickSort3Ways
    public static void main(String[] args) {

        // L'algorithme de tri rapide à trois voies est aussi un algorithme de complexité O(nlogn)
        // 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);
    }
}

Idée centrale et principe de fonctionnement de l'algorithme

La subtilité de l'algorithme de partitionnement en trois voies réside dans le fait qu'il utilise trois pointeurs pour suivre différentes régions du tableau, ce qui réalise la classification en trois voies en un seul parcours.

État de partitionnement de l'algorithme

Comprenons le processus de partitionnement de l'algorithme à l'aide d'un diagramme d'état :

Description de la figureL'algorithme maintient trois pointeurs (lt, i, gtIl divise le tableau en quatre régions ; au fur et à mesure du traitement, la région non traitée se réduit progressivement, formant finalement trois partitions bien définies.

Rôles des trois pointeurs clés

  1. ltpointeur (inférieur à)Pointe vers la fin de la région inférieure au pivot
  2. ipointeur (actuel)Position de l'élément en cours d'examen
  3. gtpointeur (supérieur à)Pointe vers le début de la région supérieure au pivot

Implémentation Python

Fonction de partitionnement en trois voies de base

Ci-dessous se trouve une implémentation standard de la fonction de partitionnement en trois voies ; nous l'analyserons ligne par ligne :

Exemple

def three_way_partition(arr, low, high):
    """
Effectuer un partitionnement en trois voies sur le tableau arr dans l'intervalle de low à high
   
Paramètres :
arr : Le tableau à partitionner
low : L'indice de début de la partition
high : L'indice de fin de la partition
       
Retourne :
(lt, gt) : Les limites gauche et droite de la région des éléments égaux à la valeur du pivot
    """
    # Choisir le pivot (ici le premier élément est choisi)
    pivot = arr[low]
   
    # Initialiser trois pointeurs
    lt = low      # La limite droite de la région des éléments inférieurs au pivot (initialisée à low)
    i = low + 1   # Position de l'élément courant en cours d'examen
    gt = high     # La frontière gauche de la région supérieure au pivot (initialisée à high)
   
    # Boucle principale : continuer tant qu'il reste des éléments non traités
    while i <= gt:
        if arr[i] < pivot:
            # Cas 1 : L'élément courant est inférieur au pivot
            # Échanger avec l'élément suivant du pointeur lt pour étendre la région des éléments inférieurs au pivot
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            # Cas 2 : L'élément courant est supérieur au pivot
            # Échanger avec l'élément situé au niveau du pointeur gt pour étendre la région des éléments supérieurs au pivot
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
            # Remarque : i n'est pas incrémenté ici car l'élément échangé n'a pas encore été examiné
        else:
            # Cas 3 : l'élément courant est égal au pivot
            # Passer directement, en élargissant la région d'égalité
            i += 1
   
    # Retourner les bornes de la région égale au pivot
    return lt, gt

Implémentation complète du tri rapide à trois voies

En nous basant sur la fonction de partition ci-dessus, nous pouvons implémenter le tri rapide à trois voies complet :

Exemple

def three_way_quicksort(arr, low=0, high=None):
    """
Fonction principale du tri rapide à trois voies
   
Paramètres :
arr : Le tableau à trier
low: L'indice de début pour le tri (par défaut : 0)
high: L'indice de fin pour le tri (par défaut : la fin du tableau)
    """
    if high is None:
        high = len(arr) - 1
   
    # Condition d'arrêt de la récursion : la longueur du sous-tableau est inférieure ou égale à 1
    if low >= high:
        return
   
    # Effectuer un partitionnement en trois voies
    lt, gt = three_way_partition(arr, low, high)
   
    # Trier récursivement la partie inférieure au pivot
    three_way_quicksort(arr, low, lt - 1)
   
    # Trier récursivement la partie supérieure au pivot
    three_way_quicksort(arr, gt + 1, high)
   
    # Remarque : la partie égale au pivot est déjà à sa position correcte, il n'est pas nécessaire de trier davantage

Exemples d’application pratique

Exemple 1 : problème de tri des couleurs

Il s'agit d'un scénario d'application classique de l'algorithme de partitionnement en trois voies, également connu sous le nom de « problème du drapeau néerlandais ».

Exemple

def sort_colors(colors):
    """
Tri des couleurs : organiser un tableau contenant uniquement 0 (rouge), 1 (blanc), 2 (bleu) dans l'ordre
   
Paramètres :
colors: Le tableau de couleurs, les éléments sont 0, 1, 2
       
Retourne :
Le tableau de couleurs trié
    """
    # Initialiser trois pointeurs
    red_ptr = 0          # La fin de la région rouge
    white_ptr = 0        # La position actuelle examinée (aussi la fin de la région blanche)
    blue_ptr = len(colors) - 1  # Le début de la région bleue
   
    while white_ptr <= blue_ptr:
        if colors[white_ptr] == 0:
            # Rouge : échanger vers la région rouge
            colors[red_ptr], colors[white_ptr] = colors[white_ptr], colors[red_ptr]
            red_ptr += 1
            white_ptr += 1
        elif colors[white_ptr] == 1:
            # Blanc : reste dans la région du milieu
            white_ptr += 1
        else:
            # Bleu : échanger vers la région bleue
            colors[white_ptr], colors[blue_ptr] = colors[blue_ptr], colors[white_ptr]
            blue_ptr -= 1
            # Remarque : white_ptr n'est pas incrémenté ici car l'élément échangé n'a pas encore été vérifié
   
    return colors

# Données de test
test_colors = [2, 0, 2, 1, 1, 0, 1, 2, 0, 1, 0, 2]
print("Tableau de couleurs d'origine :", test_colors)
print("Tableau de couleurs trié :", sort_colors(test_colors.copy()))

Description des données de testLe tableau ci-dessus représente des codes de couleur (0=rouge, 1=blanc, 2=bleu). Après le tri, tous les 0 doivent être au début, les 1 au milieu et les 2 à la fin.

Exemple 2 : regroupement des scores des étudiants

Supposons que nous devions segmenter les étudiants par score : en dessous de 60, c'est un échec ; de 60 à 80, c'est bien ; et au-dessus de 80, c'est excellent.

Exemple

def categorize_grades(scores):
    """
Classer les scores en trois niveaux : Échec (<60), Bien (60-80), Excellent (>80)
   
Paramètres :
scores : tableau de scores
       
Retourne :
Tableau de scores segmenté
    """
    if not scores:
        return scores
   
    # Utiliser l'idée de partitionnement en trois voies, avec 60 et 80 comme bornes
    # Première partition selon 60 : Échec vs. Réussite ou plus
    low = 0
    mid = 0
    high = len(scores) - 1
   
    # Premier tour : séparer les scores d'échec (<60)
    while mid <= high:
        if scores[mid] < 60:
            scores[low], scores[mid] = scores[mid], scores[low]
            low += 1
            mid += 1
        elif scores[mid] <= 80:
            mid += 1
        else:
            scores[mid], scores[high] = scores[high], scores[mid]
            high -= 1
   
    # Deuxième tour : séparer les bonnes et excellentes notes de la partie à partir de la moyenne
    # À ce stade, low pointe vers la position de la première bonne note
    mid = low
    high = len(scores) - 1
   
    while mid <= high:
        if scores[mid] <= 80:
            mid += 1
        else:
            scores[mid], scores[high] = scores[high], scores[mid]
            high -= 1
   
    return scores

# Données de test
test_scores = [45, 78, 92, 56, 85, 67, 72, 88, 59, 95, 61, 73]
print("Notes originales :", test_scores)
print("Notes segmentées :", categorize_grades(test_scores.copy()))
print("Remarque : première partie <60, partie du milieu 60-80, dernière partie >80")

Analyse de la complexité de l'algorithme

Complexité temporelle

L'analyse de la complexité temporelle de l'algorithme de tri à trois voies peut être exprimée par la formule suivante :

$$ T(n) = O(n) + T(k) + T(n - k - m) $$

Où :

  • $n$ est la longueur du tableau
  • $k$ est le nombre d'éléments inférieurs à la valeur du pivot
  • $m$ est le nombre d'éléments égaux à la valeur du pivot
  • $n - k - m$ est le nombre d'éléments supérieurs à la valeur du pivot

Meilleur casMeilleur cas : Chaque partition peut diviser uniformément le tableau en trois parties, avec une complexité temporelle $O(n \log_3 n)$, qui est en fait toujours $O(n \log n)$.

Pire casPire cas : Chaque partition est extrêmement déséquilibrée, avec une complexité temporelle $O(n^2)$.

Cas moyenCas moyen : Pour des données aléatoires, la complexité temporelle moyenne est $O(n \log n)$.

Complexité spatiale

L'algorithme est implémenté de manière récursive, et la profondeur de récursion dépend de la situation de partitionnement :

  • Meilleur cas：$O(\log n)$
  • Pire cas：$O(n)$

L'utilisation de l'espace peut être réduite grâce à l'optimisation de la récursion terminale ou en utilisant une approche itérative.

Afficher plus de code

autres extensions