Advertisement
csmine

Option info - Tris sur liste/tableau [entier]

Mar 15th, 2019
541
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
OCaml 4.43 KB | None | 0 0
  1. (* Tri par pivot sur des listes *)
  2.  
  3. (* Première version *)
  4. let partition k l =
  5. let rec aux_partition l l1 l2 = match l with
  6. |[] -> (l1,l2)
  7. |h::t when h<k -> aux_partition t (h::l1) l2
  8. |h::t -> aux_partition t l1 (h::l2)
  9. in aux_partition l [] [];;
  10.  
  11. (* Deuxième version *)
  12. let rec partition a l = match l with
  13. |[] -> ([],[])
  14. |h::t when h>a -> let (l1,l2) = (partition a t) in (l1,h::l2)
  15. |h::t -> let (l1,l2) = (partition a t) in (h::l1,l2);;
  16.  
  17.  
  18. let rec tri_pivot l = match l with
  19. |[] -> []
  20. |h::t -> let (l1,l2) = partition h t in (tri_pivot l1)@[h]@(tri_pivot l2);;
  21.  
  22.  
  23. (*Tri par pivot sur des tableaux*)
  24.  
  25. (* Fonction partition avec le 1er élément comme "pivot"*)
  26. (* Description de l'algorithme :
  27. On regarde [|5;2;6;9|]
  28. On compare à chaque fois 5 et l'élément après.
  29. Si l'élément est plus petit, alors on permute les deux, et on update "début" pour qu'il reste à la position de 5
  30. Si l'élément est plus grand, on échange ce "plus grand élément" avec le dernier, et on fini plus tôt.*)
  31. let partition t a b =
  32.     let debut = ref a in
  33.     let fin = ref b in
  34.     while !debut <> !fin do
  35.         let (ta,tb) = (t.(!debut),t.(!debut +1)) in
  36.         if ta > tb then
  37.        
  38.         begin
  39.         t.(!debut) <- tb;
  40.         t.(!debut +1) <- ta;
  41.         incr debut;
  42.         end
  43.        
  44.         else
  45.        
  46.         begin
  47.         t.(!debut + 1) <- t.(!fin);
  48.         t.(!fin) <- tb;
  49.         decr fin;
  50.         end
  51.        
  52.         done;
  53.         !debut;;
  54. (* nb : "!debut" renvoyé est la position du pivot dans le tableau *)
  55.  
  56.  
  57. (* Pour le tri par pivot, on va trier récursivement entre "debut et pivot" ; "pivot et fin" *)
  58. let tri_par_pivot t =
  59. let n = Array.length t - 1 in
  60.     let rec aux a b =
  61.         if a<b then
  62.             begin
  63.             let p = partition t a b in
  64.             aux a (p-1);
  65.             aux (p+1) b;
  66.             end in
  67.     aux 0 n;
  68.     t;;
  69.  
  70.  
  71. (* Tri par fusion sur des listes *)
  72. let rec division l = match l with
  73. |[] -> [],[]
  74. |[h] -> [h],[]
  75. |h1::h2::t -> let (l1,l2) = division t in h1::l1,h2::l2;;
  76.  
  77. let rec fusion l1 l2 = match l1,l2 with
  78. |[],_ -> l2
  79. |_,[] -> l1
  80. |h1::t1,h2::t2 when h1 < h2 -> h1::(fusion t1 l2)
  81. |h1::t1,h2::t2 -> h2::(fusion l1 t2);;
  82.  
  83. let rec tri_fusion l = match l with
  84. |[] -> []
  85. |[a] -> [a]
  86. |h::t -> let (l1,l2) = division l in
  87.             fusion (tri_fusion l1) (tri_fusion l2);;
  88.  
  89.  
  90. (* Tri par insertion sur des listes *)
  91. let rec insere a l = match l with
  92. |[] -> [a]
  93. |h::t when h<a -> h::(insere a t)
  94. |h::t -> a::t;;
  95.  
  96. let tri_insertion l =
  97. let rec aux l1 l2 = match l1 with
  98. |[] -> l2
  99. |h::t -> aux t (insere h l2)
  100. in aux l [];;
  101.  
  102.  
  103. (* Tri par insertion sur des tableaux *)
  104. let array_insertion t =
  105. let j = ref 0 in
  106. let permute a b =
  107.     let ta = t.(a) and tb = t.(b) in
  108.     t.(b) <- ta;
  109.     t.(a) <- tb in
  110.    
  111. (* On essaie d'insérer t.(i) à sa place, dans le tableau "t.(0),...,t.(i)"
  112. Pour cela, on décale les éléments qui sont plus grand que i vers la droite *)
  113. for i=1 to ((Array.length t)-1) do
  114.     j:= 0 ;
  115.     while (!j < i)&& t.(i - !j)  < t.(i - !j -1) do
  116.         permute (i - !j) (i-1 - !j);
  117.         incr j;
  118. done;
  119. t;;
  120.  
  121.  
  122.  
  123.  
  124. (* Deuxième tri par insertion sur des tableaux *)
  125. let array_selection t=
  126. let n = Array.length t in
  127. for i = 1 to n-1 do
  128. let a = t.(i) in
  129. let j = ref (i-1) in
  130.     while (!j >= 0) && t.(!j) > a do
  131.     t.(!j + 1) <- t.(!j);
  132.     decr j;
  133.     done;
  134.     t.(!j + 1) <- a
  135.     done;
  136.     t;;
  137.    
  138.  
  139.  
  140. (* Tri par selection sur des listes *)
  141. let sortir_le_max l =
  142. let rec aux_sortir_max a l = match l with
  143. |[] -> (a,[])
  144. |h::t when a>h -> let (max,l_sans_max) = aux_sortir_max a t in (max,h::l_sans_max)
  145. |h::t -> let (max,l_sans_max) = aux_sortir_max h t in (max,a::l_sans_max)
  146. in aux_sortir_max (List.hd l) (List.tl l);;
  147.  
  148.  
  149. let tri_par_selection l =
  150. let rec aux_tri l1 l2 = match l1 with
  151. |[] -> l2
  152. |h::t -> let (max,l_sans_max) = sortir_le_max l1 in aux_tri l_sans_max (max::l2)
  153. in aux_tri l [];;
  154.  
  155.  
  156. (* Tri par selection sur les tableaux *)
  157. let array_selection t =
  158.  
  159. (* Fonction qui détecte le max *)
  160. let n = Array.length t in
  161. for i=0 to (n-1) do
  162. let m = ref 0 in
  163. for j=0 to (n-i-1) do
  164. if t.(j) > t.(!m) then m:=j ;
  165. done ;
  166.  
  167. (* Fonction qui permute le "dernier" élément et le max *)
  168. let (u,v) = ( t.(n-i-1), t.(!m) ) in
  169. t.(n-i-1) <- v;
  170. t.(!m) <- u;
  171. done;
  172. t;;
  173.  
  174.  
  175.  
  176. (* Tri à bulles sur tableau *)
  177. (* Echange les éléments consécutifs qui ne sont pas dans le bon ordre *)
  178. (* Recommence les procédés sur les (n-1) premiers éléments *)
  179. let bubble_sort t =
  180. let n = Array.length t in
  181. for j=n-1 downto 0 do
  182.  
  183. for i=0 to j-1 do
  184. if t.(i)>t.(i+1) then
  185. let (u1,u2) = (t.(i),t.(i+1)) in
  186. t.(i) <- u2;
  187. t.(i+1) <- u1;
  188. done;
  189.  
  190. done;
  191. t;;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement