Le meilleur algorithme de tri - Page 1

je viens de trouver un site très bien fait expliquant les différents algorithmes de tri, et surtt, proposant une expliquation visuelle animée du fonctionnement de ces algorithmes... et on comprend tt de suite!

jusqu'à présent, le meilleur algorithme de tri que j'aie trouvé est le radix sort...
mieux à mon avis que quicksort.

si vous connaissez d'autres algos plus efficaces que le radix sort, dites le!
sinon, pour en faire profiter tt le monde, je donne les url:

pour quicksort:

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/qsort.html
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/qsort1a.html

et pour radix sort:

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/radixsort.html

la page dit que le temps d'exécution est le même que pour quicksort, mais je pense qu'on doit pouvoir optimiser radix sort bien plus que quick sort...

et merde! double post de topic

yAro, tu peux le fermer stp?

Le gros problème de quisort c'est l'occupation de la pile. Dans le pire cas, à savoir si tu pars avec un tableau rangé dans le sens inverse du sens voulu, tu auras n appels récursifs. Généralement quisort s'utilise avec d'autres algos : quand le sous-tableau à trier devient inférieur à une certaine longueur, on revient à un algo classique, ce qui permet de limiter l'usage de la pile.
Si je me souviens bien, quisort nécessite deux ou trois variables locales (passées en paramètre?). Soit mettons 6 octets (en 16 bits), plus l'appel de la fonction : ça doit faire 10 octets pour chaque appel. Donc sur TI on peut théoriquement saturer la pile avec un tableau de 1500 éléments. Ce qui ne laisse vraiment pas beucoup de marge.

moui... sinon, le radix sort, il serait mieux de ce pt de vue là?

Il n'y a pas de meilleur tri
Chaque tri a ses points forts et ses faiblesses !
Par exemple le pire des cas pour le quicksort c de se retrouver en face d'un tableua deja trié ... donc si on utilise des tableaux deja triés ou peu melangés le quicksort est a eviter.
Si on a des tableaux tres melangés le quicksort est l'un des plus efficace

Bref a chaque situation il faut utiliser un algo de tri qui convient bien

j'avais entendu dire que le plus rapide algo de tri etais le tri par bulle ! non ?

si le tableau à trier a une probabilité égale d'être totalement trié ou totalement détrié, et pour que le temps d'exécution soit indépendant de ce facteur, c quoi le mieux alors?
pour trier environ 500 valeurs...

mon prof d'alogo dit que le tri le plus rapide est la méthode par récursion, après, je peux pas te dire si c'est le meilleur en fonction de tel ou tel cas, vala

et ça consiste en koi, cet algo?

c pas le tri par insertion ?

c comme le tri à bulles...
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/sorting.html#bubble

ouais trie par insertion=récursivité

ya un bookin ultime sur ça. PpHd en avait parler sur l'ancien Forum.
c'est "Introduction à l'algorythmique"
ya tout dedans,notament le premier chap. qui est sur le trie avec tout qu'est expliqué;meme si t'es con,tu comprends,mais ça demenage pas mal quand meme.
le book fait 1300 page pour 350 francs,mais c'est une bible pour tout codeur qui se respecte.
par contre,faut utiliser le c ou l'asm, en basic ça sert peu.(vu qu'on peut rien faire en basic,ou alors c'est de suite tres lent.)

ce bouquin, je l'ai
et personne n'a parlé de basic ici
seulement, ce boukin ne répertorie pas tous les algos de tri... par exemple, il n'y a pas le radix sort...

sur mon boukin, j'ai:

- tri par insertion
- tri rapide
- tri par fusion
- tri par comptage
- tri par base
- tri par dichotomie

Maitrise des algorithmes en C Kyle Loudon
donc, pas de radix

pff meme pas le tri par bulle !

tri par bulles-tri par insertion>même chose , c just une petite variante du tri par insertion...

oui ... pis ce boukin est plutot nickel.. je le conseille pas mal ..

sBibi: le tri par insertion n'a pas grand chose à voire avec le tri à bulle regardons par exemple le pire des cas: pour le tri a bulle n(n-1)/2 operations contre n-1 (si je ne me trompe pas) pour le tri par insertion...
Sinon, un autre bouquin sympa est celui de Sedgewick: algorithmes en C.

