Tri a bulles Ocaml
arscy Messages postés 173 Date d'inscription Statut Membre Dernière intervention -
Bonjour, je suis actuellement en train d'essayer de coder le tri a bulles en Ocaml (langage dans lequel je débute). Je pense que ma fonction fait bien ce que je lui demande à savoir : on a un tableau d'entiers et on doit le trier dans l'ordre croissant par comparaisons successives.
voici mon code
(*un petit échauffement pour manipuler les tableaux *)
let tab = [|1;2;3|]in
let tmp = tab.(1) in
tab.(1)<-4;
tab.(2)<-tmp;
Printf.printf"tab[1]=%d\ntab[2]=%d" tab.(1) tab.(2);;
let tri_a_bulles tab =
let comp_ok= ref 0;(* on initialise un compteur de comparaisons bonnes *)
let taille=Array.length tab; (* on stocke la taille du tableau*)
let i = ref 0 ;(*permet d'accéder à n'importe quelle case du tableau*)
while(!comp_ok<taille-1) (*si tout le tableau est bien rangé on a taille-1 comparaisons ok *)
do
if !i+1 < taille then (* on vérifie que l'on tape bien dans le tableau*)
begin
if tab.(!i+1)<tab.(!i) then(*il faut changer les cases *)
begin
let tmp = tab.(!i+1) in(* on procède à l'échange de valeurs*)
tab.(!i+1)<-tab.(!i);
tab.(!i)<-tmp;
end
else
begin
comp_ok := !comp_ok+1;(* les cases sont dans le bon ordre *)
end
i:=!i+1;(* on passe à la case suivante *)
end
else (*on rentre dans cette partie si on est sur la dernière case du tableau*)
begin
i:=0;(*donc on repart au début du tableau *)
comp_ok:=0;
end
done
tab;;(*on retourne tab *)
(* des exemples *)
let tab = [|5;4;3;2;1|] in
tri_a_bulles tab;;
let tab = [|(-5);(-4);(-10);1|] in
tri_a_bulles tab;;
let tab = [|(-5);5;(-10);10 |]in
tri_a_bulles tab;;
or l'interpréteur soulève une erreur de syntaxe dans la dernière ligne de ma fonction tri_a_bulles
Merci de votre aide
1 réponse
Je ne connais rien à ton langage et je ne peux pas colorer mon code.
Voici comment je coderais le tri à bulles:
let rev = 1 (1 s'il y a eu inversion, 0 sinon)
while taille > 1 and rev > 0
begin
let rev = 0
let i = 0
while i < taille
begin
if tab[i] > tab[i+1]
begin
let tmp = tab[i]
tab[i] = tab[i+1]
tab[i+1] = tmp
rev = 1 (il y a inversion)
end
i = i + 1 (prochaine case)
end
taille = taille - 1 (chaque boucle intérieure place le plus grand en dernier)
end
Bonjour,
Un peu de documentation ici, si ça peut aider?
Pour ma part, OCaml implique de la récursivité car c'est un fer de lance de la programmation fonctionnelle.