Partition cyclique : un algorithme de partitionnement jusqu’à 1,5 fois plus rapide

Le partitionnement de séquence est un algorithme fondamental en programmation informatique qui réorganise les nombres dans une séquence en fonction d'une valeur pivot. L'objectif est de placer tous les nombres inférieurs à la valeur pivot en premier, suivis des autres nombres. Il existe différentes applications du partitionnement, notamment QuickSort et la recherche de la valeur médiane d'une séquence. Actuellement, il existe deux algorithmes de partitionnement bien connus : le schéma de Lomuto et le schéma de Hoare. Le schéma de Hoare est souvent préféré dans la pratique car il effectue moins de réorganisations à l'intérieur du tableau. Un nouveau schéma de partition appelé "partition cyclique" est proposé, qui est similaire au schéma de Hoare mais effectue 1,5 fois moins de réorganisations. Le schéma de partition cyclique est considéré comme presque optimal car le nombre d'affectations de valeurs devient presque égal au nombre de valeurs qui ne sont pas à leur place initiale. Le schéma de Hoare est revu et sa complexité temporelle est O(N), quel que soit l'endroit où les deux balayages se rencontrent. Le schéma de Hoare nécessite 3L/2 affectations, où L est le nombre de valeurs qui ne sont pas à leur place. Le concept de cycles d'affectations est introduit, qui est nécessaire pour optimiser le schéma de partitionnement de Hoare. Différents cas de réorganisations sont présentés, notamment le décalage cyclique gauche et l'inversion d'une séquence, pour montrer que certaines réorganisations nécessitent plus d'affectations que d'autres.