ya qq qui a une idee sur ce genre de tri
Version imprimable
ya qq qui a une idee sur ce genre de tri
Non8O pourtant j'ai fait pas mal d'algo ... Mais mon ami :google: me dit
http://hyatus.newffr.com/TAZ/Coding/algo_tri.pdf
D'ailleurs, j´ai pas le temps de lire dans les détails, alors un petit résumé de ta part sera le bienvenu:roll:
merci bien pour ton aide mais ya qq qui peut m'expliquer d'une facon facile ce genre de tri difficileCitation:
Envoyé par harsh
aparament ce sujet merite d'etre un debat car personne presque n'a idee sur ce project
merci infinement
Il peut aussi être instructif de consulter les Numerical recipes dont les livre est disponible sur
http://www.library.cornell.edu/nr/cbookcpdf.html
le chapitre 8 est dédicacé aux méthodes de tri
merci infinement
chers amis pouvez vous m'éclairer beaucoup sur les algorithmes du tri EQUILIBRE et du tri POLYPHASE (le plus important pour moi est l'EQUILIBRE) car je trouve pas assez d'information sur le net et je dois construire une simulation graphique qui explique et met en oeuvre cet algorithme :cry:
je vous attend
merci beaucoup
un descriptif se situe sur
http://www.infres.enst.fr/~premiere/...ojets05-06.pdf
Page 4 du document
mon probleme est dans la fusion des monotonies:
supposons que la memoire ne peut contenir que 10 entiers et que je dois trier 1000000 entiers, sachant que je dispose de 4 fichiers auxiliaires f1 f2 f3 f4 :
1- je commence par les 10 premiers entiers dans mon fichier sources et je les tri et cette monotonie je la place dans f1 puis la 2eme dans f2 la 3eme dans f1 , la 4eme danf f2 ....
2- je fusionne m1 et m2 dans une monotonie de 20 elements que je la place dans f3 puis m3 et m4 que je la place dans f4 etc....
3- et je refais la meme operation jusqu'atrouver une seule monotonie = fichier source trier .
c apres la repartition des monotonies dans les 2 premiers fichiers que je suis bloquer car dans la fusion j'arrive a une fausse resultat dans par exemple ce cas
si
(1ere monotonie) m1 = 1 2 3 4 5 6 7 8 9 10
(2eme monotonie) m2= 20 30 45 120 150 200 300 600 900 950
avec l'algo de fusion standard:
i <-1 ; j <-1 ;
r[m+1]<-infini ; s [n+1]<-infini ;
pour k de 1 à m+n faire
si r [ i ] <= s [ j ] alors
{ t [ k ] <- r [ i ] ; i <- i+1 ; }
sinon
{ t [ k ] <- s [ j ] ; j<-j+1 ; }
je serais pousser a prendre les 5 premier entiers de m1 et les 5 autre de m2 de les fusionner puis de les ecrire dans f3 puis les 5 autres de m1 et les 5 de m2 et de les fusionner et de les ecrire a la suite car la memoire ne contient que 10 place et je dois construire des monotonies des 20 puis 40 puis 80 .... jusqu'à 1000000
or le resultat dans notre exemple est
1 2 3 4 5 20 30 45 120 150 6 7 8 9 10 100 200 300 600 900 950
comment puis je les fusionner avec une foction generale ???
La fusion ne demande que 2 places en mémoires : 1 par liste à fusionner, à chaque étape il suffit de connaître la tête des deux listes pour faire la fusion. Après tu peux optimiser en préchargeant plus d'éléments en mémoire, mais c'est de l'optimisation prématurée à mon avis, tu devrais utiliser une fonction qui te donne la tête d'une liste contenu dans un fichier, l'écrire simplement d'abord (lire à chaque demande) puis l'optimiser plus tard si tu t'aperçoit que le résultat est trop lent.
--
Jedaï
Je me rappelle avoir déjà réalisé ce type de tri pour un projet (ordinateur avec mémoire vive limité).
Il fallait réaliser un découpage de fichier. Trier les fichiers séparement (en géneral, il vaut mieux éviter les tri qui utilisent des appels recursifs car la mémoire est limité).
Ensuite pour fusionner les fichiers, on a utilisé deux méthodes :
Fusion des fichiers deux par deux : la première étant une file de fichier que l'on trie deux par deux. (après étude, on a trouvé que la meilleur complexité se faisait avec une file)
Fusion de tous les fichiers de front : La deuxième méthode était un tri par tas pour l'ensemble des fichiers (on disposait d'une loi d'infériorité entre deux fichiers et le tri se programmait comme un tri par tas classique).