[STL] tri non stable

Bonjour à tous,

Après une petite recherche, je n'ai pas trouvé la réponse à ma question, surement peut-être parceque qu'elle est un peu étrange. Peut-être pourrez vous m'aider ? Je cherche à trier un conteneur de manière non stable, voire même la moins stable possible. Autrement dit, si j'ai les données suivantes:

Code:

---

{A, 0} {B, 1} {C, 1} {D, 2} {E, 2}

---

je voudrais que chaque tri me donne un résultat différent, soit:

Code:

---

ABCDE ou ABCED ou ACBDE ou ACBED

---

L'algorithme std::sort n'est pas stable, mais malheureusement il me retourne toujours les éléments ordonnées de la même manière. Et j'ai bien vu qu'il n'appréciait pas du tout un opérateur de comparaison de ce type :

Code:

---

1 2 3 4 5 6 7

bool operator (const C& Left, const C& Right) { if (Left.Value == Right.Value) return (rand()%2) else return Left.Value < Right.Value; }

---

Ce qui est surement formellement interdit d'ailleurs ;)
Du coup, existe-il une manière simple de faire ceci, plutôt que d'implémenter un algo qui permuterait les éléments égaux aléatoirement, par exemple ? J'ai tenté un std::random_shuffle avant chaque std::sort, m'a ça n'a pas l'air de modifier l'ordre final obtenu après le tri.

Merci d'avance pour toutes vos idées !

Faut-il initialiser la graine aléatoire avant un random_shuffle, comme en C ?

Après quelques tests, on dirait que l'initialisation de la graine est facultative... enfin les éléments sont bien permutés, peu importe la version de random_shuffle utilisée.

Mais au final, celà ne changeait pas mes resultats ... jusqu'a ce que j'essaye avec un échantillon plus grand. Et là, problème résolu ! Je m'en veux un peu, j'avais apparement trop peu d'éléments dans mon tableau pour voir la "non-stabilité" de std::sort

Du coup merci à toi, ça m'aura fait creuser un peu plus du coté de random/sort ! Voilà le code qui fonctionne :

Code:

---

1 2 3 4 5 6 7 8 9

bool Compare(const Test& Left, const Test& Right) { return Left.Value < Right.Value; }   std::vector<Test> myList; // remplissage avec beaucoup de données std::random_shuffle(myList.begin(), myList.end()); std::sort(myList.begin(), myList.end(), Compare);

---