J'ai une liste de chaînes triée par une fonction de comparaison spécifique.
Maintenant, je dois résoudre cette liste à l'aide d'une fonction de comparaison différente .
Cette nouvelle fonction de comparaison se comporte légèrement différente lorsque vous comparez certains caractères spéciaux, tels que les UMLAUTS, par exemple. Dans la plupart des cas, l'élément doit être déplacé à une ou deux emplacements pour atteindre la bonne position.
Quel algorithme de tri convient le mieux à résoudre cette liste presque entièrement triée en termes de vitesse d'exécution d'exécution?
4 Réponses :
Tri d'insertion fonctionne bien sur des listes de petites ou presque triées.
de cette papier ACM :
tests sur des listes générées au hasard de Diverses combinaisons de la longueur de la liste et les petits rapports de tri indiquent ce genre d'insertion droite est le meilleur Pour les petites ou très pratiquement triées et que ce plus rapide est le meilleur sinon.
de wiki article Tri d'insertion :
Si le tableau d'entrée est déjà trié, La sorte d'insertion fonctionne aussi peu que n-1 comparaisons, faisant ainsi l'insertion Trier plus efficace quand donné trié ou des tableaux "presque triés".
Donc, question: y a-t-il une bonne raison utiliser l'insertion Trier?
Notez que Quickersort n'est pas rapide, mais il existe une ressemblance étroite; Dans la terminologie moderne, Quickersort pourrait être considéré comme une variante de Quicksort qui trie toujours le sous-ensemble plus court (minimiser la profondeur de pile pour la récursion) et qui présente un critère de sélection de partition simple qui est probablement sensible à la mauvaise performance des cas, mais qui fonctionnerait bien pour le cas presque triché en discussion ici.
@Max: Pas vraiment (@henk et j'ai eu cette discussion il y a peu de temps). BubblesTort est habituellement utilisé sans raison pour laquelle le développeur se souvient d'un collège et il est simple (mais pas beaucoup plus simple que le tri d'insertion), et il semble être un choix général et est rapide lorsqu'ils testent avec un petit nombre d'articles commandés au hasard. Le tri d'insertion est choisi dans un scénario spécifique.
avoir accès aux deux opérations de recherche? Si oui, vous pouvez construire un hachage pendant le premier processus de tri et l'utiliser à d'autres opérations de tri
Comme je l'ai compris, votre liste de données est définie supprimée (par exemple par ordre d'ASCII / Pays Chart), mais sans certaines règles de dictionnaire appliquées pour un pays particulier. Par exemple, l'Allemagne et leurs UMLAUTS
Voir germanic_umlaut dans Wikipedia
Vous n'émettez pas de nouveaux articles, vous voulez simplement les recourir à un peu plus strict règle de tri stricte.
Comme vous pouvez lire par exemple ici
http://www.softpanorama.org/algorithms/sorting/bubblesort.shtml
Le tri des bulles fonctionne bien sur des listes triées toutes sortes avec quelques permutations. Cela semble comme le tri de la bulle est un bon algorithme pour commencer. Notez également que la tri de la bulle est un algorithme de tri "stable". Cela pourrait être important pour votre scénario.
Pour des listes presque triées, des variations du peigne Trier surperformer le QuicksTort. Je n'ai pas testé pour voir comment la trieuse du peigne se compare au tri de l'insertion.
Vous recherchez vraiment un algorithme ou juste une heuristique?
Dupliqué possible de Quel algorithme de tri fonctionne mieux sur les données principalement triées? < / a>