L'algorithme de tri rapide, ou Quicksort, figure au programme d'Informatique pour tous, le cours commun d'informatique des classes préparatoires scientifiques en deuxième année. Or, pour ce cours, le langage de référence est Python… et il est vraiment difficile de montrer avec ce langage à quel point cet algorithme est intéressant.

Présentation du problème

L'idée de base de Quicksort est très simple : pour trier une liste l, il suffit de prendre un élément p de la liste (que l'on appelle le pivot), sélectionner les éléments de l plus petits que p et les trier, sélectionner ceux qui sont plus grands et les trier… et tout remettre dans l'ordre.

Ainsi, pour trier la liste l = [3, 7, 4, 5, 1, 2, 6, 8, 9, 0], on définit le pivot comme le premier élément de la liste : p = 3 et on sépare le reste en deux sous-listes :

plus_petit = [1, 2, 0]
plus_grand = [7, 4, 5, 6, 8, 9]

Ensuite, on trie plus_petit et plus_grand et on retourne la liste

plus_petit_trie + [pivot] + plus_grand_trie

Comment fait-on pour trier les sous-listes ? En rappelant l'algorithme, sachant qu'une liste de longueur 1 est déjà triée.

Cela donne l'algorithme suivant :

def pseudo_quicksort(l):
    if len(l) <= 1:
        return l # la liste est déjà triée
    pivot = l[0]
    plus_petit = []
    plus_grand = []
    for e in l[1:]:
        if e <= pivot:
            plus_petit.append(e)
        else:
            plus_grand.append(e)
    return pseudo_quicksort(plus_petit) \\
        + [pivot] + pseudo_quicksort(plus_grand)

Quel est le problème ? Cet algorithme est correct, il trie bien une liste, est plutôt rapide et respecte l'idée derrière Quicksort. Mais c'est une version très naïve et dénaturée de Quicksort. On a le « sort », mais pas vraiment le « quick ». En particulier, cette fonction passe son temps à dupliquer des données, à créer de nouvelles listes, etc., ce que ne fait pas le véritable algorithme Quicksort.

