Comparaison entre timsort et quicksort

plus ou moins, il a à voir avec le fait que Timsort est un algorithme de tri hybride. Cela signifie que bien que les deux types sous-jacents qu'il utilise (Mergesort et Insertion sort) sont à la fois pire que Quicksort pour de nombreux types de données, Timsort ne les utilise que lorsqu'il est avantageux de le faire.

à un niveau légèrement plus profond, comme l'indique Patrick87 , quicksort est le pire des cas O (N ² ) de l'algorithme. Choisir un bon pivot n'est pas dur , mais garantir un O(N log n) quicksort vient au prix d'un tri généralement plus lent en moyenne.

pour plus de détails sur Timsort, voir cette réponse , et le billet de blog lié. Il suppose essentiellement que la plupart des données sont déjà partiellement triées, et construit "exécute" des données triées qui permettent des fusions efficaces en utilisant mergesort.

Généralement parlant quicksort est le meilleur algorithme pour le tableau primitif. Ceci est dû à la localisation de la mémoire et à la mémoire cache.

JDK7 utilise TimSort pour Object array. Le tableau d'objets ne contient que des références d'objets. L'objet lui-même est stocké en Tas. Pour comparer l'objet, nous devons lire l'objet de tas. C'est comme lire d'une partie du tas pour un objet, puis lire au hasard un objet d'une autre partie du tas. Il y aura beaucoup de cache manqué. Je suppose que pour cette raison localité de mémoire n'est pas plus importants. C'est peut-être la raison pour laquelle JDK n'utilise TimSort que pour Object array à la place si primitive array.

Ce n'est que mon avis.

Voici les numéros de référence de mon appareil (i7-6700 CPU, 3,4 GHz, 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 benchmark provient du projet sort de Swenson dans lequel il a mis en œuvre plusieurs algorithmes de tri en C. présumément , ses implémentations sont assez bonnes pour être représentatives, mais je ne les ai pas étudiées.

donc tu ne peux vraiment pas dire. Les chiffres de référence ne restent pertinents que pendant deux ans au plus et vous devez les répéter. Il est possible que timsort ait battu qsort waaay en 2011 lorsque la question a été posée, mais les temps ont changé. Ou 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 très bon et un meilleur programmeur changerait la donne en faveur de timsort. Ou peut-être que je suis nul et que je n'ai pas utilisé le bon CFLAGS lors de la compilation du code. Ou... Vous obtenez le point.

Je ne peux pas utiliser java sort standard dans codeforces concours de programmation, parce que java utilise double pivot quicksort pour les tableaux entiers et doubles, et donc il existe des tableaux qui exigent O(N^2) temps d'exécuter. Et certaines données de test sont souvent composées avec ces tableaux, donc le programme prend trop de temps et échoue. Donc je dois passer à mon propre mergeSort à la place. Cela ne peut pas se produire avec l'algorithme de timsort.