cours de Algorithme et plus nouveau pour la programmation en java Vb.net version 3

cours de Algorithme et plus nouveau pour la programmation en java Vb.net version 3

La methode generale de fusion consiste a comparer les t^etes de L1 et L2, a0
et b0, et a placer en t^ete de L le plus petit de ces elements. Si c'est a0 alors il
reste a fusionner la queue de L1 avec L2, si c'est b0 alors il reste a fusionner L1
avec la queue de L2.
Fusion de vecteurs
(* fusionne les deux vecteurs tries v1 et v2 dans v *)
(* "compare" est la fonction de comparaison. *)
let fusion_vec compare v1 v2 v =
let i = ref 0 (* indice de v1 *)
and j = ref 0 (* indice de v2 *)
and k = ref 0 (* indice de v *)
in
while (!i < vect_length(v1)) & (!j < vect_length(v2)) do
match compare v1.(!i) v2.(!j) with
| PLUSGRAND -> v.(!k) <- v2.(!j); k := !k+1; j := !j+1
| _ -> v.(!k) <- v1.(!i); k := !k+1; i := !i+1
done;
(* ici, un des deux vecteurs est epuise *)
(* on recopie la fin de l'autre *)
while !i < vect_length(v1) do
v.(!k) <- v1.(!i); k := !k+1; i := !i+1
done;
while !j < vect_length(v2) do
v.(!k) <- v2.(!j); k := !k+1; j := !j+1
done
;;
Preuve du programme
On demontre par une recurrence immediate la propriete :
a l'entree de la premiere boucle while, les elements v1:(0 :: !i

koooool