Tri par fusion

par **haiethem** Mer 15 Jan - 14:38

Voici une version récursive du tri par fusion :
0)   DEF PROC tri_f(var t:tab;d,f:entier)
1)   Si d
Tri_f(t, (d+f)div 2+1,f)
PROC fusion(t,d, (d+f)div 2,f)
  Fin si
2)   Fin
*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
0)   DEF PROC fusion (var t;d,m,f:entier)
1)   i←d,j←m+1
2)   pour k de 1 à f-d+1 faire
si (i<=m)et(j<=f)alors
si t[i] <=t[j] alors   temp[k] ←t[i]
                            i ← i+1
sinon          temp[k] ←t[j]
                           j ← j+1
         finsi
sinon si i<=m alors temp[k] ←t[i]
                            i ← i+1
sinon temp[k] ←t[j]
                           j ← j+1
fin si
fin si
fin pour
3)   pour k de 1 à f-d+1 faire
t[d+k-1] ← temp[k]
fin pour
4)   fin