On a vu dans la première partie qu'en Python, la version propre de Quicksort est moins rapide qu'une version naïve où l'on passe son temps à allouer de la mémoire et à recopier des tableaux entiers. Autrement dit, Python ne nous incite pas toujours à programmer intelligemment pour être rapide.

Nous allons maintenant nous pencher sur un autre problème de Quicksort, plus grave celui-ci : dans le pire des cas, sa complexité temporelle peut montrer jusqu'à ${`O(n^2)`}$. Pour trier une liste de 1000000 nombres, la complexité optimale est en ${`O(n \\ln n)`}$ (pour ${`n = 1000000`}$, ${`\\ln n \\simeq 13.8`}$ à comparer à ${`n`}$) et donc Quicksort devient dans ce cas vraiment lent.

Un tri optimal : le tri par tas ou Heapsort

On connaît des algorithmes de tri optimaux, qui sont en ${`O(n \\ln n)`}$ en moyenne mais aussi dans le pire des cas. Un exemple est le tri fusion mais pour trier un tableau, le cadre qui nous intéresse pour Quicksort, il présente un autre problème que nous évoquerons à la fin de l'article. Un autre algorithme très intéressant est le tri par tas (ou heap sort). Cet algorithme est donc en ${`O(n \\ln n)`}$ dans le pire des cas (et en moyenne, bien sûr, puisque c'est la borne optimale), et il a une complexité spatiale en ${`O(1)`}$ (pour Quicksort, on doit se contenter de ${`O(\\ln n)`}$ mais cela reste totalement acceptable).

Je ne vais pas expliquer le principe de cet algorithme (il nécessite de savoir ce qu'est un tas, ce que j'expliquerai dans un autre article), je vais me contenter d'en donner le code :

def heapsort(l):
    for i in range((len(l) - 1) // 2, -1, -1):
        siftDown(l, i, len(l))
    for i in range(len(l) - 1, 0, -1):
        l[0], l[i] = l[i], l[0]
        siftDown(l, 0, i)

def siftDown(l, start, end):
    curr = start
    child = 2 * curr + 1
    while child < end:
        next = curr
        if l[child] > l[next]:
            next = child
        child += 1
        if child < end and l[child] > l[next]:
            next = child
        if next == curr:
            break
        l[curr], l[next] = l[next], l[curr]
        curr = next
        child = 2 * curr + 1

Pourquoi alors utilise-t'on Quicksort et pas Heapsort ? Car comme son nom l'indique, Quicksort est vraiment rapide, plus rapide que Heapsort. À nouveau, comme dans la première partie, je ne peux pas montrer cela en Python, car l'implémentation propre de Quicksort y est ridiculement lente.

La traduction des algorithmes précédents en C++ permet d'obtenir les temps suivants (pour trier une liste d'un million d'entiers).

benchmarking quicksort
collecting 100 samples, 1 iterations each, in estimated 7.88038 s
mean: 76.3464 ms, lb 76.1706 ms, ub 76.694 ms, ci 0.95
std dev: 1212.33 μs, lb 745.453 μs, ub 2.20134 ms, ci 0.95
found 10 outliers among 100 samples (10%)
variance is slightly inflated by outliers

benchmarking heapsort
collecting 100 samples, 1 iterations each, in estimated 8.89795 s
mean: 89.0205 ms, lb 88.768 ms, ub 89.3523 ms, ci 0.95
std dev: 1461.34 μs, lb 1179.31 μs, ub 2.07013 ms, ci 0.95
found 4 outliers among 100 samples (4%)
variance is slightly inflated by outliers

On voit que Quicksort est ${`15\\%`}$ plus rapide que Heapsort.

Quicksort killers

Comment faire pour que Quicksort ait une complexité en ${`O(n^2)`}$ ? Comme trouver un Quicksort killer ? C'est simple, il suffit de lui faire trier une liste... déjà triée.

Dans ce cas, à chaque fois, le pivot est le plus petit élément de la liste à trier, ce qui fait que la sous-liste de gauche est de longueur nulle, et la sous-liste de droite ne contient qu'un élément en moins par rapport à la liste de départ.

Comme l'algorithme devient alors terriblement lent (pour une grosse liste), il faut à tout prix trouver un moyen d'éviter cela.

Une façon simple de procéder est de ne pas prendre l'élément de gauche comme pivot. Un moyen usuel, facile à programmer et peu couteux, est de prendre comme pivot la médiane entre les valeurs à gauche, au milieu et à droite de la liste. Pour une liste déjà triée, le pivot est donc la valeur du milieu, on coupe la liste en deux pour les appels récursifs et on retrouve bien une complexité en ${`O(n \\ln n)`}$.

Oui mais dans ce cas aussi, on peut trouver une liste qui se trie en ${`O(n^2)`}$.

Une autre idée est de choisir le pivot au hasard dans la liste.

Oui mais, à nouveau, on peut trouver une liste qui se trie en ${`O(n^2)`}$.

Bref, la complexité dans le pire des cas reste du ${`O(n^2)`}$, ce qui est proprement inadmissible pour une utilisation sérieuse.

Introsort

Une bonne solution pour résoudre ce problème est donner par l'algorithme Introsort (pour introspection sort). Cette méthode de tri commence par utiliser Quicksort... mais si cela mets trop longtemps, on passe en Heapsort.

Que signifie le « si cela mets trop longtemps » ? C'est très simple. Une complexité en ${`O(n \\ln n)`}$ signifie que la profondeur maximum des appels récursifs (le nombre d'appels emboîtés) doit être de l'ordre de ${`\\ln n`}$. Donc au début du tri, on calcule ${`\\ln n`}$ (fois une constante de réglage) pour obtenir (après arrondi) un entier, que l'on décrémente à chaque appel récursif (on a donc juste un entier à passer comme argument supplémentaire). Si ce compteur arrive à zéro alors que la liste n'est pas vide (plus précisément, la sous-liste correspondant à l'appel récursif courant), cela signifie que l'on est dans un cas pénible et on passe alors en Heapsort qui, comme on l'a vu, est un peu plus lent mais assure une complexité en ${`O(n \\ln n)`}$.

