Cours d'algorithmique : les tableaux avec les algorithmes de TRI

INTRODUCTION

Dans ce chapitre, nous allons présenter deux méthodes pour  trier  les éléments d'un  tableau. 

Nous ne présenterons pas  les algorithmes  les plus efficaces. Nous avons choisi de présenter tout d'abord  la méthode de  tri dite "par sélection".  Il s'agit d'une méthode qui n'est pas  très rapide.  Ensuite, nous  présenterons  la  méthode  dite  "par  fusion"  qui  est  beaucoup plus efficace. Dans  ce chapitre, nous  utiliserons  la  fonction  PLUS_PETIT(a,b) pour  trier. Cette fonction renvoie VRAI si l'élément a est plus petit que l'élément b.  

TRI PAR SELECTION 

Cette méthode est très simple. Supposons que l'on veuille trier les n éléments du tableau t. On commence par parcourir le tableau pour trouver la plus petite valeur. On la place à l'indice 0. 

Ensuite, on recommence à parcourir le tableau à partir de l'indice 1 pour trouver la plus petite valeur que l'on stocke à l'indice 1. Et ainsi de suite pour l'indice 2, 3 jusqu'à n - 2. La figure suivante montre comment l'algorithme  fonctionne  sur un  tableau de 8 éléments. Seulement quelques étapes sont représentées.  

 

La  fonction  se déroule de  la manière  suivante. Le  tableau est parcouru du premier élément (indice 0) à l'avant dernier (indice n - 2). On note i l'indice de l'élément visité à une itération donnée. On compare l'élément i avec chaque élément j qui suit dans le tableau, c'est-à-dire de l'indice i + 1 jusqu'à l'indice n - 1. Si l'élément d'indice j est plus petit que l'élément d'indice i alors on permute i et j dans le tableau. Voici le détail de la fonction de tri.  

fonction trierSelection(ELEMENT * t, ENTIER n):
 i <-- 0;

 tant que (i < n - 1) faire
  j   <--   i + 1;

  tant que (j < n) faire
   si (PLUS_PETIT(t[j],t[i])) alors
    tmp <--  t[j];
    t[j] <--  t[i];
    t[i] <-- tmp;
   fin si;

   j  <-- j + 1;
  fin tant que;

  i  <-- i + 1;
 fin tant que;
fin fonction;

TRI PAR FUSION 

L'idée de cette méthode est la suivante. Pour trier un tableau t de n éléments, on le scinde en deux tableaux de même taille (à un élément près). On les note t1 de taille n1 et t2 de taille n -n1.  Ces  deux  tableaux  sont  ensuite  triés  (appel  récursif)  et  enfin  fusionnés  de manière  à reformer le tableau  t trié. La figure suivante reprend l'exemple du tri par sélection et montre comment le tri par fusion fonctionne au travers d'étapes numérotées de 1 à 21.  

Pour réaliser ce tri, on a besoin de plusieurs fonctions dont voici la liste.  

• scinder(ELEMENT * t, ENTIER n, ELEMENT * t1,

                      ENTIER n1, ELEMENT * t2) 
 

Copie les n1 premiers éléments du tableau t dans un tableau t1 et le reste dans un tableau t2. 

• ENTIER <-- concatener(ELEMENT * t1, ENTIER n1, ELEMENT * t2,

                                             ENTIER n2, ENTIER i2)
Copie le tableau t2 de taille n2 à la fin du tableau t1 de taille initiale n1. La copie débute à l'indice i2 dans t2. Après la copie, la nouvelle taille de t1 est retournée par la fonction. 

• fusionner(ELEMENT * t, ELEMENT * t1, ENTIER n1, 

                         ELEMENT * t2, ENTIER n2) 
Recopie les éléments des tableaux t1 et t2 dans le tableau t de façon à ce qu'ils soient triés. Les éléments de t1 et de t2 sont supposés triés. 

• trierFusion(ELEMENT * t, ENTIER n) 

          Trie les n éléments du tableau t par la méthode de tri par fusion.  

Scinder un tableau

La fonction scinder copie les n1 premiers éléments du tableau t dans t1 et le reste dans t2. 

fonction scinder(ELEMENT * t, ENTIER n, ELEMENT * t1,
                         ENTIER n1, ELEMENT * t2):

 
 i <-- 0;
 j <-- 0;

 tant que (i < n1) faire
  t1[i]<-- t[i];
  i <-- i + 1:
 fin tant que;

 tant que (i < n) faire
  t2[j] <-- t[i];
  j <-- j + 1;
  i <-- i + 1;
 fin tant que;
fin fonction;

Concaténer deux tableaux

