Ecole Supérieure de Technologie
de Safi
1ère année GIM - INFORMATIQUE
TRI DE TABLEAUX
A.SOULMANI
Introduction
❑ Un tableau permet de stocker plusieurs éléments de même
type.
❑ Lorsque le type des éléments du tableau possède un ordre
total, on peut les ranger en ordre croissant ou décroissant.
❑ Trier un tableau consiste à ranger ses éléments en ordre
croissant ou décroissant.
❑ Il existe plusieurs algorithmes de tri.
❑ Utilité du tri: Dans les bases de données et les tableurs.
2
Quelques Algorithmes de Tri
❑Tri par sélection ou par minimum successif
❑Tri à bulles (Bubble sort)
❑Tri par permutation
❑Tri par insertion
❑Tri par fusion
❑Tri rapide
3
❑…etc
Tri par sélection
( Appelé également Tri par minimum successif )
On considère un tableau tab de n entiers qu’on souhaite trier selon l’ordre
croissant.
tab: 20 30 50 10 40 Taille: n = 5
Principe de l’algorithme:
Pour une position donnée du tableau tab, on cherche l’élément qui doit
y être placé. Pour cela, on parcourt le tableau de gauche à droite, et on
positionne à chaque fois le plus petit élément qui se trouve dans le
sous-tableau droit.
Donc pour trier le sous-tableau tab[i..n], il suffit de positionner au
rang i le plus petit élément de ce sous-tableau et de trier le sous-tableau
tab[i+1..n].
4
Tri par sélection
tab: 20 30 50 10 40 Taille: n = 5
for (i = 0; i < n-1; i++)
{
min = tab[i];
k = i;
i = 0 20 30 50 10 40
for (j = i + 1; j < n; j++)
{
if (tab[j] < min) i = 1 10 30 50 20 40
{
min = tab[j];
k = j; i = 2 10 20 50 30 40
}
}
i = 3 10 20 30 50 40
if (k != i)
{
temp = tab[i];
tab[i] = tab[k]; 10 20 30 40 50
tab[k] = temp;
}
}
5
Tri par sélection
void permuter (int* x, int* y){
int temp;
for (i = 0; i < n-1; i++) temp = *x;
{ *x = *y;
min = tab[i]; *y = temp;
k = i; }
for (j = i + 1; j < n; j++)
{ int rangMinTab(int n,int k,int T[]){
if (tab[j] < min) int i, pos = k;
{ for (i = pos + 1; i < n; i++)
min = tab[j]; if (T[i] < T[pos]) pos = i;
k = j; return pos;
} }
}
if (k != i) void triSelectif (int n, int tab[]){
{ int i, posMin;
temp = tab[i]; for (i = 0; i < n-1; i++)
tab[i] = tab[k]; {
tab[k] = temp; posMin = rangMinTab(n,i,tab);
} if (i != posMin)
} permuter(&tab[i],&tab[posMin]);
}
}
6
Tri par sélection
7
Tri par sélection
8
Tri à bulles
( Appelé également Tri par propagation ou bubble sort)
tab: 50 40 30 20 10 Taille: n = 5
Principe de l’algorithme:
On parcourt le tableau tab, et dès que l’on trouve que deux
éléments successifs tab[i] et tab[i+1] pour i variant
de 0 à n-2 sont dans le mauvais ordre, on les échange.
L’algorithme s’arrête lorsqu’on constate qu’aucune
permutation n’a été effectuée lors du dernier survol du
tableau.
9
Tri à bulles (version 0)
i = 0 50 40 30 20 10
tab: 50 40 30 20 10 Taille: n = 5
40 50 30 20 10
40 30 50 20 10
for (i = 0; i < n - 1; i++)
{ 40 30 20 50 10
for ( j = 0; j < n-1-i ; j++)
{
i = 1 40 30 20 10 50
if (tab[j] > tab[j+1])
{
30 40 20 10 50
temp = tab[j];
tab[j] = tab[j+1];
tab[j+1] = temp; 30 20 40 10 50
}
} i = 2 30 20 10 40 50
}
20 30 10 40 50
i = 3 20 10 30 40 50
10 10 20 30 40 50
Tri à bulles (version 1)
❑ Normalement, l’algorithme doit s’arrêter lorsqu’on constate
qu’aucune permutation n’a été effectuée lors du dernier
survol du tableau.
i = 0;
for (i = 0; i < n - 1; i++) do
{ {
nbp = 0; /* # permutations */ nbp = 0; /*nombre de permutations*/
for (j = 0; j < n-1-i ; j++) for ( j = 0; j < n-1-i ; j++)
{ {
if (tab[j] > tab[j+1]) if (tab[j] > tab[j+1])
{ {
temp = tab[j]; temp = tab[j];
tab[j] = tab[j+1]; tab[j] = tab[j+1];
tab[j+1] = temp; tab[j+1] = temp;
nbp = 1; nbp = 1;
} }
} }
if (nbp == 0) break; i++;
} }
while (nbp != 0);
11
Tri à bulles (version 1)
12
Tri à bulles (version 2)
❑ On peut limiter le parcours au dernier élément à partir duquel il n’y a pas
eu de permutation étant donné que la partie à sa droite est déjà triée.
Pour cela, il faut mémoriser cet indice pour le parcours suivant.
Version 2
indDernPermutAncien = n – 1;
indDernPermut = n – 1;
Version 1 i = 0;
i = 0; do
do {
{ nbp = 0;
nbp = 0;
for ( j = 0; j < n-1-i ; j++) for (j = 0; j < indDernPermutAncien ; j++)
{ {
if (tab[j] > tab[j+1]) if (tab[j] > tab[j + 1])
{ {
temp = tab[j]; temp = tab[j];
tab[j] = tab[j+1]; tab[j] = tab[j + 1];
tab[j+1] = temp; tab[j + 1] = temp;
nbp = 1; nbp = 1;
} indDernPermut = j;
} }
i++; }
} indDernPermutAncien = indDernPermut;
while (nbp != 0); i++;
}
13 while (nbp != 0);
Tri d’un tableau avec qsort()
#include <stdio.h>
#include <stdlib.h>
int comparer(int* x, int* y)
{
return (*x) - (*y);
}
int main()
{
int tailleTab = 10;
int tab[tailleTab] = {10, 5, 30, 25, 55, 1, 100, 77, 99, 88};
int i;
qsort(tab, tailleTab, sizeof(int), comparer);
for (i = 0; i < 10; i++)
printf("%d\t", tab[i]);
printf("\n");
return 0;
}
14
Comparaison entre méthodes de Tri
❑ On peut comparer les méthodes de tri en évaluant le temps d’exécution de chaque algorithme.
Le tableau sera rempli avec des nombres aléatoires avec srand() et rand().
❑ Utiliser la fonction clock() de la bibliothèque <time.h>
❑ La fonction clock() fournit une valeur entière représentant le nombre de périodes
d’horloge depuis le début de l’exécution du main().
Pour convertir cette valeur en seconde, il faut diviser par le nombre de périodes par seconde
de la machine qui est donné par la constante CLOCKS_PER_SEC.
…
Exemple: #include <time.h>
void main()
Pour mesurer le temps {
d’exécution de ….
Algorithme_de_tri: int n1, n2;
float temps1;
…..
n1 = clock();
Algorithme_de_tri;
n2 = clock();
temps1 = (float)(n2 – n1)/CLOCKS_PER_SEC;
…..
15 Voir Fichier: temps_execution_methode_tri_tableau_structure.c
Comparaison entre méthodes de Tri
1. Cas d’un tableau de données aléatoirement rangées
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
void main()
{
int tailleTab = 100000;
int tab1[tailleTab], tab2[tailleTab];
int i, j, k, temp, min, x;
int nbp; /* nombre de permutation dans pour l'algorithme Tri a bulles */
int np1, np2; /* pour compter le nombre de periodes d'horloges */
float tempsTriSuccessif, tempsTriBulles;
/* remplir les deux tableaux tab1 et tab2 avec les memes donnees */
/* pour que la comparaison ait un sens */
srand(time(NULL));
for (i = 0; i < tailleTab; i++){
x = rand();
tab1[i] = x;
tab2[i] = x;
}
comparaison_triMminimumsSuccessifs_vs_triBulles_tableau_aleatoire.c
16
...
np1 = clock();
/* ****************** Tri par minimum successif ********************* */
for (i = 0; i < tailleTab - 1; i++){
min = tab1[i];
k = i;
for (j = i + 1; j < tailleTab; j++){
if (tab1[j] < min){
min = tab1[j];
k = j;
}
}
if (k != i){
temp = tab1[i];
tab1[i] = tab1[k];
tab1[k] = temp;
}
}
/* **************************************************************** */
np2 = clock();
tempsTriSuccessif = (float)(np2 - np1)/ CLOCKS_PER_SEC;
printf("\t Le temps mis pour trier avec minimum successif est :
%f\n",tempsTriSuccessif);
17
np1 = clock();
/* ********************* Tri à bulles ********************** */
j = 0;
do{
nbp = 0;
for ( i = 0; i < tailleTab – 1 - j ; i++){
if (tab2[i] > tab2[i + 1]){
temp = tab2[i];
tab2[i] = tab2[i + 1];
tab2[i + 1] = temp;
nbp = 1;
}
}
j++;
}
while (nbp != 0);
/* *********************************************************** */
np2 = clock();
tempsTriBulles = (float)(np2 - np1)/ CLOCKS_PER_SEC;
printf("\t Le temps mis pour trier avec tri a bulles est :
%f",tempsTriBulles);
}
18
Comparaison entre méthodes de Tri
2. Cas d’un tableau de données déjà triées
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
void main()
{
int tailleTab = 100000;
int tab1[tailleTab], tab2[tailleTab];
int i, j, k, temp, min, x;
int nbp; /* nombre de permutation dans pour l'algorithme Tri a bulles */
int np1, np2; /* pour compter le nombre de periodes d'horloges */
float tempsTriSuccessif, tempsTriBulles;
/* remplir les deux tableaux tab1 et tab2 avec les memes donnees */
/* pour que la comparaison ait un sens */
/* ******* Tableaux déjà triés ******** */
for ( i = 0; i < tailleTab; i += 1000)
for (j = 0; j < 1000; j++)
{
tab1[i + j] = i;
tab2[i + j] = i;
}
19 comparaison_triMminimumsSuccessifs_vs_triBulles_cas_tableau_deja_trie.c
Comparaison entre méthodes de Tri
1. Cas d’un tableau de données aléatoirement rangées
1000 2000 5000 10000 20000 40000 100000
Sélection 0,001000 0,005000 0,028000 0,108000 0,450000 1,749000 10,723000
Bulles (vers. 0)
Bulles (vers. 1) 0,002000 0,007000 0,051000 0,247000 1,087000 4,440000 28,614000
Bulles (vers. 2)
qsort
comparaison_triMminimumsSuccessifs_vs_triBulles_tableau_aleatoire.c
2. Cas d’un tableau de données déjà triées
1000 2000 5000 10000 20000 40000 100000
Sélection 0,0010 0,0050 0,031000 0,109000 0,436000 1,716000 10,686000
Bulles (vers. 0)
Bulles (vers. 1) 0,000000 0,000000 0,000000 0,000000 0,000000 0,000000 0,000000
Bulles (vers. 2)
qsort
comparaison_triMminimumsSuccessifs_vs_triBulles_cas_tableau_deja_trie.c
20
Fin();
21
