tri fusion en C

Marsh Posté le 11-11-2003 à 14:34:50

je voudrais le code d'un tri fusion il parait que c'est la méthode la plus utilisée pour trier un tableau....
g fait le tri par séléection c'était pas dur mais le tri fusion serait le plus rapide
on découpe un tableau en deux on tri les deux morceaux et on les fusionne
pour les grands tableaux on doit decouper et fusionner des morceaux de 2 ou 3 elements

---------------
Ben mon PC wine bien mais... on en veux tjs plus!!!

Reply

Marsh Posté le 11-11-2003 à 14:34:50

Reply

Marsh Posté le 11-11-2003 à 14:35:44

CHRYSAOR a écrit :

je voudrais le code d'un tri fusion il parait que c'est la méthode la plus utilisée pour trier un tableau....

et avec ca ?

Reply

Marsh Posté le 11-11-2003 à 14:38:59

Code :

(* LE TRI PAR FUSION *)
(* ci dessous la fusion de deux files *)
let rec fusion (a,b) = match (a,b) with
| ([],_) -> b
| (_,[]) -> a
| (t1::r1,t2::r2)-> if t1<t2
then t1::fusion (r1,b)
else t2::fusion (a,r2)
;;
(* transforme une liste en liste de listes *)
let listemoica t = [t];;
let listeliste l=map listemoica l ;;
(* trifusion avec les listes de listes *)
(* l'ensemble des deux fonction trifusionll & boulot fonctionne, mais il
doit y avoir moyen de faire une seule fonction, et d'avoir une liste de
motifs plus facile à comprendre *)
let rec trifusionll = function
|a::b::c -> fusion (a,b) :: trifusionll c
|a::_ -> [a]
|_ -> []
;;
let rec boulot = function
|[]->[[]]
|t::r as ll-> if r=[]
then [t]
else boulot (trifusionll ll)
;;
(* la commande finale *)
let trifusion m = hd (boulot (listeliste m));;
(* des listes toutes prêtes pour faire des tests *)
let pairs= [0;2;4;6;8;10;12;14];;
let impairs=[1;3;5;7;9;11;13;15];;
let petitpair=[0;2;4];;

---------------
brisez les rêves des gens, il en restera toujours quelque chose... -- laissez moi troller sur discu !

Reply

Marsh Posté le 11-11-2003 à 14:40:57

chrisbk a écrit :

et avec ca ?

100 balles et un mars [:spamafote]

eh oh, une recherche dans google et on trouve des bibles entières sur les algorithmes de tri, faut pas pousser

---------------
Whichever format the fan may want to listen is fine with us – vinyl, wax cylinders, shellac, 8-track, iPod, cloud storage, cranial implants – just as long as it’s loud and rockin' (Billy Gibbons, ZZ Top)

Reply

Marsh Posté le 11-11-2003 à 14:41:04

c'est quel include pour que le compilo plante pas sur "let" ? [:icon9]

Reply

Marsh Posté le 11-11-2003 à 14:51:37

il est bizarre con code kad, mais je sais pas pourquoi.

Code :

let rec trifusionll = function
|a::b::c -> fusion (a,b) :: trifusionll c

ça c'est pas terminal.

Code :

let rec fusion (a,b) = match (a,b) with
| ([],_) -> b
| (_,[]) -> a
| (t1::r1,t2::r2)-> if t1<t2
then t1::fusion (r1,b)
else t2::fusion (a,r2)

se réécrit en

Code :

let rec fusion = function
| ([],x) -> x
| (x,[]) -> x
| ((t1::r1) as a,(t2::r2) as b)-> if t1<t2
then t1::fusion (r1,b)
else t2::fusion (a,r2)

bien entendu, c'est pas terminal non plus.

Code :

let listemoica t = [t];;
let listeliste l=map listemoica l ;;

se réécrit en

Code :

let listeliste l = map (fun x -> [x]) l ;;

