Trier 4 éléments. - Page 2

Thibaut (./18) :
Le calcul d'une factorielle prend un temps et une mémoire gigantesque avec des nombres pourtant raisonnables (ex : n=100). Et puis, après, pour faire un log sur un nombre de 3 millions de chiffres, bonjour !

Ben c'est facile, ça fait 3 millions*log(10)

Hippopotame (./7) :
Si a, b, c et d sont les 4 éléments à trier.

Permuter a et b au besoin pour que a<b (I)

De même pour que c<d (II)

De même permuter au besoin a et c pour que a<c (III)

De même pour que b<d (IV)

A ce stade, on sait que a est le plus petit élément et d le plus grand.

Reste à permuter éventuellement b et c pour que b<c. (V)



Ca fait 5 comparaisons et on ne peut pas faire mieux et on peut le démontrer mais flemme.

ça ne marche pas tout à fait, ton étape (III) peut casser les étapes (I) et (II) ; ça peut se réparer en disant de permuter au besoin (a,b) et (c,d) et pas juste a et c, mais du coup l'étape (IV) ne peut plus marcher... cela dit ça se résoud facilement en distinguant le cas b<d et b>d : si b<d, on continue avec (V), et si b>d alors a<c<d<b donc c'est fini ; ou bien on peut voir ça d'une autre façon en disant qu'on a éliminé l'élément minimal a, et qu'il ne reste plus qu'à trier {b,c,d} en sachant qu'on s'est déjà débrouillé pour que c<d



mais bon dans le cas général on a besoin de plus que la borne inférieure ceiling(log(n!)) comparaisons pour trier n éléments : pour n=12, il faut 30 comparaisons, alors que 12! < 2^29...

Tiens t'as une preuve de ça (ou même la liste des nombres minimum prouvés de comparaisons pour trier n éléments) ?
Ca fait longtemps que je me demande dans quelle mesure on peut se rapprocher de la borne optimale, et je ne vois pas de raison a priori pour laquelle on ne pourrait pas le faire...

je crois pas que ça ait été prouvé autrement que par recherche exhaustive sur tous les arbres de tri

pour la liste et les références : http://www.research.att.com/~njas/sequences/A036604

super