N'enterrez trop vite pas le tri par insertion

On a vu comment Introsort permet d'avoir le meilleur des mondes, la rapidité de Quicksort avec Heapsort comme ceinture de sécurité. On a ainsi un algorithme optimal en ${`O(n \\ln n)`}$, bien loin des tris naïfs en ${`O(n^2)`}$.

Et pourtant, il ne faut pas les enterrer trop vite, surtout le tri par insertion. En effet, sur des petites listes (d'une vingtaine d'éléments), ce dernier est plus rapide que le Quicksort.

Quel intérêt ? On commence avec Quicksort et lorsque la liste devient suffisamment petite, on passe en tri par insertion. Cela permet de gagner encore quelques petits pourcents supplémentaires sur la vitesse du tri.

benchmarking quicksort
collecting 100 samples, 1 iterations each, in estimated 7.88038 s
mean: 76.3464 ms, lb 76.1706 ms, ub 76.694 ms, ci 0.95
std dev: 1212.33 μs, lb 745.453 μs, ub 2.20134 ms, ci 0.95
found 10 outliers among 100 samples (10%)
variance is slightly inflated by outliers

benchmarking quicksort avec insertion à la fin
collecting 100 samples, 1 iterations each, in estimated 7.0984 s
mean: 71.4717 ms, lb 71.4158 ms, ub 71.5488 ms, ci 0.95
std dev: 331.085 μs, lb 265.105 μs, ub 449.804 μs, ci 0.95
found 13 outliers among 100 samples (13%)
variance is unaffected by outliers

C'est cet algorithme – Introsort avec finition en tri par insertion – qui est (avec des tonnes d'optimisations supplémentaires) utilisé dans la bibliothèque standard de C++. Nous allons l'étudier dans le prochain article de la série.