zewoo> c une variante...

le tri a bulles est un algo dont la complexite est en theta de n²
c clairement pas un algo efficace :]
il y a des tris dont la complexite est quand meme un peu mieux : le quick sort dans des cas favorable, le tri fucion aussi

Bon. J'ai compris. Un petit cours sur les tris.
Le meilleur tri est n*ln(n) parce que c'est la taille de l'arbre associé.
- Le tri par comptage n'est pas un vrai tri : il compte le nomnbre d'occurence d'un objet puis les insère dans un tableau.
- le tri par insertion insère dans un tableau trié un nombre.
- le tri par bulle fait monter dans le tableau complet le plus grand nombre puis recommence sur le tableau plus petit - itératif, et non récursif -
Ces algos sont en n^2.
- le quicksort n'est pas un tri rapide : au mieux n*ln(n), au pire n^2. Il consiste à prendre un nombre dans le tableau, puis classer de part et d'autre les nombres plus grands et plus peties, puis recommence sur les sous-tablmeaux.
- le tri fusion est le plus rapide car toujours en n*ln(n) : il fusionne 2 tableaux classés. Son problème est qu'il est récursif et non sur place - quicksort est sur place -

quicksort ne nécessite d'ailleurs pas de paramètre particulier : il prend en paramètre un tableau. Le problème avec celui-ci est que le nombre qui sert de pivot doit être bien choisi : si il est bien le médian, on est en n*ln(n).

Autre chose : le tri par insertion nécessite au max n-1 comparaisons pour 1 insertion alors qu'on veux en faire plus.

c peu faux ce ke tu dis Miles

1 - le quick sort est recursif !
2 - dans le pire des cas c du n² et dans le cas moyen et le meilleur des cas c du n*ln n et dans ces 2 cas la le facteur caché du n*ln n est le plus bas de tous les algos que tu cites
3 - pivot bien choisi = median ... ca veut dire koi ? que pour bien choisir le pivot il faut choisir l'element du milieu du tableau ? ... ben pas du tout ... ce n'est pas comme ca qu'on choisit le pivot et la place du pivot ne determine pas la complexite !
4 - le meilleur tri en n*ln n : et bien pas vraiment ... le meilleur tri comparatif ne peut etre qu'en n*ln n mais y a peut-etre d'autres methode de tri ...
5 - le tri par intertion ne fonctionne pas vraiment comme tu le dis )
6 - les 3 premiers algo sont en n² dans le pire des cas seulement et peut-etre dans le cas moyen mais ca je sais pas ;o)
7 - il n'existe pas de meilleur tri que les autres : chaque tri est plus adapté a une situation particuliere [sauf certain tri vraiment pourri qui sont mauvais tout le temps ] ! Donc en general pour un programme on utilise un algo de tri qui fonctionnera bien avec le type de donnees a traiter :]

Sans conteste, le tri fusion (implemente par genalib), qui travaille sur place !
(Mais on perd un petit truc).

Bill-Bob >
1 - J'ai dit où qu'il n'était pas récursif ?
2 - ça dépend de ton implémentation.
3 - J'ai pas dit qu'il falait prendre le médian, mais celui qui aurait le même nombre de nombre plus grands et plus petits. Regarde à ta définition en proba de médian.
4 - Le meilleur tri ne peut être qu'en n*ln(n). Si quelqu'un veut, je peut le lui démontrer.
5 - Il fonctionne comment alors - je peux me tromper, je suis aussi humain - ?
6 - ils sont n^2 dans le cas moyen
7 - En général quicksort puis tri fusion si il y a beaucoup de valeur.

Erreur : Effectivement, fusion est sur place et facile à implémenter.

Bil-Bob> "le pire des cas pour le quicksort c de se retrouver en face d'un tableua deja trié "

C'est pas plutôt quand le tableau est trié dans l'ordre inverse ?

le tri tas est en place, et au pire des cas en n*ln(n)

Blue_Z> En fait, les deux sont les pires cas, parce que les sous-tableaux sont déséquilibrés

Quenalma> et au mieux aussi en n*ln(n)

tu peux me demontrer qu'un algo de trie ne peux pas descendre en dessou de n*ln(n) stp
merci :]