Cours-Informatique.tn| Révision

Révision Informatique

Les méthodes de tri :

Les méthodes de tri d'un tableau (par sélection, à bulles et par insertion).

Introduction :

Un algorithme de tri est une suite finie d'instructions servant à réordonner une séquence d'éléments suivant un critère fixé à priori (relation d'ordre total ).

par exemple si on a un tableau T de taille n=6

	1	2	3	4	5	6
T	20	3	50	12	35	7

Trier le tableau en ordre croissant (de plus petit au plus grand) relativement à un ordre total noté ≤ donne le résultat suivant:

	1	2	3	4	5	6
T	3	7	12	20	35	50

Trier le tableau en ordre décroissant (de plus grand au plus petit) relativement à un ordre total noté ≥ donne le résultat suivant:

	1	2	3	4	5	6
T	50	35	20	12	7	3

Questions:

You Scored % - /

1. Trier un tableau consiste à :

le mettre en ordre
le mettre en désordre

2. La relation d'ordre total ≥ permet de trier le tableau en ordre :

Croissant
Décroissant

2. Quelles sont les types de tableaux qu'on peut trier ?

Tableau d'entier
Tableau de réels
Tableau de caractères
Tableau de chaines de caractères

On peut trier autres types que les entiers. Il suffit de disposer d'un domaine de valeurs muni d'une relation d'ordre total. On peut donc trier des caractères, des mots en ordre alphabétique.

1-Le tri par sélection:

Algorithme:

0)DEF Proc Tri_selection (VAR T :TAB ; n :entier)
1)Pour i de 1 à n-1 faire
          [pos_min←i] Pour j de i+1 à n faire
                              Si ( T[j] < T[pos_min])Alors
                                                    pos_min ← j
                              Finsi
                             FinPour
      Si ( pos_min <> i) Alors 
                                          aux ←T[i]
                                          t[i]←T[Pos_min]
                                          t[pos_min]←aux
       Finsi
   FinPour
2)Fin Tri_selection

T.D.O locaux(Tableau de déclaration des objets locaux)

Objet	Type/Nature	Rôle
i, j, pos_min , aux	Entier

Traduction en Pascal:

Procedure tri_selection (var T:TAB ; n:integer);
Var i,j,pos_min, aux: integer;
Begin
For i:=1 to n-1 do
	begin
		pos_min:=i;
		for j:=i+1 to n do
	   if t[j]  < t[pos_min] then pos_min:=j;
	if i <> pos_min then 
						begin
						aux:=t[i];
						t[i]:=t[pos_min];
						t[pos_min]:=aux;
						end;
	end;
End;

2-Le tri à bulles :

Algorithme:


0) DEF Proc permute(var x,y:entier)
1)aux←x
2) x ← y
3) y ←aux
4)Fin permute

T.D.O locaux(Tableau de déclaration des objets locaux)

Objet	Type/Nature	Rôle
aux	Entier


0) DEF Proc Tri_Bulles (VAR T :TAB , n :entier)
1) Répéter
       Echange ←faux
          Pour i de 1 à n-1 faire
               Si ( T[i] > T[i+1])Alors Permute(T[i], T[i+1])
                                                Echange ← vrai
               FinSi
           FinPour
        n ← n-1
    Jusqu'à (Echange = Faux) ou (n=1)
2) Fin Tri_Bulles

T.D.O locaux(Tableau de déclaration des objets locaux)

Objet	Type/Nature	Rôle
i echange permute	Entier booléen procédure

Traduction en Pascal:

procedure permute(var x,y:integer);
var aux:integer;
Begin
aux:=x;
x:=y;
y:=aux;
end;


procedure  Tri_Bulles (VAR T :TAB ; n :integer);
var  i:integer; echange:boolean;
Begin
Repeat
echange:=False;
for i:=1 to n-1 Do
	if T[i] > T[i+1]) Then
				begin
				Permute(T[i], T[i+1]);
				Echange := true ;
				end;
n:=n-1;
until  (Echange = false) or (n=1);
end;

3-Le tri par insertion:

Algorithme:

0) DEF Proc Tri_insertion (VAR T :TAB , n :entier)
1) Pour i de 2 à n faire
       TMP ←T[i]
       j ← i
          Tant que (j > 1) et (T[j-1] > TMP)   faire
               T[j] ← T[j-1]
               j  ← j-1
           FinTantque   
        T[j] ← TMP
    FinPour
2) Fin Tri_insertion

T.D.O locaux(Tableau de déclaration des objets locaux)

Objet	Type/Nature	Rôle
i,j TMP	Entier Entier	compteurs variable temporaire

Traduction en Pascal:

procedure  Tri_insertion (VAR T :TAB ; n :integer);
var  i,j:integer; tmp:integer;
Begin

for i:=2 to n Do
  Begin
    Tmp:=t[i];
    j:=i;
	     while (j > 1) and (T[j-1] > Tmp)   do
				begin
				T[j]:=t[j-1];
				j:=j-1;
				end;
    T[j]:=tmp;
  End;
end;