Nicolas Delestre et Michel Mainguenaud …

1 Algorithmes de triNicolas Delestre et Michel pour l ENSICAEN parLuc algortihmes de triD finition d un algorithme de tri,Le tri par minimum successifs,Le tri a bulles,Le tri algorithmes de s quentielle non tri eRecherche s quentielle tri e,Recherche finition d un algorithme de TriLes tableaux permettent de stocker plusieurs l ments de m me type ausein d une seule entit ,Lorsque le type de ces l ments poss de un ordre total, on peut donc lesranger en ordre croissant ou d croissant,Trier un tableau c est donc ranger les l ments d un tableau en ordrecroissant ou d croissantDans ce cours on ne fera que des tris en ordre croissantIl existe plusieurs m thodes de tri qui se diff rencient par leur complexit d ex cution et leur complexit de compr hension pour le tout d abord :le tri par minimum successifTableaux proc dure les algorithmes de tri utilisent une proc dure qui permet d changer (depermuter) la valeur de deux variables Dans le cas o les variables sont enti res,la proc dure changer est la suivante :proc dure changer(E/S a,b : Entier)D clarationtemp : Entierd buttemp aa bb tempfinTableaux par minimum tri par minimum successif estun tri par s lection :Pour une place donn e, on s lectionne l l ment qui doit y trepositionn De ce fait, si on parcourt la tableau de gauche droite, on positionne chaque fois le plus petit l ment qui se trouve dans le sous tableau droitOu plus g n ralement : Pour trier le sous-tableau t[ ] ilsuffit de positionner au rang i le plus petit l ment de cesous-tableau et de trier le sous-tableau t[i+ ]Tableaux par minimum exemple, pour trier<101, 115, 30, 63, 47, 20>, on va avoir les bouclessuivantes.

2 I=1<101, 115, 30, 63, 47, 20>i=2<20, 115, 30, 63, 47, 101>i=3<20, 30,115, 63, 47, 101>i=4<20, 30,47, 63, 115, 101>i=5<20,30, 47, 63, 115, 101>Donc en sortie :<20, 30, 47, 63, 101, 155>Il nous faut donc une fonction qui pour soit capable de d terminer le plus petit l ment (en fait l indice du plus petit l ment) d un tableau partir d un certainrangTableaux (t : Tableau[ ] d Entier ; rang, nbElements :Naturel) :NaturelD clarationi, indiceCherche : Natureld butindiceCherche rangpouri rang+1 nbElementsfairesit[i]<t[indiceCherche]al orsindiceCherche ifinsifinpourretournerindiceCherchefinTa bleaux par minimum algorithme de tri est donc :proc dureeffectuerTriParMimimumSuccessif(E/S t : Tableau[ ]d Entier; E nbElements : Naturel)D clarationi,indice : Natureld butpouri 1 nbElements-1faireindice indiceDuMinimum(t,i,nbElements)sii6=indi cealorsechanger(t[i],t[indice])finsifinp ourfinTableaux Recherche du minimum sur un tableau de taillen Parcours du (n) =n+T(n 1) T(n) =n(n+ 1)2 Complexit enO(n2).

3 Tableaux tri bullesPrincipe de la m thode : S lectionner le minimum du tableau enparcourant le tableau de la fin au d but et en changeant tout coupled l ments cons cutifs non ordonn bulles : ExemplePar exemple, pour trier<101, 115, 30, 63, 47, 20>, on va avoir les bouclessuivantes :i=1<101, 115, 30, 63, 47,20> <101, 115, 30, 63,20, 47> <101, 115, 30,20, 63, 47> <101, 115,20, 30, 63, 47> <101,20, 115, 30, 63, 47>i=2<20, 101, 115, 30, 63, 47>i=3<20, 30,101, 115, 47, 63>i=4<20, 30,47,101, 115, 63>i=4<20, 30, 47, 63, 101, 115>Donc en sortie :<20, 30, 47, 63, 101, 155>Tableaux bulles : l algorithmeproc dureTriBulles(E/S t : Tableau[ ] d Entiers,nbElements : Naturel)D clarationi,k : Natureld butpouri 0 nbElements-1fairepourk nbElements-1 i+1fairesit[k]<t[k-1]alorsechanger(t[k], t[k-1])finsifinpourfinpourfinTableaux bulles : Complexit sNombre de tests(moyenne et pire des cas) :T(n) =n+T(n 1) T(n) =n(n+ 1)2 Compl xit enO(n2).

4 Nombre d changes (pire des cas):E(n) =n 1 +n 2 + + 1 O(n2)Nombre d change (en moyenne)O(n2)(calcul plus compliqu )En r sum : complexit enO(n2).Tableaux tri rapidePrincipe de la m thodeChoisir un l ment du tableau appel pivot,Ordonner les l ments du tableau par rapport au pivotAppeler r cursivement le tri sur les parties du tableau gauche et droite du partitionproc durepartition(E/S t: Tableau[ ] d Entier; E :premier, dernier :Naturel, S: indPivot:Naturel)D clarationcompteur, i :Naturel,pivot:Entierd butcompteur premierpivot t[premier]pouri premier+1 dernierfairesit(i)< pivotalorscompteur compteur+1echange(t[i],t[compteur]);fins ifinpourechanger(T,compteur,premier)indP ivot compteurfinTableaux de partition6(c)3(i)0917825463(i,c)09178254 630(i,c)9178254630(c)9(i)178254630(c)91( i)782546301(c)9(i)782546301(c)9782(i)546 3012(c)789(i)54630125(c)897(i)46301254(c )978(i)4301256(c)978 Tableaux tri rapideAlgorithme :proc duretriRapide(E/S t : Tableau[ ] d Entier.)

5 Gauche,droit :Naturel)D clarationpivot :Natureld butsigauche<droitealorspartition(t,gauche,droite,pivot)triRapide(t,gauche,pivot-1)triRapide(t,pivot+1,droite)finsifinTableaux ..Dans l exemple pr c dent on passe de :<6,3,0,9,1,7,8,2,5,4> <4,3,0,1,2,6,8,9,7>et on se relance sur :<4,3,0,1,2>et<8,9,7>Tableaux Le tri par rapport au pivot n cessite de parcourir le tableau. On relanceensuite le processus sur les deux sous tableaux gauche et droite (n) =n+T(p) +T(q)p, qtaille des sous tableaux gauche et le meilleur des casp=qet:T(n) =n+ 2T(n2)Posonsn= 2p. On obtient :T(p) = 2p+ 2T(p 1)=p2p+ 2pEn repassant enn:T(n) = log2(n).n+n. La complexit est donc enO(nlog2(n))(dans le meilleur des cas).Tableaux de rechercheRecherche dans un tableau non tri .fonctionrechercheNonTrie(tab : Tableau[ ] d l ments, x : l ment) :NaturelD clarationi : Natureld buti 0tant que(i MAX) et (tab[i]6=x)fairei i+1fintantquesii=MAX+1alorsretournerMAX+ 1finsiretournerifinTableaux de rechercheRecherche s quentielle dans un tableau tri.

6 FonctionrechercheSeqTrie(tab : Tableau[ +1] d l ments, x : l ment):NaturelD clarationi : Natureld buti 0tab[MAX+1] xtant quex>tab[i]fairei i+1fintantqueretournerifinTableaux de recherchefonctionrechercheDicoTrie(tab : Tableau[ ] d l ments, x : l ment) :NaturelD clarationgauche,droit,milieu : Natureld butgauche 0;droit MAXtant quegauche droitfairemilieu (gauche+droit) div 2six=tab[milieu]alors retournermilieufinsisix<tab[milieu]alorsdroit milieu-1sinongauche milieu+1finsifintantqueretournerMAX+1finTableaux cherche 101 dans<20, 30, 47, 63, 101, 115>.i=1<20(g), 30, 47(m), 63, 101, 115(d)>.i=2<20, 30, 47, 63(g), 101(m), 115(d)>.et on renvoi l indice de