Le tri par fusion

Une autre procédure récursive pour faire le tri est le tri par fusion (ou par interclassement). La méthode provient du tri sur bande magnétique (périphérique autrefois fort utile des ordinateurs). C'est aussi un exemple de la méthode Divide and Conquer. On remarque d'abord qu'il est aisé de faire l'interclassement entre deux suites de nombres triés dans l'ordre croissant. En effet, soient á a₁, a₂, ... a_M ñ et á b₁, b₂, ... b_N ñ ces deux suites. Pour obtenir, la suite interclassée á c₁, c₂, ... c_M+N ñ des a_i et b_j, il suffit de faire le programme suivant. (On suppose que l'on met deux sentinelles a_M+1 = ¥ et b_N+1 = ¥ pour ne pas compliquer la structure du programme.)

int[] a = new int[M+1],
b = new int[N+1],
c = new int[M+N];

int i = 0, j = 0;

a[M+1] = b[N+1] = Integer.MAX_VALUE;

for (int k = 0; k < M+N; ++k)
if (a <= b[j]) {
c[k] = a[i];
++i;
} else {
c[k] = b[j];
++j;
}
Successivement, [i]c_k devient le minimum de a_i et b_j en décalant l'endroit où l'on se trouve dans la suite a ou b selon le cas choisi. L'interclassement de M et N éléments se fait donc en O(M+N) opérations. Pour faire le tri fusion, en appliquant Divide and Conquer, on trie les deux moitiés de la suite á a₁, a₂, ... a_N ñ à trier, et on interclasse les deux moitiés triées. Il y a toutefois une difficulté car on doit copier dans un tableau annexe les 2 moitiés à trier, puisqu'on ne sait pas faire l'interclassement en place. Si g et d sont les bornes à gauche et à droite des indices du tableau à trier, le tri fusion est donc

static void TriFusion(int g, int d) {

int i, j, k, m;

if (g < d) {
m = (g + d) / 2;
TriFusion (g, m);
TriFusion (m + 1, d);
for (i = m; i >= g; --i)
b = a[i];
for (j = m+1; j <= d; ++j)
b[d+m+1-j] = a[j];
i = g; j = d;
for (k = g; k <= d; ++k)
if (b[i] < b[j]) {
a[k] = b[i]; ++i;
} else {
a[k] = b[j]; --j;
}
}
}
La recopie pour faire l'interclassement se fait dans un tableau b de même taille que a. Il y a une petite astuce en recopiant une des deux moitiés dans l'ordre inverse, ce qui permet de se passer de sentinelles pour l'interclassement, puisque chaque moitié sert de sentinelle pour l'autre moitié. Le tri par fusion a une très grande vertu. Son nombre d'opérations [i]C_N est tel que C_N = 2 N + 2 C_N/2, et donc C_N = O(N log N). Donc le tri fusion est un tri qui garantit un temps N log N, au prix d'un tableau annexe de N éléments. Ce temps est réalisé quelle que soit la distribution des données, à la différence de QuickSort. Plusieurs problèmes se posent immédiatement: peut on faire mieux? Faut-il utiliser ce tri plutôt que QuickSort?

Nous répondrons plus tard ``non'' à la première question, voir section 1. Quant à la deuxième question, on peut remarquer que si ce tri garantit un bon temps, la constante petite devant N log N de QuickSort fait que ce dernier est souvent meilleur. Aussi, QuickSort utilise moins de mémoire annexe, puisque le tri fusion demande un tableau qui est aussi important que celui à trier. Enfin, on peut remarquer qu'il existe une version itérative du tri par fusion en commençant par trier des sous-suites de longueur 2, puis de longueur 4, 8, 16, ....


2.7 Programmes en Caml

