Tri a bulles Ocaml

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

  • Votes
  • Date
  • Date décroissante
  1. 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

    1. 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.