Tri a bulles Ocaml

Fermé
Clement_7057 Messages postés 4 Date d'inscription jeudi 21 novembre 2019 Statut Membre Dernière intervention 26 octobre 2022 - 26 oct. 2022 à 09:53
arscy Messages postés 173 Date d'inscription dimanche 26 janvier 2014 Statut Membre Dernière intervention 5 octobre 2023 - 29 oct. 2022 à 10:34

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

PierrotLeFou
29 oct. 2022 à 02:50

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

0
arscy Messages postés 173 Date d'inscription dimanche 26 janvier 2014 Statut Membre Dernière intervention 5 octobre 2023 9
Modifié le 29 oct. 2022 à 10:36

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.

0