(* Fibonaci, voir page X *)
let rec fib n =
if n <= 1 then 1
else fib (n - 1) + fib ( n - 2);;
(* Factorielle, voir page X *)
let rec fact n =
if n <= 1 then 1
else n * fact (n - 1);;
(* Triangle de Pascal, voir page X *)
let rec C n p =
if n = 0 || p = n then 1
else C (n - 1) (p - 1) + C (n - 1) p;;
(* Fibonaci itératif, voir page X *)
let fib n =
let u = ref 1 and v = ref 1 in
for i = 2 to n do
let u0 = !u and v0 = !v in
u := u0 + v0;
v := u0
done;
!u;;

(* Le même en style fonctionnel *)
let fib n =
let rec fib_aux k u v =
if k > n then u
else fib_aux (k + 1) (u + v) u in
fib_aux 2 1 1;;
(* La fonction d'Ackermann, voir page X *)
let rec ack m n =
if m = 0 then n + 1 else
if n = 0 then ack (m - 1) 1 else
ack (m - 1) (ack m (n - 1));;
(* La fonction 91, voir page X *)
let rec f91 n =
if n > 100 then n - 10
else f91 (f91 (n + 11));;
(* La fonction de Morris, voir page X *)
let rec g m n =
if m = 0 then 1
else g (m - 1) (g m n);;
(* Les tours de Hanoi, voir page X *)
let rec hanoi n i j =
if n > 0 then begin
hanoi (n - 1) i (6 - (i + j));
printf "%d -> %d\n" i j;
hanoi (n - 1) (6 - (i + j)) j;
end;;
#open "graphics";;
open_graph "";;

let rec dragon n x y z t =
if n = 1 then begin
moveto x y;
lineto z t
end else begin
let u = (x + z + t - y) / 2
and v = (y + t - z + x) / 2 in
dragon (n - 1) x y u v;
dragon (n - 1) z t u v
end;;
(* La courbe du dragon, voir page X *)
let rec dragon n x y z t =
if n = 1 then begin
moveto x y;
lineto z t
end else begin
let u = (x + z + t - y) / 2
and v = (y + t - z + x) / 2 in
dragon (n - 1) x y u v;
dragon_bis (n - 1) u v z t
end

and dragon_bis n x y z t =
if n = 1 then begin
moveto x y;
lineto z t
end else begin
let u = (x + z - t + y) / 2
and v = (y + t + z - x) / 2 in
dragon (n - 1) x y u v;
dragon_bis (n - 1) u v z t
end;;

clear_graph();;
dragon 15 120 120 50 50;;
(* Quicksort, voir page X *)

let rec qsort g d =
if g < d then begin
let v = a.(g)
and m = ref g in
for i = g + 1 to d do
if a.(i) < v then begin
m := !m + 1;
let x = a.(!m) in
a.(!m) <- a.(i); a.(i) <- x
end
done;
let x = a.(!m) in
a.(!m) <- a.(g); a.(g) <- x;
qsort g (!m - 1);
qsort (!m + 1) d
end;;
(* Quicksort, voir page X *)
let rec quicksort g d =
if g < d then begin
let v = a.(d)
and t = ref 0
and i = ref (g - 1)
and j = ref d in
while j > i do
incr i;
while a.(!i) < v do incr i done;
decr j;
while a.(!j) > v do decr j done;
t := a.(!i);
a.(!i) <- a.(!j);
a.(!j) <- !t
done;
a.(!j) <- a.(!i);
a.(!i) <- a.(d);
a.(d) <- !t;
quicksort g (!i - 1);
quicksort (!i + 1) d
end;;
(* Tri fusion, voir page X *)

let b = make_vect n 0;;

let rec tri_fusion g d =
if g < d then begin
let m = (g + d) / 2 in
tri_fusion g m;
tri_fusion (m + 1) d;
for i = m downto g do
b.(i) <- a.(i) done;
for i = m + 1 to d do
b.(d + m + 1 - i) <- a.(i) done;
let i = ref g and j = ref d in
for k = g to d do
if b.(!i) < b.(!j) then begin
a.(k) <- b.(!i); incr i
end else begin
a.(k) <- b.(!j); decr j
end
done
end;;