La partition Lomuto est un algorithme de partition simple utilisé dans le tri rapide. L'algorithme de Lomuto partitionne le sous-réseau A[left] ... A[right] et suppose que A[left] est un pivot. Comment modifier cet algorithme pour partitionner A[left] ... A[right] en utilisant un donné pivot P (qui diffère de A[left])?Comment modifier le schéma de partition Lomuto?
L'algorithme de partitionnement de Lomuto dépend du pivot qui est l'élément le plus à gauche du sous-partition en cours de partitionnement. Il peut également être modifié pour utiliser l'élément le plus à droite du pivot à la place; par exemple, voir le chapitre 7 du CLRS. L'utilisation d'une valeur arbitraire pour le pivot (par exemple, quelque chose qui ne figure pas dans le sous-tableau) ferait foirer les choses dans une implémentation de quicksort car il n'y aurait aucune garantie que votre partition rende le problème plus petit. Supposons que vous ayez zéro comme valeur sur laquelle vous avez pivoté mais que toutes les entrées de tableau N étaient positives. Alors votre partition donnerait un tableau d'éléments de longueur nulle < = 0 et un tableau de longueur N contenant les éléments> = 0 (qui sont tous). Vous obtiendriez une boucle infinie essayant de faire le quicksort dans ce cas. Pareil si vous essayiez de trouver la médiane du tableau en utilisant cette forme modifiée de la partition de Lomuto. La partition dépend de manière critique du choix d'un élément du tableau sur lequel pivoter. Vous perdriez fondamentalement la postcondition qu'un élément (le pivot) serait définitivement mis en place après la partition, ce que la partition de Lomuto garantit.
L'algorithme de Lomuto dépend aussi de manière critique du pivotement sur un élément qui se trouve dans la première ou la dernière position de la matrice en cours de partitionnement. Si vous pivotez sur un élément qui ne se trouve ni à l'avant ni à l'extrémité du tableau, l'invariant de la boucle qui est au cœur de la raison pour laquelle la partition de Lomuto fonctionne serait un cauchemar.
Vous pouvez pivoter sur un élément différent de la matrice en l'échangeant avec le premier élément (ou le dernier si vous l'implémentez) comme première étape. Regardez la conférence vidéo du MIT sur Quicksort pour le cours 6.046J où ils discutent en profondeur de l'algorithme de partitionnement de Lomuto (bien qu'ils l'appellent simplement Partition) et d'une implémentation de quicksort basée sur elle, sans parler d'une grande probabilité de discuter de l'exécution attendue d'un forme aléatoire de quicksort:
http://www.youtube.com/watch?v=vK_q-C-kXhs
CLRS et perles de programmation ont tous les deux grandes sections sur quicksort si peut-être vous êtes coincé à l'aide d'un livre inférieur pour une classe d'algorithmes ou quelque chose.
dépend de la façon dont vous définissez P, P est un indice ou un élément particulier? si c'est un index, alors c'est facile. vous modifiez vos deux passes
...
i = left
j = right
while (a[i]<a[p]) i++
while (a[p]>a[j]) j--
if (i <= j)
swap(a, i, j)
qsort(a, left,i)
qsort(a, j,right)
...
si P n'est pas un indice, mais une valeur particulière, vous devrez rechercher d'abord, et ensuite seulement faire ce qui précède avec l'indice résultant. Le tableau n'étant pas encore trié, vous pouvez uniquement effectuer une recherche linéaire. Vous pouvez également trouver un schéma plus astucieux (hashtable) pour trouver votre pivot P, mais je ne vois pas pourquoi vous auriez besoin de faire une telle chose.
Merci beaucoup pour cette excellente explication. – Michael