Comparaison entre timsort et quicksort

Question

Pourquoi est-ce que j'entends souvent dire que Quicksort est l'algorithme de tri global le plus rapide alors que Timsort (d'après wikipedia ) semble donner de bien meilleurs résultats ? Google ne semble pas avoir trouvé de comparaison.

Answer 1

TimSort est un mergesort hautement optimisé, il est stable et plus rapide que les anciens mergesort.

par rapport au tri sélectif, il présente deux avantages :

1. Il est incroyablement rapide pour toutes les séquences de données triées (y compris les données triées à l'envers) ;
2. Dans le pire des cas, il s'agit toujours de O(N*LOG(N)).

Pour être honnête, je ne pense pas que le numéro 1 soit un avantage, mais il m'a impressionné.

Voici les avantages de QuickSort

1. QuickSort est très très simple, même une implémentation hautement optimisée, nous pouvons écrire ses codes pseduo en moins de 20 lignes ;
2. QuickSort est le plus rapide dans la plupart des cas ;
3. La consommation de mémoire est de LOG(N).

Actuellement, le SDK Java 7 met en œuvre le tri temporel et une nouvelle variante de tri rapide : le Dual Pivot QuickSort.

Si vous avez besoin d'un tri stable, essayez timsort, sinon commencez par quicksort.

Answer 2

Plus ou moins, c'est lié au fait que Timsort est un algorithme de tri hybride. Cela signifie que si les deux tris sous-jacents qu'il utilise (Mergesort et Insertion sort) sont tous deux moins bons que le Tri sélectif pour de nombreux types de données, Timsort ne les utilise que lorsqu'il est avantageux de le faire.

A un niveau un peu plus profond, en tant que Patrick87 le tri sélectif est, dans le pire des cas, une méthode O(n 2 ). Le choix d'un bon pivot n'est pas dur mais la garantie d'un tri sélectif O(n log n) se fait au prix d'un tri généralement plus lent en moyenne.

Pour plus de détails sur Timsort, voir cette réponse et l'article de blog en lien. Il part du principe que la plupart des données sont déjà partiellement triées, et construit des "séries" de données triées qui permettent des fusions efficaces à l'aide de mergesort.

Answer 3

D'une manière générale, le tri sélectif est le meilleur algorithme pour les tableaux primitifs. Cela est dû à la localité de la mémoire et au cache.

JDK7 utilise TimSort pour les tableaux d'objets. Le tableau d'objets ne contient que des références d'objets. L'objet lui-même est stocké dans le tas. Pour comparer un objet, nous devons lire l'objet dans le tas. Cela revient à lire un objet dans une partie du tas, puis à lire l'objet au hasard dans une autre partie du tas. Il y aura beaucoup de manques dans le cache. Je suppose que c'est pour cette raison que la localité de la mémoire n'est plus importante. C'est peut-être la raison pour laquelle le JDK n'utilise TimSort que pour les tableaux d'objets et non pour les tableaux primitifs.

Ce n'est qu'une supposition.

Answer 4

Voici les résultats des tests effectués sur ma machine (i7-6700 CPU, 3.4GHz, Ubuntu 16.04, gcc 5.4.0, paramètres : SIZE=100000 et RUNS=3) :

$ ./demo 
Running tests
stdlib qsort time:                 12246.33 us per iteration
##quick sort time:                  5822.00 us per iteration
merge sort time:                    8244.33 us per iteration
...    
##tim sort time:                    7695.33 us per iteration
in-place merge sort time:           6788.00 us per iteration    
sqrt sort time:                     7289.33 us per iteration    
...
grail sort dyn buffer sort time:    7856.67 us per iteration

Le point de référence provient de l'étude de Swenson trier dans lequel il a mis en œuvre plusieurs algorithmes de tri en C. Vraisemblablement Il est vrai que ses implémentations sont suffisamment bonnes pour être représentatives, mais je ne les ai pas étudiées.

On ne peut donc pas vraiment savoir. Les chiffres de référence ne restent pertinents que pendant deux ans au maximum, après quoi il faut les répéter. Il est possible que timsort ait battu qsort en 2011 lorsque la question a été posée, mais les temps ont changé. Ou bien qsort a toujours été le plus rapide, mais timsort l'a battu sur des données non aléatoires. Ou le code de Swenson n'est pas si bon et un meilleur programmeur ferait pencher la balance en faveur de timsort. Ou peut-être que je suis nul et que je n'ai pas utilisé le bon code de CFLAGS lors de la compilation du code. Ou... Vous voyez ce que je veux dire.

Answer 5

Tim Sort est idéal si vous avez besoin d'un tri préservant l'ordre, ou si vous triez un tableau complexe (comparant des objets basés sur le tas) plutôt qu'un tableau primitif. Comme d'autres l'ont mentionné, le tri rapide bénéficie considérablement de la localité des données et de la mise en cache du processeur pour les tableaux primitifs.

Le fait que le pire cas de quicksort est O(n^2) a été soulevé. Heureusement, il est possible d'obtenir un temps O(n log n) dans le pire des cas avec le tri sélectif. Le pire cas de quicksort se produit lorsque le point pivot est la plus petite ou la plus grande valeur, par exemple lorsque le pivot est le premier ou le dernier élément d'un tableau déjà trié.

Nous pouvons obtenir un tri sélectif O(n log n) dans le pire des cas en fixant le pivot à la valeur médiane. Puisque la recherche de la valeur médiane peut être effectuée en temps linéaire O(n). Puisque O(n) + O(n log n) = O(n log n), cela devient la complexité temporelle la plus défavorable.

Dans la pratique, cependant, la plupart des implémentations estiment qu'un pivot aléatoire est suffisant et ne recherchent donc pas la valeur médiane.