Je ne vais pas le redémontrer mais.
La complexité (en nombre de comparaisons) dans le pire des cas d'un
algorithme de tri est n.log(n). On connait beaucoup d'algorithmes qui
ont cette complexité dans le pire des cas (entre autre merge-sort et heap-sort)
et un certain nombre qui l'on en moyenne (quick-sort).
Personne n'utilise merge sort car ce n'est pas un algorithme en place (on
recopie les infos et on a besoin de deux fois plus de mémoire).
Tout le monde utilise quick-sort car il fonctionne en placeet a une très faible
constante cachée (mieux vaut du 2n.log(n) en pratique mais pas tout le temps
que du 100000n.log(n) toujours).
Ceci dit, il existe effectivement des algorithmes très efficace dans des cas
particuliers. Bucket sort en fait partie. Si tu sais que tu dois trier une liste
contenant tous les entiers de 1 à n, ben tu lis les entiers et tu les mets
directement dans la bonne case.
Pour information, le sort d'unix est un quick-sort. Or, quick-sort compare les
premiers éléments de la liste et les derniers elements de la liste à un "pivot".
C'est très mauvais dans pas mal de cas. Pour s'en rendre compte, imaginez
ce qui se passe si on doit trier les éléments d'une bande magnétique?
Paf, je vais chercher le premier élément, paf je vais chercher le dernier,
paf, je vais chercher le second élément... Bref, vous avez l'idée.
De nos jours, il y a une telle différence entre l'accès mémoire et le
fonctionnement du processeur qu'il est beaucoup plus rentable d'optimiser
les accès mémoire que le temps de calcul. Le sort d'unix ne le fait pas. Il
est donc normal qu'il se fasse enfoncer.
# glou
Posté par fmaz fmaz . En réponse au journal M'enfin ?? .... Évalué à 10.
Je ne vais pas le redémontrer mais.
La complexité (en nombre de comparaisons) dans le pire des cas d'un
algorithme de tri est n.log(n). On connait beaucoup d'algorithmes qui
ont cette complexité dans le pire des cas (entre autre merge-sort et heap-sort)
et un certain nombre qui l'on en moyenne (quick-sort).
Personne n'utilise merge sort car ce n'est pas un algorithme en place (on
recopie les infos et on a besoin de deux fois plus de mémoire).
Tout le monde utilise quick-sort car il fonctionne en placeet a une très faible
constante cachée (mieux vaut du 2n.log(n) en pratique mais pas tout le temps
que du 100000n.log(n) toujours).
Ceci dit, il existe effectivement des algorithmes très efficace dans des cas
particuliers. Bucket sort en fait partie. Si tu sais que tu dois trier une liste
contenant tous les entiers de 1 à n, ben tu lis les entiers et tu les mets
directement dans la bonne case.
Pour information, le sort d'unix est un quick-sort. Or, quick-sort compare les
premiers éléments de la liste et les derniers elements de la liste à un "pivot".
C'est très mauvais dans pas mal de cas. Pour s'en rendre compte, imaginez
ce qui se passe si on doit trier les éléments d'une bande magnétique?
Paf, je vais chercher le premier élément, paf je vais chercher le dernier,
paf, je vais chercher le second élément... Bref, vous avez l'idée.
De nos jours, il y a une telle différence entre l'accès mémoire et le
fonctionnement du processeur qu'il est beaucoup plus rentable d'optimiser
les accès mémoire que le temps de calcul. Le sort d'unix ne le fait pas. Il
est donc normal qu'il se fasse enfoncer.
Frédéric