(et c'est terminal)

on peut tout faire en une seule fonction, comme tu le dis (en gardant ton code, corrigé un peu) :

Code :

let trifusion m =
let listeliste l = List.map (fun x -> [x]) l in
let rec boulot =
let rec trifusionll =
let rec fusion = function
| ([],x) -> x
| (x,[]) -> x
| (((t1::r1) as a),((t2::r2) as b))-> if t1<t2
then t1::fusion (r1,b)
else t2::fusion (a,r2) in
function
|a::b::c -> fusion (a,b) :: trifusionll c
|a::_ -> [a]
|_ -> [] in
function
|[]->[[]]
|t::r as ll-> if r=[]
then [t]
else boulot (trifusionll ll)
in
List.hd (boulot (listeliste m));;

Message édité par nraynaud le 11-11-2003 à 15:04:15

---------------
trainoo.com, c'est fini

Reply

Marsh Posté le 11-11-2003 à 14:55:24

[:rofl]
les salauds

---------------
J'ai un string dans l'array (Paris Hilton)

Reply

Marsh Posté le 11-11-2003 à 18:27:39

Hoooo du Caml!!!
J'en connais un qui va s'amuser....

CHRYSAOR mettons les choses au point... On aura plaisir a te filer des conseils, des astuces, t'aider a résoudre des problemes, répondre a tes questions, mais faire le boulot a ta place... faudrait voir a pas nous confondre avec une équipe de programmeurs bénévoles! Pour qui nous prends-tu?

Reply

Marsh Posté le 11-11-2003 à 20:33:12

désolé je pensais pas ofusquer(lol) tant de monde moi!!!
non en fait c que je vois bien l'algo je m'en sors tjs bien avec les algos mais je peine avec le code et la syntaxe...
manque de temps et de pratique cjuste de la "petite" programmation que je fais c pas super fort.
est ce qu'il y en a qui connaisse les cartes matlog?? je dois travailler avec une BL2000 et le "dynamic c" a priori ca ressemble a du c meme enormement mais avec de petits changements.
je voudrais deux ou trois conseils et savoir si quelqu'un sait ou je peux trouve le logiciel pour bosser chez moi je le trouve pas...
voir meme pour un qui ait l'adsl m'envoyer l'iso du cd que je me debrouille
lol je crois que je suis en train de demander 1000000? et une montagne de mars
excusez moii!!!

Message édité par Chrysaor le 11-11-2003 à 20:33:32

---------------
Ben mon PC wine bien mais... on en veux tjs plus!!!

Reply

Marsh Posté le 12-11-2003 à 15:48:45

Content que tu l'aies bien pris
Demande tous les conseils que tu veux; C'est juste que la paresse est tres, tres mal vue sur ce forum... alors tu penses bien que demander qu'on te fasse ton boulot allait déclencher de telles réactions...
Concernant les cartes matlog, désolé, je ne connais pas du tout mais d'apres ce que j'ai vu sur http://www.e-matlog.com/ProdServ/ZW/DC/Docs/M0058f.pdf ca a l'air d'etre effectivement tres proche du C, et dans ce cas je te renvoie a la section bibliolinks concernant ce langage.
Quant au logiciel dont tu parles, cherche "dynamic c" dans google, tout simplement...

Reply

Marsh Posté le 12-11-2003 à 15:48:45

Reply

Marsh Posté le 20-11-2003 à 21:04:59

CHRYSAOR a écrit :

on découpe un tableau en deux on tri les deux morceaux et on les fusionne

Je voie pas de quelle tri tu parles, j'en connais deux qui utilisent cette methode, et apparement le plus utilisé est non pas le tri par fusion mais le tri rapide.

Message édité par xWillow le 20-11-2003 à 21:05:34

Reply

Marsh Posté le 20-11-2003 à 22:03:30

xWillow a écrit :

Je voie pas de quelle tri tu parles, j'en connais deux qui utilisent cette methode, et apparement le plus utilisé est non pas le tri par fusion mais le tri rapide.

La difference entre le tri fusion et le tri rapide c'est que :
- dans le tri rapide, on sépare les elements en 2 parties séparées par un pivot : tous les elements plus petits que le pivot à gauche et les autres à droite. On tri chaque sous partie et on met le resultat bout à bout.
- dans le tri fusion, on sépare au milieu sans se poser de questions, on tri les 2 sous parties et on les rassemble intelligement en fusionnant les deux parties en profitant du fait qu'elles sont déjà triées justement.

Reply

Marsh Posté le 20-11-2003 à 22:10:03

Kristoph a écrit :

- dans le tri fusion, on sépare au milieu sans se poser de questions, on tri les 2 sous parties et on les rassemble intelligement en fusionnant les deux parties en profitant du fait qu'elles sont déjà triées justement.

Tu oublies de dire le principal! On trie récursivement les 2 sous parties... C'est a dire en utilisant un tri fusion justement! Sinon ca ne sert a rien...

Tri fusion :
ma liste n'a qu'un élément?
oui -> renvoyer la liste
non -> la couper en deux. Faire un tri fusion sur les deux morceaux, fusionner les deux résultats.

Reply

Marsh Posté le 20-11-2003 à 22:28:00

Ace17 a écrit :

Tu oublies de dire le principal! On trie récursivement les 2 sous parties... C'est a dire en utilisant un tri fusion justement! Sinon ca ne sert a rien...

Tri fusion :
ma liste n'a qu'un élément?
oui -> renvoyer la liste
non -> la couper en deux. Faire un tri fusion sur les deux morceaux, fusionner les deux résultats.

Ah non, quand je disais qu'on trie les sous partie, j'entends par la qu'on doit faire un "tri rapide". De même lors du "tri rapide", il faut trier les sous parties avec un "tri fusion". Sauf si le pgcd du nombre d'elements des 2 parties est 54 bien sur. À ce moment il faut faire un "tri a bulle"

Reply

Marsh Posté le 21-11-2003 à 06:49:05

Kristoph a écrit :

Ah non, quand je disais qu'on trie les sous partie, j'entends par la qu'on doit faire un "tri rapide". De même lors du "tri rapide", il faut trier les sous parties avec un "tri fusion". Sauf si le pgcd du nombre d'elements des 2 parties est 54 bien sur. À ce moment il faut faire un "tri a bulle"

:lol:
Non mais je voulais juste insister la dessus; Parce que faut faire gaffe tu sais j'en ai connu qui, pour faire un tri fusion, coupaient leur listent en deux, triaient chaque sous partie par un tri par selection, et ensuite concatenaient les deux listes!!! :sarcastic:

Reply

Marsh Posté le 23-11-2003 à 16:13:07

moi j'ai fait ça pour le tri fusion

let coupe l =
let rec aux l l2= match l with
|[]->l2,[]
|[x]->l2@[x],[]
|(h::h2::t)-> if h2<h then (l2@[h],h2::t)
else aux (h2::t) (l2@[h])
in aux l [];;

let rec decoupage l=match l with
|[]->[[]]
|[x]->[[x]]
|l-> let (x,y)= coupe l in x::decoupage y;;

let rec fusion (l1,l2) = match (l1,l2) with
|l1,[]->l1
|[],l2->l2
|(h1::t1),(h2::t2)->if h1<=h2 then h1::fusion (t1,(h2::t2))
else h2::fusion (t2,(h1::t1));;

let tri_fusion l = let d=decoupage l
in let rec aux ll=match ll with
|[[]]->[]
|[[x]]->[x]
|[a;b]->fusion (a,b)
|(h::h2::t)->aux((fusion (h,h2))::t)
in aux d;;

et pour avoir des listes à tester :

let l1=[5;3;2;7;6;9];;
let l2=[9;8;2;3;4;7;1;3;2];;
let l3=[8;10;17;2;1;12;7;6;9];;

let rec genere x len = match len with
|0->[]
|len->(random__int x)::genere x (len-1);;

Message édité par blazkowicz le 23-11-2003 à 16:24:59

Reply

tri fusion en C

Sujets relatifs:

Leave a Replay