Correction TD 8 : Algorithmes de tri

Licence 1 MASS semestre 2, 2007/2008

Exercice 1 : Tester

On consid`ere que le tri devrait ˆetre selon l"ordre croissant. a-AlgorithmeTest(T: tableau d"entiers;n: entier) : bool´een d´ebut variablei: entier i←0 i←i+ 1 fin tant que retourneri≥n-1 fin b-AlgorithmeCompter(T: tableau d"entiers;n: entier) : entier d´ebut variablei,c: entier c←0 pouride0`an-2faire siT[i]> T[i+ 1]alors c←c+ 1 fin si fin pour retournerc fin

Exercice 2 : Nombre d"op´erations

a- Pour effectuerkrecherches dans un tableau non tri´e de taillenil faut compter en moyenne kn

2op´erations.

b- Trier le tableau se fait ennlog2nauquel il faut ajouter la recherche di- chotomique qui se fait en log

2net qu"on doit fairekfois : (n+k)log2n.

c- En moyenne il est donc plus int´eressant de trier le tableau et de faire une recherche dichotomique des quek≥log2n. 1

Exercice 3 : Suppressions

a- On commence par chercher l"´el´ements`a supprimer et ensuite on d´ecale les suivants. Algorithmesuppression(T: tableau d"entiers,s,k: entier) : entier d´ebut variablei,r: entier r←0 r←r+ 1 fin tant que sir > k-1alors retournerk sinon pourider`ak-2faire

T[i]←T[i+ 1]

fin pour retournerk-1 fin si fin b-AlgorithmesuppressionOrdonn´ee(T: tableau d"entiers,s,k: entier) : entier d´ebut variablei,r,d: entier r←0 siT[r] =salors d←d+ 1 fin si r←r+ 1 fin tant que sir > k-1etd= 0alors retournerk sinon pourider-d`ak-2faire

T[i]←T[i+d]

fin pour retournerk-d fin si fin

Exercice 4 : Ordre d´ecroissant

a-AlgorithmetriS´election(T: tableau d"entiers,n: entier) : rien d´ebut 2 variablei,jMax: entier pouride0`an-2faire jMax←indiceMax(T,n,i)

Permuter(T,i,jMax)

fin pour fin AlgorithmePermuter(T: tableau d"entiers,i,j: entier) : rien d´ebut variablex: entier x←T[i]

T[i]←T[j]

T[j]←x

fin AlgorithmeindiceMax(T: tableau d"entiers,n,k: entier) : entier d´ebut variablei,iMax : entier iMax←k pouridek+ 1`an-1faire siT[i]> T[iMax]alors iMax←i fin si fin pour retourneriMax fin b-AlgorithmetriInsertion(T: tableau d"entiers,n: entier) : rien d´ebut variablei: entier pouride1`an-1faire

Ins´erer(T,i)

fin pour fin Algorithmeins´erer(T: tableau d"entiers,i: entier) : rien d´ebut variablej,x: entier x←T[i] j←i-1

T[j+ 1]←T[j]

j←j-1 fin tant que

T[j+ 1]←x

fin 3quotesdbs_dbs4.pdfusesText_8

[PDF] Correction TD 8 : Algorithmes de tri - LISIC

Les tableaux 1 Exercice 1 - LIPN

Tableaux - CORRIGE - grug

Exercices avec Solutions

Algorithmique - Correction du TD3

exercices corrigés algorithmepdf

SUJET + CORRIGE