Index des CoursChapitre précedentChapitre 6

Les algorithmes de tri

 

Dans ce chapitre on présente quelques algorithmes utiles, qui permettent d'ordonner les éléments d'un tableau dans un ordre croissant ou décroissant. L'ordre est par défaut croissant.

Un vecteur est dit trié si V[i] <= V[i+1], quel que soit i Є [1..n-1]

1.     Tri par sélection

1-a)        Principe

Utiliser un vecteur VT (vecteur trié) comme vecteur résultat. Celui ci contiendra les éléments du vecteur initial dans l'ordre croissant.

Le principe est de :

0-  Chercher le plus grand élément dans le vecteur initial V

1-    Sélectionner le plus petit élément dans V

2-    Le mettre dans son ordre dans le vecteur VT

3-    Le remplacer par le plus grand élément dans le vecteur initial (pour qu'il ne sera plus le minimum)

4-    Si le nombre d'éléments dans le vecteur résultat n'est pas identique à celui dans le vecteur       initial Retourner à l'étape 1                                                                                             Sinon on s'arrête.

1-b)        Exemple

Soit le vecteur V contenant 4 éléments.

                                             V                                                     VT

Au départ

10

15

-1

7

         

Phase 1

10

15

15

7

 

-1

     

Phase 2

10

15

15

15

 

-1

7

   

Phase 3

15

15

15

15

 

-1

7

10

 

Phase 4

15

15

15

15

 

-1

7

10

15

Schéma de l'algorithme                  

ALGORITHME TRI_SELECTION

CONST Bi = 1

          Bs = 10

VAR  V, VT : Tableau[Bi..Bs] de réel

         N, i, j, indmin : entier

         MIN, MAX : réel

DEBUT

{Chargement du vecteur V}

{Recherche du maximum}

MAX¬V[1]

Pour i de 2 à N

FAIRE

 Si MAX < V[i] Alors

         MAX¬V[i]

 FINSI

FINFAIRE

POUR i de 1 à N-1 FAIRE

  {Recherche du minimum}

         MIN ¬ V[1]

indmin ¬ 1

Pour j de 2 à N faire

         Si  MIN > V[j] ALORS

                  MIN¬V[j]

                       Indmin ¬ j

         Fin si

         Fin Faire

  {Mettre le minimum trouvé à sa place dans le vecteur résultat}

         VT[i] ¬ MIN

         V[indmin] ¬ MAX

Fin Faire

VT[N] ¬ MAX

FIN

Peut-on améliorer cet algorithme ?

2.     Algorithme de tri par sélection et permutation

Il s'agit ici d'éviter la construction d'un second vecteur et d'utiliser un seul vecteur initial qui sera trié.

Supposons traités n-i (1 <= i < N) éléments du vecteur.

         V[1..i] non traité                              V[i+1..N] Trié

V[1..i] non traité V[i+1..N] Trié

                         

  1                                           i                                             N

On peut considérer le vecteur V comme la concaténation de deux sous-vecteurs : le sous-vecteur V[1..i] dont les éléments n'ont pas encore été triés, et le sous vecteur V[i+1..N] dont les éléments sont triés. D'autre part tous les éléments du sous-vecteur V[1..i] sont inférieurs ou égaux à l'élément V[i+1].

On a donc :

         V[1..i] non traité, V[1..i] <= V[i+1], V[i+1..N] Trié

On a deux cas :

·        I = 1

(V[1] non traité, V[1]<= V[2], V[2..N] trié) donc V[1..N] trié

L'algorithme est terminé.

·        I > 1

Pour augmenter le sous-vecteur V[i+1..n] d'un élément, il suffit de chercher le plus grand élément contenu dans le sous-vecteur V[1..i] et de placer cet élément en position i.

Schéma de l'algorithme

ALGORITHME SLECTION_PERMUTATION

CONST Bi = 1

          Bs = 10

VAR  V : Tableau[Bi..Bs] d'entier

         N, i, j : entier

DEBUT

{Chargement du vecteur V}

Pour i de N à 2 Faire

