Quel algorithme de tri fonctionne le mieux sur la plupart des données triées?

Question

Quel algorithme de tri fonctionne le mieux sur la plupart des données triées?

Answer 1

Basé sur la méthode hautement scientifique de regarder des gifs animés, je dirais que les sortes d'insertion et de bulles sont de bons candidats.

Answer 2

Seulement quelques articles => TRI D'INSERTION

Les articles sont pour la plupart déjà triés => TRI D'INSERTION

Préoccupé par les pires scénarios => HEAP SORT

Intéressé par un bon résultat moyen => QUICKSORT

Les articles sont tirés d'un univers dense => BUCKET SORT

Désir d'écrire le moins de code possible => INSERTION SORT

Answer 3

timsort

Timsort est "une adaptation, stable, naturel mergesort" avec "surnaturel performances sur de nombreux sortes partiellement ordonné des tableaux (moins de lg(N!) comparaisons nécessaires, et aussi peu que N-1)". Python intégré dans l' sort() a utilisé cet algorithme pour un certain temps, apparemment, avec de bons résultats. Il est spécifiquement conçu pour détecter et prendre avantage de partiellement trié de sous-séquences dans l'entrée, qui se produisent souvent dans la vraie ensembles de données. C'est souvent le cas dans le monde réel que les comparaisons sont beaucoup plus cher que la permutation des éléments dans une liste, puisque celle généralement juste swaps de pointeurs, ce qui rend très souvent timsort un excellent choix. Toutefois, si vous savez que vos comparaisons sont toujours très bas prix (rédaction d'un jouet de programme pour trier les nombres entiers de 32 bits, par exemple), d'autres algorithmes existent qui sont susceptibles de faire mieux. La meilleure façon de profiter de timsort est bien sûr d'utiliser Python, mais depuis le Python est open source, vous pouvez également être en mesure d'emprunter le code. Alternativement, la description ci-dessus contient plus de suffisamment de détails pour écrire votre propre mise en œuvre.

Answer 4

Le tri par Insertion avec le comportement suivant:

1. Pour chaque élément, k des logements 1..n, vérifiez d'abord si el[k] >= el[k-1]. Si oui, passez à l'élément suivant. (Évidemment ignorer le premier élément.)
2. Si non, utiliser les binaires de recherche en éléments 1..k-1 afin de déterminer l'emplacement de l'insertion, puis scoot les éléments en plus. (Vous pouvez faire cela seulement si k>T où T est certaine valeur de seuil; avec de petits k c'est exagéré.)

Cette méthode rend le moins nombre de comparaisons.

Answer 5

Essayez introspective de tri. http://en.wikipedia.org/wiki/Introsort

C'est quicksort, mais il évite le pire des cas, le comportement que quicksort a près de listes triées.

Le truc, c'est que ce genre-algorithme détecte les cas où quicksort va dans le pire des cas, le mode et les commutateurs de tas ou de fusion de tri. Presque trié les partitions sont détectés par certains non naiive partition de méthode et de petites partitions sont gérées en utilisant le tri par insertion.

Vous obtenez le meilleur de tous les principaux algorithmes de tri pour le coût d'un plus code et de la complexité. Et vous pouvez être sûr que vous ne serez jamais à court dans le pire des cas, le comportement peu importe la façon dont vos données ressemble.

Si vous êtes un programmeur C++ vérifier votre std::algorithme de tri. Il peut déjà utiliser introspective de tri en interne.