Recherche dans un tableau: ➔ Recherche dichotomique: Tri_Sélection

Écrire un programme qui permet de saisir n entiers à mettre 1 2 3 4 5 6 7 0)DEF Proc Tri_selection (VAR T :TAB ; n :entier)
dans un tableau T puis une valeur v, puis vérifie si v existe 1)Pour i de 1 à n-1 faire
V est ici si T[m] > v V est ici si T[m] < v premposmin(T:tab, i:entier, n:entier):entier
dans T ou non.
a=1 m b=n 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
Analyse de la fonction Recherche: Analyse de la fonction recherche_dicho:
DEF FN recherche_dicho (T:TAB,n: entier,v:entier): Booléen pos_min  j
S L.D.E O.U
DEF FN recherche (T:TAB,n: entier,v:entier): Booléen Finsi
O.U 2 Résultat=recherche_dichotrouve a
S L.D.E
1 trouve=[a 1, b n, trouve FAUX] b FinPour
2 Résultat=[] si T[i]=v alors recherche VRAI i
répéter trouve
sinon recherche FAUX m Si ( pos_min < > i) Alors Permute(T[i], T[Pos_min])
[m (a+b) DIV 2] si T[m]=v alors trouve VRAI
finsi Finsi
1 i=[i 0]Répéter sinon si T[m]>v alors b m-1
FinPour
sinon a m+1
i i+1 2)Fin Tri_selection
finsi
jusqu'a (T[i]=v) ou (i=n)
3 FIN recherche jusqu'a (trouve) OU (a>b) Tri_Bulles
3 FIN recherche_dicho
0) DEF Proc Tri_Bulles (VAR T :TAB ; n :entier)
T.D.O.Locaux: Objet Type/Nature
T.D.O.Locaux: Objet Type/Nature 1) Répéter
i entier
trouve booléen Echange faux
Remarque: a,b,m entier
Pour i de 1 à n-1 faire
La recherche dichotomique s'applique sur un tableau trié.
Algorithme de la fonction recherche: Algorithme de la fonction recherche_dicho: Si ( T[i] > T[i+1])Alors Permute(T[i], T[i+1])
0) DEF FN recherche (T:TAB,n: entier,v:entier): Booléen 0) DEF FN recherche_dicho (T:TAB,n: entier,v:entier): Booléen
1) i 0 1) a 1, b n, trouve FAUX Echange  vrai
Répéter répéter FinSi
i i+1 m (a+b) DIV 2
jusqu'a (T[i]=v) ou (i=n) FinPour
si T[m]=v alors trouve VRAI
2) si T[i]=v alors recherche VRAI sinon si T[m]>v alors b m-1 n n-1
sinon recherche FAUX sinon a m+1
3) Fin recherche Jusqu'à (Echange = Faux) ou (n=1)
finsi
jusqu'a (trouve) OU (a>b) 2) Fin Tri_Bulles
Devoirs et exemens sur : www.kiteb.net

2) recherchedicotrouve Tri_Insertion :
3) Fin recherche_dicho 0) DEF Proc Tri_Insertion (VAR T :TAB ; n :entier)
En Pascal: En Pascal: 1) Pour i de 2 à n faire
function recherche(T:tab;n:integer;v:integer):boolean; function recherche_dicho(T:tab;n:integer;v:integer):boolean;
Tmp  T[i]
var i:integer; var a,b,m:integer;trouve:boolean;
begin begin ji Decaler(var T:tab, var j, v:entier)
i:=0; a:= 1 ; b:= n; trouve:=false; Tant que ( j >1) et (T[j-1] > Tmp ) faire
repeat repeat T[j]T[j -1]
i:=i+1; m:=(a+b) div 2; jj–1
until (T[i]=v)or (i=n) si T[m]=v then trouve:=true else
if (T[i]=v)then rechercher:=true FinTantQue
if T[m]>v then b:=m-1 else a:=m+1;
else rechercher:=false; until (trouve)or (a>b); T[j ] Tmp
end; recherche_dicho:=trouve; FinPour
end; 2) FIN Tri_Insertion