Sciences de l'informatique

Bienvenue dans notre forum de partage et d'échange d'information technique dans le domaine NTIC (Informatique, Programmation, Réseau, Multimédia), ce forum est destinée à tous les élèves Tunisiens
 
AccueilCalendrierFAQMembresGroupesS'enregistrerConnexion
Rechercher
 
 

Résultats par :
 
Rechercher Recherche avancée
Derniers sujets
Navigation
 Portail
 Index
 Membres
 Profil
 FAQ
 Rechercher
Mars 2017
LunMarMerJeuVenSamDim
  12345
6789101112
13141516171819
20212223242526
2728293031  
CalendrierCalendrier
Qui est en ligne ?
Il y a en tout 1 utilisateur en ligne :: 0 Enregistré, 0 Invisible et 1 Invité

Aucun

Le record du nombre d'utilisateurs en ligne est de 6 le Ven 13 Jan - 2:22

Partagez | 
 

 Le tri fusion

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
Dhifallah Fethi
Admin
avatar

Messages : 74
Date d'inscription : 02/03/2011

MessageSujet: Le tri fusion   Jeu 3 Mar - 12:37

Le tri fusion


Le principe:

Le principe de cet algorithme est très simple. Il consiste à fusionner deux sous-séquences triées en une séquence triée.

Il exploite directement le principe du divide-and-conquer qui repose, grosso-modo, en la division d'un problème en ses sous problèmes et en des recombinaisons bien choisies des sous-solutions optimales.

Le principe de cet algorithme tend à adopter une formulation récursive :
  • On découpe les données à trier en deux parties plus ou moins égales
    On trie les 2 sous-parties ainsi déterminées
    On fusionne les deux sous-parties pour retrouver les données de départ

Donc chaque instance de la récursion va faire appel à nouveau au programme, mais avec une séquence de taille inférieure à trier.

La terminaison de la récursion est garantie, car les découpages seront tels qu'on aboutira à des sous-parties d'un seul élément; le tri devient alors trivial.
Une fois les éléments triés indépendamment les uns des autres, on va fusionner (merge) les sous-séquences ensemble jusqu'à obtenir la séquence de départ, triée.

La fusion consiste en des comparaisons successives.
Des 2 sous-séquences à fusionner, un seul élément peut-être origine de la nouvelle séquence. La détermination de cet élément s'effectue suivant l'ordre du tri à adopter.

Une fois que l'ordre est choisi, on peut trouver le chiffre à ajouter à la nouvelle séquence; il est alors retiré de la sous-séquence à laquelle il appartenait.
Cette opération est répétée jusqu'à ce que les 2 sous-séquences soient vides.
Supposons qu'on ait à trier la séquence suivante : [11,4,27,17,32,5,12] par ordre croissant.

Opération de découpage

Cette partie est très simple, elle va consister à découper notre séquence en des sous-séquences de taille presque égales (si le nombre d'éléments de la séquence est impair, on ne saurait pas avoir des tailles rigoureusement égales).

Une fois les découpages effectués, après un certain nombre d'instances, on va avoir des sous-séquences d'un seul élément, comme ceci:

[11] [4] [27] [17] [32] [5] [12]


Bien évidemment, de telles sous-séquences sont triées, vu qu'il n'y a qu'un seul élément.
Le but va maintenant être de fusionner correctement ces listes, chacune triée, entre elles.

Opération de fusion

On va fusionner les listes 2 à 2, ce qui va nous donner 4 sous-listes:

[4,11] [17,27] [5,32] [12]

On continue le processus jusqu'à ce que la liste de départ soit triée. On obtient ainsi:

[4,5,11,12,17,27,32]

qui constitue bien un tri de la séquence de départ.

Voici maintenant une illustration des étapes de l'algorithme avec d'autres données:

[Vous devez être inscrit et connecté pour voir cette image]

L'algorithme peut être décrit récursivement :
  • On découpe en deux parties à peu près égales les données à trier
    On trie les données de chaque partie
    On fusionne les deux parties


La récursivité s'arrête car on finit par arriver à des listes composées d'un seul élément et le tri est alors trivial.

L'animation de tri fusion

[Vous devez être inscrit et connecté pour voir ce lien]
Téléchargement de l'animation

Taille:18.23 KB
[Vous devez être inscrit et connecté pour voir ce lien]

Code en Pascal:(mode récursive):

Code:
  { ***********PROCEDURE FUSIONNER****************}
procedure fusionner ( var t: vect ; d,m,f : integer);
Var  aux, i, j, k : integer;
begin
  J:=M;I:=M-1;
  WHILE  (J<=F) DO
    BEGIN
      while (T[J] <t[I]) and (i>=1) do
        BEGIN
            I:=I-1;
        END;
      Aux:=T[J];
      For  k:= J DOWNTO I+1 DO
          T[k]:=t[K-1];
      T[I+1]:=Aux;

      J:=J+1;
      I:=J-1;
    END;
End;
    { ***********PROCEDURE TRI_FUSION****************}
Procedure Tri_Fusion (Var t : veQct; d, f : integer);
Var  m:integer;
Begin
 If f > d Then
  Begin
      m := (d + f) Div 2;
      afficher(t,d,f);
      Tri_Fusion (t, d, m);
      Tri_Fusion (t, m + 1, f);
      fusionner (t,d,m,f);
      afficher(t,d,f);
  end;
End;
Revenir en haut Aller en bas
http://ntic.moontada.net
 
Le tri fusion
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Sciences de l'informatique :: 4ème SI :: Programmation :: Cours-
Sauter vers: