Les algorithmes de Tri d’un tableau

Définition:

Un algorithme de tri est un algorithme qui permet d’organiser une collection d’objets selon  un ordre déterminé. Il s’agit des ordres numérique et lexicographique (dictionnaire) ou ordre alphabétique. Aussi, l’ordre peut être un ordre croissant ou décroissant :

  1. Ordre croissant : Un tableau t est dit trié en ordre croissant si pour tout indice i<j, t[i]<=t[j]
  2. Ordre décroissant : Un tableau trié en ordre décroissant  veut dire que pour tout indice i<j, t[i]>=t[j]

Exemple:

1 5 2 4 3 1 : pas trié

“Sp” “Zo” “Fan” : aucun tri

1 1 2 3 4 5 : trié en ordre croissant

“Fa” “Sp” “Zo” : tableau de chaine de caractères en ordre croissant

5 4 3 2 1 1 : tableau d’entier en ordre décroissant

“Zo” “Sp” “Fa” : tableau en ordre décroissant

1- Algorithme de tri : Tri par sélection

Principe :

– trouver le minimum du tableau

– le placer  en tête du tableau (échange (T[1],min))

– recommencer avec  le reste du tableau

Exemple 1 :

Exemple de Tri par selection
Exemple avec l'algorithme de tri par selection

Exemple 2 : 

tableau initial :

 99    8   7    1      200    -3     6

-3      8   7    1       200   99    6

-3     1    7     8      200     99   6

-3   1   6  8   200    99    7

-3   1   6  7   200  99   8

-3  1   6   7   8    99    200

-3  1  6    7    8   99      200

Algorithme :
pour  i de 1  à n  - 1 faire min  ←T[i]//initialisation pour  j de i +1  à n     //Boucle  de rechreche  du   min si T[j] <  min      alors min   ←T[j] //actualisation Fin  si FinPour si min   <>T[i]   alors // échanger  (T[i] , min) Fin  si Fin  Pour

Remarque:

Une  variante consiste à procéder de  façon symétrique, en  plaçant d’abord le plus  grand  élément à la fin, puis  le second plus grand  élément en avant-dernière position,  etc.

Exemple :

Exemple avec l'algorithme de tri par insertion

Exercice : Trier un tableau T(10) en utilisant cette  variante

2- Algorithme de tri : Tri par insertion

Principe :

– La partie gauche du tableau contient  les données déjà triées

– Pour tout nouvel élément, trouver sa position  dans la partie gauche, et l’insérer

Exemple1 :

tri d'insertion

Exemple 2 :

2| (5) 1 6 3 10 7

2 5|(1) 6 3 10 7

1 2 5|(6) 3 10 7

1 2 5 6|(3)10  7

1 2 3 5 6|(10)7

1 2 3 5 6 10|(7)

1 2 3 5 6 7 10 | fini

 

Algorithme :

 ( En utilisant une recherche séquentielle)

 

pour  i de 1  à  n faire

x <--  T[i]

j <-- i

tant  que (j >  =2   et T[j  - 1]  >  x  )

T[j]  <--   T[j  - 1]

j <--     j –  1

Fin  TantQue

T[j]  <-- x

Fin  Pour

Remarque:

Le tri par insertion est considéré comme le tri le plus efficace  sur des entrées de petite  taille. Il est  aussi très rapide lorsque les  données sont  déjà  presque triées.  Mais  ,en  général, le tri par  insertion  est  beaucoup plus lent  que d’autres  algorithmes comme le  tri  rapide et  le  tri fusion  pour  traiter de  grandes séquences, car  sa complexité asymptotique est  quadratique. Pour  ces raisons, il est  utilisé en  pratique en  combinaison avec  d’autres méthodes comme le tri rapide  (ou quicksort).

Exercice : Soit T(10)  un  tableau des réels. On  suppose que  le  tableau est  déjà  rempli.  Ecrire  un algorithme  qui  permet  d’ordonner (trier)  le  tableau dans l’ordre  décroissant  en  utilisant  l’algorithme  de  tri par insertion

3- Algorithme de tri : Tri par bulles

Principe :

1- on parcourt le tableau en commençant de la fin,

2- on compare l’élément d’indice  i avec  son  voisin immédiat  de rang  i-1 et on effectue une  permutation si l’élément du rang i et inférieur à son voisin du rang i-1.( si t[i]<t[i-1], echange t[i] et t[i-1] )

3- Après  chaque parcours complet  du tableau, l’algorithme  recommence  l’opération. Lorsqu’aucun échange  n’a lieu pendant un parcours, cela  signifie que le tableau est trié. On arrête alors l’algorithme.

A chaque fois, les petites valeurs remontent le tableau (les petites bulles vont vers la surface)

Exemple :

Tri à bulles

Algorithme :

Repeter AucunEchange<--Vrai Pour  j allant de n  à 1(-1) Si t[j]<t[j-1]  Alors échange(t,j,j-1) AucunEchange<--  faux Finsi FinPour Jusqu’à (AucunEchange=vrai) Fin

Pour conclure, voici un exemple d’un tableau non trié au départ et les étapes de tri selon les trois algorithmes de tri vu dans ce cours (tri par insertion , tri par selection et le tri à bulles) :

trois algorithmes de Tri

Vous pouvez suivre notre liste des vidéos sur l’algorithmique sur notre chaine youtube 9raytifclick (Darija: arabe marocaine) : Cours sur les algorithmes.

Aussi, si vous voulez commencer l’apprentissage d’un langage de programmation, voilà notre cours : Langage Python Niveau 1 qui sera très utile pour vous (il vous aide à pratiquer tous les éléments vu dans notre cours d’algorithmique).

Un Commentaire

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *