J'ai un tableau d'objets. les objets ont une valeur booléenne que je veux utiliser comme une clé pour trier le tableau (tous les objets avec vrai viennent avant tous les objets avec faux) mais sinon, laissez les choses dans le même ordre.Stable tri de 2 tableaux de valeur?
Existe-t-il une solution simple, O (n) sur place? Peut-être une variante de radix-sort?
Voir here pour une discussion à ce sujet. Vous pouvez avoir soit une solution O (n) qui a besoin d'espace supplémentaire, soit une solution sur place O (n log n).
Hmm. Avec une liste chaînée, cela devrait être faisable - vous chercheriez la première entrée "fausse" et la garderiez comme "emplacement d'insertion". (S'il n'y a pas de "fausses" entrées alors vous avez terminé de toute façon :) Ensuite, parcourez toute la liste - si vous êtes devant l'emplacement d'insertion et trouvez une "fausse" entrée ou si vous êtes après le lieu d'insertion et trouver une entrée "true" puis la déplacer directement avant "l'emplacement d'insertion". Jusqu'à présent, donc O(n).
Maintenant, vous pouvez convertir un tableau dans une liste chaînée dans O(n) et vous pouvez copier les données arrière dans le tableau en O(n). Donc, je pense que cela fonctionnerait en termes de complexité - mais ce n'est pas sur place. Je vais réfléchir à savoir si cela peut être fait sur place ...
Voici une autre question très similaire http://stackoverflow.com/questions/682171/arrange-0s-1s-in-a-array – sharptooth
Il y a une légère différence dans cette question, étant donné que la moitié des éléments sont des 1 et la moitié des 0, ce qui peut vous aider à réduire un peu les besoins en espace ou en temps. – MahlerFive
Eh bien, c'est raisonnable. – sharptooth