Au contraire, le « vrai » Quicksort effectue un tri en place (c.à.d. il modifie le tableau plutôt que d'en créer un nouveau) et la seule mémoire supplémentaire qu'il utilise est pour la pile d'appel lors de la récursion (de taille logarithmique par rapport à la taille de liste, donc quasiment négligeable). Et il est vraiment très rapide.

Dans la version originale de Hoare, en choisissant toujours comme pivot le premier élément de la liste, on a deux pointeurs qui se déplacent, l'un i de gauche à droite en s'assurant que les éléments le précédant sont plus petits que le pivot, et un autre j de droite à gauche avec tous les éléments le suivant strictement plus grands que le pivot :

Et lorsqu'il y a un problème, si i pointe sur un élément strictement plus grand que le pivot et j pointe sur un élément plus petit, on les échange, et on peut avancer.

Quel est le problème, donc ? C'est qu'il est assez difficile de montrer que la bonne version est vraiment meilleure que la mauvaise en Python, puisque que le code de la fonction pseudo_quicksort ci-dessus est (légèrement) plus rapide que le code propre (et très commenté, peut-être un peu trop, mais les invariants de boucles permettent de vérifier facilement la correction de l'implémentation) de Quicksort :

def quicksort(l):
    def aux(debut, fin) :
        # Si debut <= fin + 1, la liste est de longueur au plus 1,
        # elle est déjà triée.
        if fin <= debut + 1:
            return
        # On choisit le pivot,
        pivot = l[debut]
        # Puis on va partager le reste de la liste
        # par rapport à ce pivot.
        i = debut + 1
        j = fin - 1
        while True:
            # Invariant de boucle
            # 1. debut < i, j < fin et i <= j + 1
            # 2. si debut < k < i alors l[k] <= pivot
            # 3. si j < k < fin alors pivot <= l[k]
            while i <= j and l[i] <= pivot:
                i += 1
            # en sortie de boucle, on a
            # 1. soit i == j + 1
            # 2. soit i <= j et l[i] > pivot
            while i <= j and l[j] > pivot:
                j -= 1
            # de même, en sortie de boucle, on a
            # 1. soit i == j + 1
            # 2. soit i <= j et l[j] <= pivot
            # En conclusion, deux cas sont possibles ici :
            # 1. i == j + 1
            # 2. i <= j et l[j] <= pivot < l[i]
            # Dans le premier cas, on a fini de trier
            if (i > j):
                break
            # Sinon, on a donc l[j] <= pivot < l[i]
            #   et donc i < j
            # On échange les deux éléments :
            l[i], l[j] = l[j], l[i]
            # et on continue
            i += 1
            j -= 1
        # On a maintenant
        # 1. i == j + 1
        # 2. debut < k <= j => l[k] <= pivot
        # 3. i <= k < fin => l[k] > pivot
        # On mets le pivot à sa place
        l[debut], l[j] = l[j], l[debut]
        # et on trie les deux côtés séparément.
        aux(debut, j)
        aux(i, fin)
    aux(0, len(l))

Vérification du problème

Pour vérifier que la mauvaise version est plus rapide que la bonne, comparons les temps mis par les deux fonctions.

Pour cela, nous allons utiliser la fonction intermédiaire suivante :

def chrono(n, f):
    # on trie f fois une liste de n éléments
    t1 = 0.0
    t2 = 0.0
    for _ in range(f):
        l1 = [random.random() for _ in range(n)]
        l2 = l1[:] # on duplique la liste
        t1 -= time.time()
        _ = pseudo_quicksort(l1)
        t1 += time.time()
        t2 -= time.time()
        _ = quicksort(l2)
        t2 += time.time()
    return t1 / f, t2 / f

À chaque fois, si les temps mis sont comparables, pseudo_quicksort est en général plus rapide que quicksort.

Un autre comparatif

Comparons maintenant les temps d'exécutions avec une implémentation plus sérieuse, en réitérant l'expérience en langage C++. Voici tout d'abord le code de pseudo_quicksort :

std::vector<int> pseudo_quicksort(std::vector<int> l) {
  if (l.size() <= 1) {
    return l;
  }
  int pivot = l[0];
  std::vector<int> plus_petit, plus_grand;
  for (auto it = l.begin() + 1 ; it != l.end(); ++it) {
    if (*it <= pivot) {
      plus_petit.push_back(*it);
    } else {
      plus_grand.push_back(*it);
    }
  }
  // On trie plus_petit et plus_grand
  std::vector<int> r = pseudo_quicksort(plus_petit);
  std::vector<int> r2 = pseudo_quicksort(plus_grand);
  // On reconstruit le résultat final...
  r.push_back(pivot);
  r.insert(r.end(), r2.begin(), r2.end());
  // ... avant de le renvoyer.
  return r;
}

Voici maintenant le code de quicksort :

void quicksort_aux(int l[], int debut, int fin) {
  if (fin <= debut + 1)
    return;
  int pivot = l[debut];
  int i = debut + 1, j = fin - 1;
  while (true) {
    while (i <= j && l[i] <= pivot) {
      i += 1;
    }
    while (i <= j && l[j] > pivot) {
      j -= 1;
    }
    if (i > j) {
      break;
    }
    int tmp = l[i];
    l[i] = l[j];
    l[j] = tmp;
    i += 1;
    j -= 1;
  }
  int tmp = l[debut];
  l[debut] = l[j];
  l[j] = tmp;
  quicksort_aux(l, debut, j);
  quicksort_aux(l, i, fin);
}

void quicksort(std::vector<int> l) {
  quicksort_aux(l.data(), 0, l.size());
}

Ce sont des traductions directes des codes Python précédents. En triant une liste de 1000000 entiers, j'obtiens le résultat suivant :

clock resolution: mean is 47.536 ns (10240002 iterations)

benchmarking pseudo_quicksort
collecting 100 samples, 1 iterations each, in estimated 85.2807 s
mean: 854.245 ms, lb 847.087 ms, ub 862.863 ms, ci 0.95
std dev: 39.8463 ms, lb 33.4953 ms, ub 50.2214 ms, ci 0.95
found 5 outliers among 100 samples (5%)
variance is moderately inflated by outliers

benchmarking quicksort
collecting 100 samples, 1 iterations each, in estimated 626.126 ms
mean: 6.3364 ms, lb 6.26806 ms, ub 6.42072 ms, ci 0.95
std dev: 386.494 μs, lb 322.376 μs, ub 493.992 μs, ci 0.95
found 4 outliers among 100 samples (4%)
variance is severely inflated by outliers

Ce que l'on peut y lire, c'est que la version quicksort mets en moyenne 6.3364 ms alors que la version pseudo_quicksort mets quand à elle... 854.245 ms.

Cette différence conséquente rends bien mieux compte de la différence entre quicksort qui est un modèle d'efficacité, et pseudo_quicksort qui est un modèle d'inefficacité.

Utilisation mémoire

Une autre grande différence entre les deux fonctions réside dans l'utilisation de la mémoire. Pour pseudo_quicksort, de nombreuses listes vont être créées, ce qui implique une consommation importante de mémoire.

À l'inverse, si l'on ne tient pas compte de l'espace de pile utilisé pour les appels récursifs, quicksort nécessite une taille mémoire constante pour s'exécuter.

Il est possible d'illustrer cela à l'aide de la fonction profile du module memory_profiler, en procédant par exemple ainsi :

# on définit les méthodes de tri
...

# on définit la fonction que l'on veut profiler
@profile
def test():
    l1 = [random.random() for _ in range(10000)]
    l2 = l1[:]
    gc.collect()
    gc.disable()
    _ = qs(l1)
    gc.collect()
    gc.disable()
    quicksort(l2)

test()

Les commandes du module gc permettent de nettoyer la mémoire avant l'appel aux fonctions de tri. La consommation mémoire vient alors exclusivement de ces fonctions.

Si l'on note test.py ce fichier, en exécutant dans un shell la commande

python3 -m memory_profiler test.py

on obtient un affichage de type

Filename: d3.py

Line #    Mem usage    Increment   Line Contents
================================================
    43   28.152 MiB   28.152 MiB   @profile
    44                             def truc():
    45   35.156 MiB    0.699 MiB       l1 = [random.random() for _ in range(...
    46   35.922 MiB    0.766 MiB       l2 = l1.copy()
    47   35.922 MiB    0.000 MiB       gc.collect()
    48   35.922 MiB    0.000 MiB       gc.disable()
    49   38.852 MiB    2.930 MiB       _ = pseudo_quicksort(l1)
    50   38.852 MiB    0.000 MiB       gc.collect()
    51   38.852 MiB    0.000 MiB       gc.disable()
    52   38.852 MiB    0.000 MiB       quicksort(l2)

On voit que l'exécution de pseudo_quicksort a nécessité 2.930 MiB de mémoire supplémentaire, alors que quicksort en a nécessité 0.000 MiB.

Le table suivant indique diverses mesures de consommation mémoire en fonction de la taille de la liste à trier.

Comme on le voit, pseudo_quicksort est très consommateur alors qu'au contraire, quicksort est très économe. Bien sûr, dans le premier cas, la consommation de mémoire, dûe à d'incessantes duplications de portions de listes, a un coût temporel important qui est clairement visible pour le programme en C++ mais est totalement occulté en Python.

Comme on vient de le voir, le tri rapide est un algorithme de tri extrèmement rapide et très peu consommateur de mémoire. Le tri est effectué en place, et chaque élément de la liste effectué un nombre très faible de déplacements avant d'arriver à la bonne place.

Il est vraiment dommage de le confondre avec la méthode illustrée par pseudo_quicksort (on choist un élément, on mets les éléments plus petits devant et les autre derrière et on recommence) qui est, certes, une méthode de tri mais reflète une approche très naïve de la programmation et ne tient absolument pas compte de questions comme comment représenter et manipuler efficacement les données. Ce n'est guère plus que l'idée d'un algorithme.

Il reste un problème important concernant l'algorithme quicksort, c'est qu'il a une complexité en ${`O(n^2)`}$ dans le pire des cas. Dans un prochain article, nous allons présenter quelques idées pour résoudre ce grave problème, sous la forme d'un autre algorithme de tri en place de complexité optimale (en ${`O(n \\ln n)`}$ dans le pire des cas) et de modification de Quicksort pour assurer cette complexité optimale.