Cette fonction copie le tableau t2 à la fin du tableau t1 de taille initiale n1. On suppose que t1 a  la capacité suffisante pour recevoir  tous  les éléments de  t2. Le  tableau  t2 est parcouru, en commençant à partir de l'indice i2. Chaque case de  t2 visitée est copiée à  l'indice n1 qui est augmenté d'une unité. A  la  fin de  l'exécution, n1 est  retourné puisqu'il exprime  la nouvelle taille de t1.   

fonction ENTIER   concatener(ELEMENT * t1, ENTIER n1,
                                               ELEMENT * t2, ENTIER n2,
                                               ENTIER i2):

i <-- 0;

 tant que (i < n2) faire
  t1[n1] <-- t2[i2 + i];
  n1 <-- n1 + 1;

  i <-- i + 1;
 fin tant que;

 rendre n1;
fin fonction;

Fusionner deux tableaux 

Cette fonction fusionne les deux tableaux t1 de taille n1 et t2 de taille n2 supposés triés dans le  tableau  t. La  fusion  se  fait de  façon  à  ce  que  t  soit  trié. Pour  cela, on parcours  t1  et  t2 parallèlement. Quand l'élément visité dans t1 est plus petit que celui visité dans t2, on copie l'élément de  t1 dans  t et on passe à  l'élément suivant de  t1, sinon on copie celui de  t2 et on avance  dans  t2.  On progresse comme cela  jusqu'à  ce  que  l'un des  deux  tableaux  ait  été complètement visité. Dans ce cas, on copie la partie non visitée de l'autre tableau directement dans t.  

fonction fusionner(ELEMENT * t, ELEMENT * t1, ENTIER n1,
                            ELEMENT * t2, ENTIER n2):

  

i1 <-- 0;
 i2 <-- 0;
 i  <-- 0;

 tant que (i1 < n1 et i2 < n2) faire
  si (PLUS_PETIT(t1[i1],t2[i2])) alors
   t[i] <-- t1[i1];
   i1 <-- i1 + 1;
  sinon
   t[i] <-- t2[i2];
   i2 <-- i2 + 1;
  fin si;

  i  <-- i + 1;
 fin tant que;

 i <-- concatener(t,i,t1,n1 - i1,i1);
 concatener(t,i,t2,n2 - i2,i2);
fin fonction;

Trier un tableau par fusion 

Cette  fonction  effectue  le  tri  du  tableau  t de  n  éléments.  Elle  alloue  d'abord  la mémoire nécessaire pour t1 et t2. Ensuite, elle copie chaque moitié de t dans t1 et t2. Ensuite, par appel récursif, elle trie les tableaux t1 et t2. Enfin, elle fusionne ces deux tableaux dans t et libère la mémoire occupée par  t1 et  t2. On utilise  la fonction ENT qui retourne  la partie entière d'un nombre. 

fonction trierFusion(ELEMENT * t, ENTIER n):
 si (n > 1) alors
  n1 <-- ENT(n / 2);
  t1  <-- ALLOUER(ELEMENT,n1);
  t2  <-- ALLOUER(ELEMENT,n - n1);

  si (t1  # nil et t2 #  nil) alors 
   scinder(t,n,t1,n1,t2);
   trierFusion(t1,n1);
   trierFusion(t2,n - n1);
   fusionner(t,t1,n1,t2,n - n1);
   LIBERER(t1);

   LIBERER(t2);
  sinon
   /* Erreur: Pas assez de mémoire. */
   si (t1 # nil) LIBERER(t1);
   si (t2 # nil) LIBERER(t2);
  fin si;
 fin si;
fin fonction; 

CONCLUSION 

Dans  ce  chapitre, nous  avons  vu deux méthodes  pour  trier  les  éléments  d'un  tableau.  La méthode par sélection est  très  simple à mettre en oeuvre et nécessite peu de mémoire. Par contre,  elle est très  lente. A l'opposé,  la méthode par fusion  est  un peu plus  compliquée  à écrire et nécessite beaucoup plus de mémoire. En contrepartie, elle est plus rapide.  

En effet, la méthode par sélection effectue un nombre d'opérations de l'ordre de n² opérations pour  un  tableau de  n  éléments.  La  méthode  par  fusion  effectue  quant  à  elle  n  log(n) opérations  pour  un  tableau de même  taille.  Pour  simplifier,  log(n) peut  être  vu  comme  le nombre de fois que l'on peut diviser le nombre n par 2 avant d'arriver à 1. Par exemple, 245 /2 = 122,  122  /  2 = 61,  61  /  2 = 30,  30  /  2 = 15,  15  /  2 = 7,  7  /  2 = 3,  3  /  2 = 1. Donc, on considérera que log(245) vaut 7.  

------------------------------------------------------------------------------------------------------
 <<< Introduction

                >>> CHAPITRE II : LISTE CHAINEES