Institut Préparatoire aux Etudes d’Ingénieurs – El Manar 2013-2014

1ere Année MP, PC, PT Page 1

Correction problème : Tri par casier

1) Procédure SAISIR (VAR N : entier)

Début

Répéter Lire(N) Jusqu’à N <=1000

Fin SAISIR

2) Procédure SAISIE_TAB (N : entier , VAR T : TAB)

VAR i :entier

Début

Pour i de 1 à N faire

Répéter Lire(T[i])

Jusqu’à (T[i]>= -499) ET (T[i]<=500)

Fin SAISIE_TAB

3) Procédure MIN_MAX (N : entier, T : TAB , VAR min,max :entier)

VAR i : entier

Début

minT[1] , maxmin

pour i de 1 à N faire

si T[i] < min alors minT[i] fin si

si T[i] > max alors maxT[i] fin si

fin pour

Fin MIN_MAX

4) Procédure CONSTRUIRE (N : entier, T : TAB , VAR C :TAB)

VAR min,max,i : entier

Début

MIN_MAX(N,T,min,max)

Lmax-min+1

pour i de 1 à L faire C[i]0 fin pour

pour i de 1 à N faire

C[T[i]-min+1]C[T[i]-min+1]+1

fin pour

Fin CONSTRUIRE

5) Procédure TRIER(N : entier, VAR T : TAB)

VAR min,max,i ,L : entier

C :TAB

Début

MIN_MAX(N,T,min,max)

Lmax-min+1

CONSTRUIRE (N , T , C )

i1

pour k de 1 à L faire

tant que C[k]>0

T[i]min+k-1

C[k]C[k]-1

ii+1

fin tant que

fin pour

Fin TRIER