Bonjour,

A partir d'une liste quelconque d'éléments ayant une relation d'ordre, je cherche à regrouper consécutivement les éléments égaux. Considérons par exemple la liste d'entiers {1, 2, 1, 3, 2, 3}.

Evidemment la liste triée {1, 1, 2, 2, 3} vérifie mon critère mais les listes {2, 2, 1, 1, 3}, {3, 1, 1, 2, 2} par exemple le vérifient aussi.

Ma question est la suivante : ce problème a-t-il une complexité mathématique plus faible qu'un tri? Quel est son nom?

Ce problème est critique car je travaille sur des listes de plusieurs millions d'éléments et qu'un tri, même avec un algorithme performant est de peu non acceptable en termes de runtime.

Concernant la typologie de mes données, si j'ai des occurrences multiples, j'ai rarement plus de 2 ou 3 fois le même élément dans la liste. Sinon, mes éléments sont non bornés. Peut-être ces éléments de typologies peuvent-t-ils orienter un choix d'algorithme (je code en C++ (au cas où un algorithme adapté existe dans Boost)).

En espérant avoir été clair dans l'exposé de mon problème, par avance merci.