Trier une liste selon l'ordre défini par une autre liste

Question

Comment trier les éléments de la liste afin qu'ils suivent l'ordre d'un autre (surensemble) liste B ? Supposons pas de doublons.

par exemple. A peut contenir [8 5 2 1] et B peut contenir [5 6 7 8 9 1 2 3 4], et je voudrais trier A pour devenir [5 8 1 2]

Je suis intéressé par les moyens de le faire efficacement et avec une bonne complexité d'exécution.

Answer 1

Si B est une surcouche de , je venais de larguer dans une table de hachage, scan B et créer une nouvelle liste où insérer tous les éléments de B qui est contenu dans la table de hachage. Utilisations O (a) l'exécution de la mémoire et O supplémentaire (b).

Answer 2

Voici quelques idées:

(Dans les complexités de temps donné, n est la taille de A et m est la taille de B . la complexité du temps ne sont pas simplifiées.)

• Pour chaque élément B , faire une recherche linéaire de pour voir si cet élément existe en elle. Si oui, échange avec le premier élément qui n'a pas encore été mis en place. complexité Temps: O (nm)
• Comme ci-dessus, mais d'abord le contenu de dans une structure de recherche efficace pour éviter la recherche linéaire. complexité Heure: O (n + m) en supposant O (1) recherche
• Trier B . Ensuite, pour chaque élément , trouver son indice (qui est garanti Exister) dans B en utilisant la recherche binaire. Enregistrer cet indice dans un réseau auxiliaire de même taille que A . Utiliser cette matrice d'indices comme entrée à un comparateur qui sortes A . complexité Heure: O ((m m log) + (n log n) + (n log n))