J'ai une gamme de valeurs qui est presque, mais pas tout à fait triée, avec quelques valeurs déplacées (disent, 50 sur 100 000). Comment trier le plus efficacement?
5 Réponses :
Ma première intuition serait d'identifier les éléments égarés et de les déplacer vers un tableau séparé, triez-les avec n'importe quel algorithme que vous aimez (avec les quelques-uns, cela ne devrait pas avoir d'importance), puis fusionnez les régler.
Découvrez le "degré" de Nessés (et d'où les éléments "mal placés") dans un tableau sont effectivement difficiles, autant que je sache ... Savez-vous de tout bon algorithme pour cela?
Veuillez proposer un algorithme pour trouver ce que vous appelez "éléments égarés". Merci.
Utilisez Tri d'insertion ; C'est génial avec des tableaux presque triés, car il est près de O (n) temps pour eux. En fait, je crois que le .NET Framework utilise un tri d'insertion pour trier les valeurs ENUM en interne (puisqu'elles sont souvent triées), même si je devrais revérifier cela.
Sous l'hypothèse que la matrice est presque triée, vous pouvez utiliser l'une des opérations suivantes:
wiki a même une implémentation Java sur elle. Puisque vous ne pouvez pas le faire plus vite que O (n) (puisqu'il prend beaucoup de temps pour même de savoir si un tableau est trié ou non) Smoothsort est un bon choix. Plus de détails ici .
L'avantage de SoodSort est qu'il se rapproche de l'heure O (n) si l'entrée est déjà trié dans une certaine mesure
Tri de coctail
La complexité du cocktail tri dans grand O la notation est O (N2) pour le pire cas et le cas moyen, mais il devient plus proche de O (n) si la liste est principalement commandé avant d'appliquer le Algorithme de tri,
Timsort
Les tableaux de Java utilisent actuellement Timsort dans Java 7 afin de trier les objets (
Trier () ). Description de Timsort ici .
Trouver le meilleur algorithme de tri dépend quel point le contrôle que vous avez sur les données.
algorithmes de tri sont classés dans les méthodes d'insertion, l'échange, la sélection, la fusion, etc .. Cela signifie que si vous pouvez contrôler le mécanisme qui insère de nouvelles données sur le tableau, vous pouvez les trier tout en faisant cela. Si vous ne pouvez trier le tableau après les données sont là, le meilleur algorithme pour le faire est un autre complètement différent.
Quoi qu'il en soit, ce sont des lectures intéressantes:
http://en.wikipedia.org/wiki/Sorting_algorithm
ce que devraient-étudiants-être enseignés, premier quand-premier apprentissage tri-algorithmes
aujourd'hui, le Ainsi, lisez votre documentation de libc ou encore mieux, vérifiez comment il implémente le tri (si vous avez accès à la source), car il s'agit parfois d'un détail de mise en œuvre non établi sur les docs! qsort ou fusion des fonctions fournies par la plupart des implémentations de libc gère déjà ce cas particulier de manière efficace.
Vous pouvez ajouter «algorithme» dans votre balise. Peut-être qu'ils peuvent aider aussi aussi.
Quelles sont vos valeurs? Ints ou flotteurs simples, ou des structures? Quelle est votre mesure d'efficacité? espacer ? temps ?
Mec, vous avez sérieusement besoin de revenir en arrière et de revoir vos questions et d'accepter certains.