Limites des techniques de tri par comparaison

Question

Le tri par comparaison est opté dans la plupart des scénarios où les données doivent être classées. Des techniques telles que le tri par fusion, le tri rapide, le tri par insertion et d'autres types de comparaison peuvent gérer différents types de données et leur efficacité avec une limite inférieure de O (nLog (n)).

Mes questions sont

1. Y at-il des limites des techniques de tri par comparaison?
2. Tout type de scénario où des techniques de tri sans comparaison seraient utilisées?

acclamations

Answer 1

Vous avez répondu plus ou moins vous. Les techniques de tri basées sur la comparaison sont limitées à la limite inférieure de O (n Log (n)). Les techniques de tri sans comparaison ne souffrent pas de cette limite. Le problème général avec les algorithmes de non-tri est que le domaine doit être mieux connu et pour cette raison ils ne sont pas aussi polyvalents que les techniques de comparaison.

Pigeonhole sort est un exemple simple et très simple qui est assez rapide tant que le nombre de valeurs de clé possibles est proche du nombre d'éléments.

Answer 2

Il est évident que les limitations des tris de comparaison sont le facteur temps - some are better than others, mais étant donné un ensemble de données suffisamment important, elles deviendront toutes trop lentes à un moment donné. L'astuce consiste à choisir la bonne étant donné le type et la combinaison de données que vous triez.

Le tri sans comparaison est basé sur d'autres facteurs ignorant les données, par exemple counting sort ordonnera une collection de données, en inspectant chaque élément - ne le comparant avec aucune autre valeur dans la collection. Le tri par comptage est utile pour commander une collection basée sur certaines données, si vous aviez une collection d'entiers, il les ordonnerait en prenant tous les éléments avec la valeur 1 et en les mettant d'abord dans la destination, puis tous les éléments de valeur 2 etc. (ok, il utilise un tableau "sparse" pour zoomer rapidement sur la collection et réorganiser les valeurs, laissant des espaces mais c'est le principe de base)

Answer 3

Il est facile de voir pourquoi le tri par comparaison nécessite environ N comparaisons N. Il y a N! permutations et comme nous le savons ln (N!) est approximativement N ln N - N + O (ln N). En grande notation O, on peut négliger les termes inférieurs à N ln N, et comme ln et log ne diffèrent que par la constante, on obtient le résultat final O (N log N)