{Recherche de l'indice du maximum dans V[1..i]}

 indmax ¬ 1

 Pour j de 2 à i

 FAIRE

  Si V[indmax] < V[j] Alors

         indmax ¬ i

  FIN SI

FIN FAIRE

{Mettre le maximum relatif trouvé à sa place}

Si indmax <> i Alors

         Aux ¬ V[indmax]

         V[indmax] ¬ V[i]

         V[i] ¬ Aux

Fin Si

Fin Faire

3. Tri par la méthode des bulles

Même principe que le précédent.

Après avoir traité n-i (1 <= i < N) éléments du vecteur.

         V[1..i] non traité                              V[i+1..N] Trié

V[1..i] non traité  V[i+1..N] Trié

                         

  1                                           i                                             N

On peut donc considérer le vecteur V comme la concaténation de deux sous-vecteurs : le sous-vecteur V[1..i] dont les éléments n'ont pas encore été triés, et le sous vecteur V[i+1..N] dont les éléments sont triés. D'autre part tous les éléments du sous-vecteur V[1..i] sont inférieurs ou égaux à l'élément V[i+1].

On a donc :

         V[1..i] non traité, V[1..i] <= V[i+1], V[i+1..N] Trié

On a deux cas :

·        I = 1

(V[1] non traité, V[1]<= V[2], V[2..N] trié) donc V[1..N] trié

L'algorithme est terminé.

·        I > 1

Pour augmenter le sous-vecteur V[i+1..n] d'un élément, il suffit de chercher le plus grand élément contenu dans le sous-vecteur V[1..i] et de placer cet élément en position i.

On parcourt le sous-vecteur V[1..i] de gauche à droite et, chaque fois qu'il y a deux éléments consécutifs qui ne sont pas dans l'ordre, on les permute. Cette opération permet d'obtenir en fin du iième parcours le plus grand élément placé en position i, et les éléments après cette position sont ordonnés.

Schéma de l'algorithme

ALGORITHME TRI_BULLE1

CONST N= 10

VAR           V : tableau[1..N] de réel

         N, i, j : entier

         AUX : réel

DEBUT

{Chargement du vecteur}

POUR i de N à 2 pas –1 FAIRE

         POUR j de 1 à i FAIRE

                   SI V[j]>V[j+1] ALORS

                     AUX ¬ V[j]

                     V[j] ¬ V[j+1]

                     V[j+1] ¬ AUX

                   FIN SI

         FIN FAIRE

FIN FAIRE

FIN

Application

Exécuter à la main cet algorithme avec les vecteurs suivants :

2

2

-1

3

0

1

1

-1

2

5

13

15

Que remarquez-vous ?

3. Schéma de l'algorithme à bulle optimisé

ALGORITHME TRI_BULLE1

CONST N= 10

VAR           V : tableau[1..N] de réel

         N, i, j : entier

         AUX : réel

DEBUT

{Chargement du vecteur}

i ¬ N

atonpermuté ¬ vrai

TANT QUE (atonpermuté) FAIRE

         j¬1

         atonpermuté ¬ faux

         TANT QUE (j < i) FAIRE

                   DEBUT

                    SI (V[J+1] < V[j]) ALORS

                            AUX¬V[J+1]

                            V[J+1] ¬V[J]

                            V[J] ¬ AUX

                      FIN SI

                            atonpermuté¬vrai

                   FIN

                   j¬j+1

         FIN

         i¬i-1

         FIN

FIN

POUR i de N à 2 pas –1 FAIRE

         POUR j de 1 à i FAIRE

                   SI V[j]>V[j+1] ALORS

                     AUX ¬ V[j]

                     V[j] ¬ V[j+1]

                     V[j+1] ¬ AUX

                   FIN SI

         FIN FAIRE

FIN FAIRE

FIN

Chapitre précedentIndex des Cours

Tags: cours, algorithme, informatique, algorithmes, tri, programmation, formation, tableaux, architecture

Révisé le :23-Sep-2010| ©2010 www.technologuepro.com