Recherche et tri dans un tableau

id: 33-238-recherche-et-tri-tableau slug: 33-238-recherche-et-tri-tableau titre: Recherche et tri dans un tableau chapitre: 4 chapitre_titre: 'Les structures de données : les tableaux' lecon: 3 niveau: 4eme-sci ordre: 30 prerequis:

• tableaux-declaration
• sous-programmes-fonctions-procedures duree_estimee_min: 45 mots_cles:
• recherche sequentielle
• recherche dichotomique
• tri selection
• tri bulles
• tri insertion
• tableau langages:
• analyse
• pascal objectifs:
• Mettre en œuvre une recherche séquentielle dans un tableau
• Mettre en œuvre une recherche dichotomique sur un tableau trié
• Décrire et implémenter les tris par sélection, à bulles et par insertion
• Distinguer les conditions d'application de chaque méthode de recherche status: published source_pdf: 33_238.pdf source_pages:
• 1 kind: cours

Recherche dans un tableau

Énoncé : Écrire un programme qui permet de saisir n entiers à mettre dans un tableau T, puis une valeur v, et qui vérifie si v existe dans T ou non.

Recherche séquentielle

L'idée est de parcourir le tableau, élément par élément, jusqu'à trouver la valeur recherchée ou bien atteindre la fin du tableau.

0) DEF FN recherche1 (T:TAB, n:entier, v:entier) : Booléen
1) i ← 0
   trouve ← Faux
   Répéter
       i ← i+1
       si T[i] = v alors trouve ← vrai
   jusqu'à (trouve) ou (i = n)
2) recherche ← trouve
3) Fin recherche1

0) DEF FN recherche1 (T:TAB, n:entier, v:entier) : Booléen
1) i ← 0
   trouve ← Faux
   Répéter
       i ← i+1
       si T[i] = v alors trouve ← vrai
   jusqu'à (trouve) ou (i = n)
2) recherche ← trouve
3) Fin recherche1

function recherche1(T:tab; n:integer; v:integer):boolean;
var
    i:integer;
    trouve:boolean;
begin
    i:=0;
    trouve:=false;
    repeat
        i:=i+1;
        if t[i]=v then trouve:=true;
    until (trouve) or (i=n);
    recherche:=trouve;
end;

Autre méthode (recherche séquentielle, variante)

Ici on n'utilise pas de booléen trouve à l'intérieur de la boucle : on sort dès qu'on trouve la valeur ou qu'on atteint la fin, puis on teste après la boucle.

0) DEF FN recherche2 (T:TAB, n:entier, v:entier) : Booléen
1) i ← 0
   Répéter
       i ← i+1
   jusqu'à (T[i] = v) ou (i = n)
2) si T[i] = v alors recherche ← VRAI
   sinon recherche ← FAUX
3) Fin recherche2

T.D.O locaux :

Recherche dichotomique

La recherche dichotomique s'applique sur un tableau trié. On compare la valeur recherchée à l'élément du milieu, puis on poursuit la recherche dans la moitié pertinente du tableau.

0) DEF FN recherche_dicho (T:TAB, n:entier, v:entier) : Booléen
1) a ← 1
   b ← n
   trouve ← FAUX
   répéter
       m ← (a+b) DIV 2
       si T[m] = v alors trouve ← VRAI
       sinon si T[m] > v alors b ← m-1
             sinon a ← m+1
       finsi
   jusqu'à (trouve) ou (a > b)
2) recherche_dicho ← trouve
3) Fin recherche_dicho

0) DEF FN recherche_dicho (T:TAB, n:entier, v:entier) : Booléen
1) a ← 1
   b ← n
   trouve ← FAUX
   répéter
       m ← (a+b) DIV 2
       si T[m] = v alors trouve ← VRAI
       sinon si T[m] > v alors b ← m-1
             sinon a ← m+1
       finsi
   jusqu'à (trouve) ou (a > b)
2) recherche_dicho ← trouve
3) Fin recherche_dicho

function recherche_dicho(T:tab; n:integer; v:integer):boolean;
var
    a,b,m:integer;
    trouve:boolean;
begin
    a:=1;
    b:=n;
    trouve:=false;
    repeat
        m:=(a+b) div 2;
        si T[m]=v then trouve:=true
        else if T[m]>v then b:=m-1
             else a:=m+1;
    until (trouve) or (a>b);
    recherche_dicho:=trouve;
end;

Tri d'un tableau

Trier un tableau consiste à réorganiser ses éléments dans un ordre (croissant ou décroissant). Nous présentons ici trois méthodes classiques.

Tri par sélection

Principe : à chaque itération, on recherche la position du minimum dans la partie non triée du tableau, puis on l'échange avec le premier élément de cette partie.

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 Permute(T[i], T[pos_min]) Finsi
   FinPour
2) Fin Tri_selection

Tri à bulles

Principe : on parcourt le tableau et on échange tout couple d'éléments consécutifs mal ordonnés. On répète tant qu'au moins un échange a eu lieu.

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

Tri par insertion

Principe : on prend les éléments un par un (à partir du deuxième) et on insère chacun à sa bonne place dans la partie déjà triée à sa gauche.

0) DEF Proc Tri_Insertion (VAR T:TAB ; n:entier)
1) Pour i de 2 à n faire
       Tmp ← T[i]
       j ← i
       // Decaler(var T:tab, var j, v:entier)
       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

Synthèse