EDIT: B> Je ne suis pas sûr que ma question initiale soit assez claire. J'ai besoin d'un algorithme qui calculera la séquence minimale des mouvements pour réorganiser une matrice d'une commande à une autre. On sait que les deux tableaux contiendront les mêmes éléments (pas de doublons) et auront la même longueur. Par exemple: var c = $('#container-id');
$(els).each(function() {
c.append(this);
});
4 Réponses :
Ma première pensée est que vous devriez utiliser Sélection Triez au lieu de La méthode de tri intégrée, puisqu'il rend le plus faible nombre de swaps nécessaires. De cette façon, vous pouvez simplement déplacer l'élément DOM pour déplacer l'ID dans la liste.
Corrigez-moi si je me trompe, mais cela ressemble à une sélection de sélection fera toujours des swaps O (n). En outre, considérez le cas où la liste est complètement triée, sauf que le premier élément devrait être en dernier. L'algorithme que je cherche, déplacerait simplement cet élément à la fin.
Divisez les touches et le tableau Index dans une gamme distincte d'objets {clé, index}. Trier ce tableau (en utilisant le meilleur type que vous puissiez, bien sûr; soit une sorte de fusion si les comparaisons sont chères, ou rapide s'ils sont bon marché). Vous savez maintenant, à partir des index réels dans la matrice triée et les valeurs d'index stockées dans chaque élément, comment réorganiser le tableau d'origine.
Une fois que vous avez triché les clés, le nombre "optimal" de mouvements sera le O (n) du tableau d'origine. Si vous souhaitez réorganiser la matrice d'origine en place, vous pouvez dériver les interchangees de votre liste triée d'index assez simplement.
Knuth Volume 3 a une section sur "Networks de tri". Il ne va pas dans un lot de détail sur la manière de construire des réseaux de comparaison minimum, mais cite quelques travaux (par exemple, par Batcher et lui-même) sur la façon de les construire. Notez que, tandis que ceux-ci sont des notes comme "réseaux de comparaison minimum", peu (le cas échéant) d'entre eux ont vraiment été prouvé être minimes - ils tentent de minimiser le nombre de comparateurs nécessaires, mais pas nécessairement réussi en termes d'atteinte réellement le vrai minimum.
http://fr.wikipedia.org/wiki/longest_increducing_subequence
trouver la recherche croissante la plus longue (selon la nouvelle commande de tri). Puis déplacez chaque élément qui n'est pas dans cette séquence, dans sa place par rapport aux éléments déjà dans la séquence.
Dans votre exemple, 'A, B, E' et 'A, C, E' sont liés à la recherche de plus longue de la recherche préalable. Le mieux que vous puissiez faire est de choisir l'un de ceux-ci et déplacez simplement les autres éléments.
Oui, je peux voir comment ça va faire ce que je veux. Il semble que je puisse aussi bien passer à l'utilisation du tri de patience pour le tri, car cela triera la liste et trouvera la sous-séquence en même temps. Merci!
Est-ce toujours le moyen «préféré» de réorganiser les éléments DOM? J'essaie d'optimiser pour la taille du code, pas nécessairement d'exécution - je vais presque toujours avoir moins de 100 nœuds de réorganiser). De plus, comment garderiez-vous une trace d'avoir à insérer plusieurs nœuds entre deux nœuds de la LIS?