Discussion :

[bigquick]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 !

[Médinoc]

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

[bigquick]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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);