Le meilleur algorithme de tri - Page 2

>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).

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

moi j'en serais bien incapable
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

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

>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

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

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

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.