Partitionnement Quicksort: Hoare vs Lomuto

83

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?

Robert S. Barnes
la source
2
Je ne peux penser à aucune situation dans laquelle Lomuto est meilleur que Hoare. Il semble que Lomuto effectue des échanges supplémentaires chaque fois A[i+1] <= x. Dans un tableau trié (et avec des pivots raisonnablement choisis), Hoare n'échange presque pas et Lomuto en fait une tonne (une fois que j est devenu assez petit, puis tout le A[j] <= x.) Que me manque-t-il?
Wandering Logic
2
@WanderingLogic Je ne suis pas sûr, mais il semble que la décision de Cormen d'utiliser la partition de Lomuto dans son livre soit peut-être pédagogique - elle semble avoir un invariant de boucle assez simple.
Robert S. Barnes le
2
Notez que ces deux algorithmes ne font pas la même chose. À la fin de l'algorithme de Hoare, le pivot n'est pas à sa position finale. Vous pouvez ajouter un swap(A[p], A[j])à la fin de Hoare pour obtenir le même comportement pour les deux.
Aurélien Ooms
Vous devriez également vérifier i < jdans les 2 boucles de répétition du partitionnement de Hoare.
Aurélien Ooms
@ AurélienOoms Le code est directement copié du livre.
Robert S. Barnes

Réponses:

92

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

n1n

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,,n

Méthode de Lomuto

jA[j]x1,,nx1xx1x

{1,,n}1n

1nx=1n(x1)=n212.

n

Méthode de Hoare

x

ijxij

x

Hyp(n1,nx,x1)nxx1(nx)(x1)/(n1)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:

1nx=1n(nx)(x1)n1=n613.

(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

0ijO(nlogn)

0A[j] <= xi=nΘ(n2)

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.

Sébastien
la source
16
Wow, c'est une réponse détaillée. Bien fait!
Raphaël
Je suis d'accord avec Raphael, très bonne réponse!
Robert S. Barnes
1
Je voudrais apporter une petite précision: à mesure que le rapport entre les éléments uniques et le nombre total d’éléments diminue, le nombre de comparaisons effectuées par Lomuto croît considérablement plus rapidement que celles de Hoare. Cela est probablement dû à la mauvaise partition de Lomuto et à la bonne partition moyenne de Hoare.
Robert S. Barnes
Grande explication des deux méthodes! Je vous remercie!
v kouk
Vous pouvez facilement créer une variante de la méthode Lomuto capable d'extraire tous les éléments égaux au pivot et de les laisser en dehors de la récursion, bien que je ne sois pas sûr que cela puisse aider ou nuire à la moyenne des cas.
Jakub Narębski
5

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

n1n

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

Fernando Pelliccioni
la source