Soit T un tableau de N éléments ordonnés et x un élément de même type que les éléments de T. Il s'agit d'examiner la présence de x dans T. Comme le tableau est ordonné, il satisfait la spécification suivante :
i[1 , N-1]T (i) ≤ T (i+1)
Au lieu de faire une recherche linéaire (Parcourir tout le tableau T du premier élément au dernier), on décompose le tableau en deux sous-tableaux T1 et T2 et trois cas peuvent se produire :
-x est trouvé la recherche est terminé.
-la recherche continue dans T1.
-la recherche continue dans T2.
Exemple
Soit le tableau suivant T :
1
2
3
4
5
6
7
8
3
7
8
8
11
15
20
24
Vous constatez que letableau Test déjà ordonné.On va voir comment s'applique laméthode de recherche binaire pour rechercher si x = 20 existe dans le tableau T.
On divise l'intervalle des indices [1,8] en deux intervalles [1,4] et [5,8]. On obtient deux tableaux T1 etT2.
1
2
3
4
5
6
7
8
3
7
8
8
11
15
20
24
La recherche va continuer dans letableau T2 puisque x (20) est plus supérieur que le plus grand élément de T1. Donc l'intervalle de recherche devient [5,8] et on va le diviser à son tour en deux intervalles [5,6] et [7,8].
5
6
7
8
11
15
20
24
De même, la recherche va continuer dans T2. L'intervalle de recherche devient [7,8]. On le divise en deux intervalles [7,7] et [8,8].Finalement, x est trouvé.
7
8
20
24
Le programme de la recherche dichotomique est le suivant :
Tableau T(N) : Entier
Variables inf , sup , milieu , x : Entier
Variable Trouve : Booléen
DEBUT
Trouve ← Faux
inf = 1
sup ← N
TANT QUE inf ≤ sup ET Trouve = Faux
milieu ← (inf + sup) Div 2‘ Div est la division entière
SI T(milieu) = x ALORS
Trouve ← Vrai
SINON
SI T(milieu) < x alors
inf ← inf + 1
SINON
sup ← milieu –1
FIN SI
FIN SI
FIN TANT QUE
SI Trouve = Vrai ALORS
Ecrire « L’élément » , x , « existe dans T »
SINON
Ecrire « L’élément » , x , « n’existe pas dans T »
Soit T un tableau de N éléments muni d’une relation d’ordre ”. Trier ce tableau c’est construire un algorithme qui devra satisfaire à la spécification suivante :
i[1 , N-1]T (i) ≤ T (i+1)
Dans ce paragraphe on va traiter plusieurs algorithmes de tri : tri par sélection, tri par bulle, tri par comptage, tri par insertion, tri par shell.
10.1. Tri par bulle
Principe
Ce tri permet de faire remonter petit à petit un élément trop grand vers la fin du tableau en comparant les éléments deux à deux.
Si un élément d’indice i est supérieur à un élément d’indice i+1 on les échange et on continue avec le suivant. Lorsqu’on atteint la fin du tableau on repart du début. On s’arrête lorsque tous les éléments du tableau sont bien placés c'est-à-dire qu’on aura aucun changement d’éléments à effectuer.
Algorithme
Tableau T(N) : Entiers
Variables j , nc : Entiers
DEBUT
REPETER
nc ← 0
POUR j = 1 A (N-1)
SI T(j) > T(j+1) ALORS
nc ← nc +1
z ← T(j)
T(j) ← T(j+1)
T(j+1) ← z
FIN SI
FIN POUR
JUSUQU’A nc = 0
FIN
Exemple
Soit le tableau suivant :
52
10
1
25
Boucle REPETER
Etat du tableau
Valeur de nc
Itération 1
10
52
1
25
3
10
1
52
25
10
1
25
52
Itération 2
1
10
25
52
1
1
10
25
52
1
10
25
52
Itération 3
1
10
25
52
0
10.2. Tri par sélection
Principe : Soit T un tableau de N éléments. On cherche le plus petit élément du tableau et on le place à la première position. Après, on cherche le pluspetit dansles (N-1) qui reste et onle place en deuxième position et ainsi de suite.
5210125623855323
15210256238 55323
1352102562855323
1335210256285523
1338521025625523
1338105225625523
1338102352256255
1338102325526255
1338102325526255
1338102325525562
Algorithme :
POUR i ALLANT DE 1 A 9
FAIRE
Petit ← TAB (i)
POUR j ALLANT DE i A 10
FAIRE
Si (TAB (j) < petit) ALORS petit ← TAB (j) ; position ← j FSI
FinPour
POUR j ALLANT DE position A i+1 PAS –1
FAIRE
TAB(j) ← TAB (j-1) ;
FinPour
TAB (i) ← petit ;
FinPour
5.4.2- Le tri bulle :
FAIRE
Inversion ← FAUX
POUR i ALLANT DE 1 A 9
FAIRE
Si (TAB (i) > TAB (i+1))
ALORS
Tampon ← TAB (i) ;
TAB (i) ← TAB (i+1) ;
TAB (i+1) ←Tampon
Inversion ←VRAI
FSI
FinPour
JUSQUA (inversion = FAUX) ;
5.4.3- Le tri par permutation :
POUR i ALLANT DE 1 A 9
FAIRE
SI (TAB (i+1) < TAB (i))
ALORS
Abouger ← TAB (i+1)
j ← 1 ;
TanQue ((j < i) ET (TAB (j) < TAB (i+1)))
Faire j ← j+1
FTQ
POUR k ALLANT DE i+1 A j+1 PAS –1
Faire
TAB (k) ← TAB (k-1)
FinPour
TAB (j) ← abouger
FSI
Fin Pour
5.4.4- Le tri par comptage :
POUR i ALLAN DE 1 A 10
FAIRE
RES (i) ← 0
NB (i) ← 0
POUR j ALLANT DE 1 A 10
FAIRE
Si TAB (j) < TAB (i) ALORS NB (i) ← NB (i) + 1 FSI
