30

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

31

>Miles: C'est possible de descendre en dessous de n*ln(n). Va lire le bouquin 'Intro a l'algorithmique'. C'est tres bien developpe (trie lineaire).

32

Désolé PpHd, mais un vrai tri est en n*ln(n). Si tu descend en dessous, c'est que tu connais des infos supplémentaires. Par ex, le tri par comptage sait que ce qui est à trier est des nombres compris entre X et Y. Dans ce cas, c'est linéaire. Mais c'est pas un tri au sens propre du terme.

Démonstration par les arbres.

L'arbre de comparaison est simple : A chaque noeud, on teste si la valeur - pas forcément un nombre - est plus grand ou plus petit que la valeur du noeud. On passe à gauche ou à droite selon les cas. L'arbre a une profondeur en ln(n).
Maintenant, supposons qu'il existe un arbre plus court : un test ne sera pas fait, et donc le nombre sera mal classé, et donc le tri plante. - démo un peu pas très clair, mais j'ai pas mon cours d'algo sur moi -.

CQFD
Site : http://www.phareaway.com/
Membre du groupe Phare Away et webmaster du site

33

moi j'en serais bien incapable smile
mais je confirme ce ke j'ai entendu : un algo de tri comparatif ne peut pas se comporter mieux que du n.ln(n) ... mais c franchement pas trop mal comme truc :]

mais il faut considerer le pire des cas bien entendu : sinon il y a pleins de tris qui sont lineaires suivants le tableau qu'on leur donne a manger smile

et surtout le n.ln(n) c'est une approximation asymptotique du comportement du tri : donc il est vrai pour un tableau comportant pas mal de valeurs ... mais pour un petit tableau de 10 elements se sera pas forcement vrai smile
avatar
pwet

34

>Miles: Va lire ce chapitre. Tout y est tres bien explique. Oui, ce sont des tries par index. Et oui, il faut connaitre la borne max et la borne min. Mais leur calcul reste lineaire smile

35

lol g posté en reponse a oxman sans voir qu'il y avait 2 pages :þ
avatar
pwet

36

oui, je l'ai déjà fais aussi ça !
c pas très clair, je suis d'accord !
:D

37

PpHd > Merci , mais je connaît déjà le tri linéaire qui bel et bien en temps linéaire, mais pas très pratique pour trier des noms et des trucs comme ça.
Autrement, pour répondre à Billy-Bob, une véritable valeur de tri est plutôt ln(n!) pour n valeurs.
Site : http://www.phareaway.com/
Membre du groupe Phare Away et webmaster du site