Algorithme de tri - Page 2

De toute facon, de bien choisir son elmt de référence pour le tri fusion et c'est bon, on a le meilleur tri.

Kevin Kofler
:

liquid
: quicksort, c le tri rapide ? selon les donnees que tu as a trier et le nbre d'elements, il est plus efficace que le tri fusion (O(nlog(n) contre O(n²) (d'apres mes souvenirs hein))

Tes souvenirs sont mauvais. C'est le tri fusion le plus efficace asymptotiquement dans le pire des cas (O(n log n) contre O(n²)).

hu ? c'est le tri fusion en nlog(n) et le quicksort en n² ? merci pour l'info :]

nEUrOO
: De toute facon, de bien choisir son elmt de référence pour le tri fusion et c'est bon, on a le meilleur tri.

Le quicksort tu veux dire, non?

hu ? c'est le tri fusion en nlog(n) et le quicksort en n² ? merci pour l'info :]

Pour le tri fusion, on coupe en deux parties égales à chaque fois, et on fait un traitement linéaire pour les réunir. Ca fait bien du n.log(n)

Merci pour toutes ces réponses je vais bosser les liens et les codes sources.
(pas mal le lien http://www-ipst.u-strasbg.fr/ipst/deug-ti/aide-c/tris/sommaire.htm
jibax je veux bien que tu m'envoie ça.
Si vous avez des trucs sous Mapple ça m'intéresse aussi.
Voilà encore merci et si vous avez des progs tout fait compilé ?

liquid > euh j'ai oublié la balise troll dans mon premier post ... il est vrai que si, mais seulement si, tu sais ce que tu manipules, le quicksort peut être le meilleur.
Mais bon en fait si je ne l'aime pas c'est pas seulement parce qu'il est très mauvais dans le pire cas et qu'en plus le pire cas est un cas simple, c'est surtout parce que je le trouve moche et beaucoup trop tordu, alors que le tri fusion est simple et élégant

Mon prof de scheme a dit la même chose ...

ouais, helas mon prof dit "tri rapide c le meilleur ds la plupart des cas" et c'est vrai que c difficile a realiser

Moi je le trouve pas moche du tout, je trouve que c'est sympa l'idée du partitionnement. ^^

Smile :
je voudrais qu'il soit programmé c pour un TIPE c pour comparer différent algorithme de tri Donc il me faut des pas performants et des performants

mauvais plan. C'est entièrement au cours d'info, donc tu vas droit dans le mur, mais ce n'est que mon avis...

Pas s'il calcule les complexités de chaque algo.
Il peut faire rentrer ça ds Maths+Info, ce qui passe s'il est en MP option Info

Mais bon c'est vrai qu'il y avait d'autres thèmes un peu plus diversifiés surement mais s'il a commencé les tris, je pense pas que c'est fin janvier qu'il va commencer un nouveau TIPE.

Pourquoi pas ?
TIPE rédigé en trois jours à l'arrache powa

Ca c'est un savoir faire dont je ne disposais pas
3 jours ? Je crois que t'es le nouveau record !

TIPE rédigé en trois jours à l'arrache powa

TIPE qui ne dépasse pas le stade du brouillon powa

Euh mais ça fait une moins bonne note dans ce cas non ?

Ben non, pkoi, tu t'es quand même pas fait chier à mettre ton TIPE au propre?

Bah pour moi brouillon ça veut dire pas de transparents donc il y a un minimum à mettre au propre quand même nan ?

Euuuuh à l'époque où j'ai passé le concours fallait rendre un rapport de je crois entre 5 et 10 pages en même temps qu'on s'inscrivait aux oraux

Bah oui, mais tu rends un brouillon normalement, non?

Bah pour moi brouillon ça veut dire Ah zut c'est demain qu'il faut rendre le dossier pour les ens, je savais pas, bon allez hop photocopies et ratures powaa..

Hum c'était quand même vraiment crade.. => 11

./49 > Ah oui, je vois ce que tu veux dire, bon ouais en fait j'ai essayé d'écrire à peu près droit au stylo noir sur une feuille blanche, et sans faire de rature quand même (tipp-ex powa quand c'est pour faire des photocopies )
Mais le truc c'est que quand j'ai su que je devais le rendre trois jours plus tard je n'avais même pas encore choisi le sujet, et encore moins écrit le moindre mot (bon bien sûr j'avais une vague idée de thème (les nombres diophantiens), et j'avais quand même fait l'effort de me procurer et de feuilleter deux bouquins dans les deux mois qui avaient précédé... mais fin janvier j'étais loin d'avoir commencé )
Enfin j'ai eu 15, pas si mal

Sburb :
Pas s'il calcule les complexités de chaque algo.
Il peut faire rentrer ça ds Maths+Info, ce qui passe s'il est en MP option Info
Mais bon c'est vrai qu'il y avait d'autres thèmes un peu plus diversifiés surement mais s'il a commencé les tris, je pense pas que c'est fin janvier qu'il va commencer un nouveau TIPE.

On a calculé les complexités en cours d'info...

Oups je voulais dire option SI ...
Enfin ça peut paraitre bizarre de faire de l'info en MP option SI mais l'année dernière il y en a un qui a fait ce sujet et je crois qu'il a eu 16 ou qq chose comme ça. Donc ca passe

Sburb :
Oups je voulais dire option SI ...
Enfin ça peut paraitre bizarre de faire de l'info en MP option SI mais l'année dernière il y en a un qui a fait ce sujet et je crois qu'il a eu 16 ou qq chose comme ça. Donc ca passe

ouh la, pas bon, si qqn l'a déjà fait...
De plus, un SI doit rester en maths/phy/SI, non ? Si tel n'est pas le cas, tant mieux
Sinon, faut bien voir qu'une partie du TIPE, c'est de la recherche d'info et l'autre, c'est du travail perso dessus. Donc si tout a déjà été fait, y'a plus la partie perso, d'autant que si qqn a déjà fait le TIPE là-dessus, il vaut mieux aller beaucoup plus loin que ce TIPE là pour que les examinateurs ne pensent pas à la recopie brutale. en gros, faut faire gaffe...

C'est une personne de ma prépa qui l'a fait et il y a pas d'infos autre part donc il n'aura pas de problème avec la recherche perso.
Sinon il faudra qu'il fasse attention parce que ça s'est bien passé au TIPE mais les profs de prépa trouvaient que ce type de sujet amène une organisation type catalogue qui est pas géniale.
Enfin normalement un SI doit rester en maths/phy/SI mais bon apparement ça dérange personne s'il y a un peu de maths dedans.

Personne n'a parle du Count Sort ? Etrange. C'est pourtant le plus rapide.

Pas franchement. O(max(card V,card([min V,max V]))), sans même parler du cas où l'ordre est dense (chaînes de caractères)... Ce qui ne l'empêche pas d'être efficace dans un certain nb de cas particuliers, bien sûr.

Je parlais d'un Count Sort optimise qui delegue automatiquement s'il se rend compte qu'il ne peut pas etre rapide. La premiere passe reste en O(n).

OK. Cela dit si le programmeur n'a pas prévu d'optimiser pour ça, on peut se retrouver avec des surprises (programme qui "normalement" tourne vite mais qui avec une petite modif tourne 10x plus lentement).