Recherche dans un tableau: Recherche dichotomique : Tri_Sélection :
Écrire un programme qui permet de saisir n entiers à 1 2 3 4 5 6 7 0)DEF Proc Tri_selection (VAR T :TAB ; n :entier)
mettre dans un tableau T puis une valeur v, puis vérifie V est ici si T[m]>V V est ici si T[m]<V 1)Pour i de 1 à n-1 faire premposmin(T:tab, i:entier, n:entier):entier
si v existe dans T ou non. a=1 m b=n [pos_min←i] Pour j de i+1 à n faire
Recherche séquentielle (milieu de a et b) Si ( T[j] < T[pos_min])Alors
0) DEF FN recherche1 (T:TAB,n: Algorithme de la fonction recherche_dicho: pos_min ← j
entier,v:entier): Booléen 0) DEF FN recherche_dicho (T:TAB,n:
1) i← 0 trouve ←Faux Finsi
entier,v:entier): Booléen
Répéter FinPour
1) a← 1, b← n, trouve← FAUX
i← i+1 Si ( pos_min < > i) Alors Permute(T[i], T[Pos_min])
répéter
si T[i]=v alors trouve←vrai
m← (a+b) DIV 2 Finsi
jusqu'a (trouve) ou (i=n) FinPour
2) recherche← trouve si T[m]=v alors trouve← VRAI
sinon si T[m]>v alors b← m-1 2)Fin Tri_selection
3) Fin recherche1
T.D.O locaux(Tableau de déclaration des objets locaux) sinon a← m+1 Tri_Bulles :
Objet Type/Nature Rôle finsi 0) DEF Proc Tri_Bulles (VAR T :TAB ; n :entier)
jusqu'a (trouve) ou (a>b)
i Entier 1) Répéter
2) recherche_dicho←trouve
trouve booléen 3) Fin recherche_dicho Echange← faux
Autre méthode : T.D.O locaux(Tableau de déclaration des objets locaux) Pour i de 1 à n-1 faire
0) DEF FN recherche2 (T:TAB,n: entier,v:entier): Booléen Si ( T[i] > T[i+1])Alors Permute(T[i], T[i+1])
Objet Type/Nature Rôle
1) i← 0 Echange ← vrai
Répéter a,b,m Entier
FinSi
i← i+1 trouve booléen
FinPour
jusqu'a (T[i]=v) ou (i=n)
n ←n-1
2) si T[i]=v alors recherche← VRAI En Pascal :
Jusqu'à (Echange = Faux) ou (n=1)
sinon recherche←FAUX function
3) Fin recherche2 2) Fin Tri_Bulles
recherche_dicho(T:tab;n:integer;v:integer):boolean;
T.D.O locaux(Tableau de déclaration des objets locaux) var a,b,m:integer;trouve:boolean; Tri_Insertion :
Objet Type/Nature Rôle begin 0) DEF Proc Tri_Insertion (VAR T :TAB ; n :entier)
i Entier a:= 1 ; b:= n; trouve:=false; 1) Pour i de 2 à n faire
En Pascal : repeat Tmp ← T[i]
Cours d’ informatique en ligne :
function recherche1(T:tab;n:integer;v:integer):boolean; m:=(a+b) div 2; j←i Decaler(var T:tab, var j, v:entier)
var i:integer; trouve:boolean; si T[m]=v then trouve:=true else Tant que ( j >1) et (T[j-1] > Tmp ) faire
begin if T[m]>v then b:=m-1 else a:=m+1; T[j] ←T[j -1]
i:=0; trouve:=false;
until (trouve)or (a>b); j←j–1
repeat
recherche_dicho:=trouve; FinTantQue
i:=i+1;
if t[i]=v then trouve:=true; end; T[j ] ←Tmp
until (trouve) or (i=n); FinPour
recherche:=trouve; 2) FIN Tri_Insertion
end;
