Il existe deux méthodes de partition quicksort mentionnées dans Cormen:

Hoare-Partition(A, p, r)
x = A[p]
i = p - 1
j = r + 1
while true
    repeat
        j = j - 1
    until A[j] <= x
    repeat
        i = i + 1
    until A[i] >= x
    if i < j
        swap( A[i], A[j] )
    else
        return j

et:

Lomuto-Partition(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
    if A[j] <= x
        i = i + 1
        swap( A[i], A[j] )
swap( A[i +1], A[r] )
return i + 1

Abstraction faite de la méthode de choix du pivot, dans quelles situations l’une est-elle préférable à l’autre? Je sais par exemple que Lomuto est relativement peu performant lorsqu'il existe un pourcentage élevé de valeurs en double (c'est-à-dire lorsque plus de 2 tiers de la matrice est la même valeur), alors que Hoare se comporte très bien dans cette situation.

Quels autres cas spéciaux rendent une méthode de partition significative mieux que l'autre?

Dimension pédagogique

En raison de sa simplicité, la méthode de partitionnement de Lomuto pourrait être plus facile à mettre en œuvre. Il y a une belle anecdote dans la Programmation de Jon Bentley sur le tri:

«La plupart des discussions sur Quicksort utilisent un schéma de partitionnement basé sur deux indices qui s'approchent [...] [c'est-à-dire ceux de Hoare]. Bien que l'idée de base de ce schéma soit simple, j'ai toujours trouvé les détails délicats - j'ai déjà passé une bonne partie des deux jours à chasser un bogue caché dans une courte boucle de partitionnement. Un lecteur d'un avant-projet s'est plaint de ce que la méthode standard à deux index est en réalité plus simple que celle de Lomuto et a esquissé du code pour faire valoir son point; J'ai arrêté de chercher, j'ai trouvé deux insectes.

Dimension de performance

Pour une utilisation pratique, la facilité de mise en œuvre pourrait être sacrifiée pour des raisons d'efficacité. Sur une base théorique, nous pouvons déterminer le nombre de comparaisons d’éléments et d’échanges pour comparer les performances. De plus, le temps d'exécution réel sera influencé par d'autres facteurs, tels que les performances de la mise en cache et les prédictions erronées des branches.

Comme indiqué ci-dessous, les algorithmes se comportent de manière très similaire sur les permutations aléatoires, à l' exception du nombre de swaps . Là-bas, Lomuto a besoin de trois fois plus que Hoare!

Nombre de comparaisons

$n-1$$n$

Nombre de swaps

Le nombre de swaps est aléatoire pour les deux algorithmes, en fonction des éléments du tableau. Si nous supposons des permutations aléatoires , c'est-à-dire que tous les éléments sont distincts et que chaque permutation des éléments est également probable, nous pouvons analyser le nombre attendu de swaps.

$1,\ldots,n$

Méthode de Lomuto

$j$$A[j]$$x$$1,\ldots,n$$x-1$$x$$x-1$$x$

$\{1,\ldots,n\}$$\frac1n$

$n$

Méthode de Hoare

$x$

$i$$j$$x$$i$$j$

$x$

$\mathrm{Hyp}(n-1,n-x,x-1)$$n-x$$x-1$$(n-x)(x-1)/(n-1)$$x$

Enfin, nous effectuons une nouvelle moyenne sur toutes les valeurs de pivot pour obtenir le nombre total de swaps attendus pour le partitionnement de Hoare:

(Une description plus détaillée se trouve dans la thèse de ma maîtrise , page 29.)

Motif d'accès mémoire

Les deux algorithmes utilisent deux pointeurs dans la matrice qui l’analysent séquentiellement . Par conséquent, les deux se comportent de manière presque optimale en ce qui concerne la mise en cache.

Eléments identiques et listes déjà triées

Comme déjà mentionné par Wandering Logic, les performances des algorithmes diffèrent plus radicalement pour les listes qui ne sont pas des permutations aléatoires.

$n/2$

$0$$i$$j$$\mathcal O(n\log n)$

$0$A[j] <= x$i=n$$\Theta(n^2)$

Conclusion

La méthode de Lomuto est simple et facile à mettre en œuvre, mais ne devrait pas être utilisée pour mettre en œuvre une méthode de tri de bibliothèque.

Quelques commentaires ont été ajoutés à l'excellente réponse de Sebastian.

Je vais parler de l’algorithme de réorganisation des partitions en général et non de son utilisation particulière pour Quicksort .

La stabilité

L'algorithme de Lomuto est semistable : l'ordre relatif des éléments ne satisfaisant pas le prédicat est conservé. L'algorithme de Hoare est instable.

Modèle d'accès d'élément

L'algorithme de Lomuto peut être utilisé avec une liste à liens simples ou des structures de données similaires similaires. L'algorithme de Hoare a besoin d'une bidirectionnalité .

Nombre de comparaisons

$n-1$$n$

Mais pour ce faire, nous devons sacrifier 2 propriétés:

1. La séquence à partitionner ne doit pas être vide.
2. L'algorithme ne peut pas renvoyer le point de partition.

$n$