cours TRI selection insertion bublle sort

cours TRI selection insertion bublle sort

1. I TRI PAR S
´
ELECTION
Un algorithme de tri est, en informatique ou en math´ematiques, un algorithme qui
permet d’organiser une collection d’objets selon une relation d’ordre d´etermin´ee. On
retrouve ces algorithmes dans les bases de donn´ees, dans les moteurs de recherche
jusque dans les jeux 3-D o`u les facettes des objets sont affich´ees par ´eloignement crois-
sant.
I.
1 -
Sur une liste de n ´el´ements, le principe du tri par s´election est le suivant
:
•rechercher le plus petit ´el´ement du tableau, et le placer en premi`ere
position
•rechercher le second plus petit ´el´ement du tableau et le placer en
seconde position;
•continuer de cette fa¸con jusqu’`a ce que le tableau soit enti`erement
tri´e.
D´efinition :
´
Ecrire les ´etapes de l’ex´ecution du tri par selection de L=[9,6,1,4,8]. On
pr´esentera les r´esultats sous forme de tableau avecminle minimum de la
listeLetLtrila liste tri´ee.
Exemple 1 :
L min Ltri
[9,6,1,4,8]1 [1]
[9,6,4,8]4 [1,4]
[9,6,8]6 [1,4,6]
[9] 9[1,4,6,8,9]
Figure 1: Illustration du tri par s´el´ection
2 -
□1 - D´efinir une fonctionminindice(L) renvoyant le minimum et son
indice de la listeL.
□2 - Proposer une fonctiontriselectionpermettant d’obtenir une liste
Ltritri´ee issue deL. On pourra utiliser la m´ethodepop(i) qui supprime
l’´el´ement de positionid’une liste.
Exemple 2 :
1defmin_indice ( L ):
2 m = L [0]
3 indice = 0
4 forkinrange(len( L )):
5 ifm > L [ k ]:
6 m = L [ k ]
7 indice = k
8 returnm , indice
Le tri par s´election s’obtient alors simplement
JB, NG, SR

2. I TRI PAR S
´
ELECTION
1deftri_selection ( L ):
2 Ltri =[]
3 whilelen( L ) >0:
4 x , i =min( L )
5 Ltri . append ( x )
6 L . pop ( i )
7 returnLtri
Il est possible d’obtenir une ´ecriture r´ecursive .On d´efinit tout d’abord une condition
d’arrˆet lorsque la liste ne contient qu’un ´el´ement. Ensuite, on isole le minimum et on
r´eapplique la fonction sur la liste sans le minimum :
1deft r i _ s e l e c t i o n _ r e c ( L ):
2 iflen( L )==1:returnL
3 else:
4 x , i =min( L )
5 return[ x ] + t r i _ s e l e c t i o n _ r e c ( L [: i ] + L [ i +1:])
3 -
a)
L’algorithme propos´e ci-dessus g´en`ere une nouvelle liste tri´ee, le tri ne modifie par la
listeL. Il est donc n´ecessaire d’utiliser de l’espace m´emoir pour cr´eer une nouvelle liste.
On parle alors decomplexit´e spatialequi est ´evalu´e ici du mˆeme ordre de grandeur
que la liste `a trier.
On pourrait proposer une fonction qui muteen placela listeLen modifiant petit
`a petit la liste.
1deftri_selection ( L ):
2 forkinrange(len( L )):
3 x , i = min_indice ( L [ k :])
4 i += k
5 L [ k ] , L [ i ] = L [ i ] , L [ k ]
b) ´e
Evaluons le nombre d’op´eration. On retrouve deux boucles imbriqu´ees :
•un boucle for pour le parcours de la listeL;
•une boucle for pour la fonctionindicemin
Le parcours de la liste ´etant d’une taille d´ecroissante, le nombre d’op´erations `a
effectuer est de l’ordre de :
n+ (n−1) + (n−2) +...+ 1 =
n
On en d´eduit que la complexit´e est enO(n
2
).
c)
La classification des algorithmes de tri est tr`es importante, car elle permet de choisir
l’algorithme le plus adapt´e au probl`eme trait´e, tout en tenant compte des contraintes
impos´ees par celui-ci. Les principales caract´eristiques qui permettent de diff´erencier
les algorithmes de tri, outre leur principe de fonctionnement, sont la complexit´e tem-
porelle, la complexit´e spatiale et le caract`ere stable.
Un tri est ditstables’il pr´eserve l’ordonnancement initial des ´el´ements
que l’ordre consid`ere comme ´egaux. Pour d´efinir cette notion, il est
n´ecessaire que la collection `a trier soit ordonnanc´ee d’une certaine
mani`ere (ce qui est souvent le cas pour beaucoup de structures de
donn´ees, par exemple pour les listes ou les tableaux).
D´efinition :
L’int´erˆet d’un tri stable est qu’on peut appliquer ce tri successivement, avec des
crit`eres diff´erents. Imaginez, par exemple, que dans le cadre d’une campagne de
pr´evention, vous vouliez trier une liste de personnes en fonction de la cat´egorie d’ˆage.
Vous obtenez une liste avec les personnes les plus ˆag´ees en premier. Si maintenant, vous
voulez re-trier cette liste en fonction du poids, par exemple, vous aurez, si l’algorithme
de tri est stable, les personnes les plus lourdes en premier et, pour les personnes de
mˆeme poids, celles qui sont les plus ˆag´ees en premier. Ce qu’un algorithme non-stable
ne garantirait pas.
MONTRER LA STABILITE AU TABLEAU AVEC DEUX ELEMENTS IDEN-
TIQUES DE COULEUR DIFFERENTES
JB, NG, SR

3. II TRI PAR INSERTION
II.
1 -
Soit une liste L de n ´el´ements. Le tri par insertion consiste `a ins´erer `a
la i`eme it´eration le i`eme ´el´ement `a la bonne place par ordre croissant.
D´efinition :
Figure 2: Illustration du tri par insertion
Dans l’algorithme, on parcourt le tableau `a trier du d´ebut `a la fin. Au moment o`u
on consid`ere le i-`eme ´el´ement, les ´el´ements qui le pr´ec`edent sont d´ej`a tri´es. Pour faire
l’analogie avec l’exemple du jeu de cartes, lorsqu’on est `a la i-`eme ´etape du parcours,
le i-`eme ´el´ement est la carte saisie, les ´el´ements pr´ec´edents sont la main tri´ee et les
´el´ements suivants correspondent aux cartes encore m´elang´ees sur la table. L’objectif
d’une ´etape est d’ins´erer le i-`eme ´el´ement `a sa place parmi ceux qui pr´ec`edent. Il faut
pour cela trouver o`u l’´el´ement doit ˆetre ins´er´e en le comparant aux autres, puis d´ecaler
les ´el´ements afin de pouvoir effectuer l’insertion.
1Pour i variant de 2 a n faire :
2 inserer L [ i ] a sa place dans [ L [1] ,... , L [i -1]]
3Fin pour
´
Ecrire les ´etapes de l’ex´ecution du tri par insertion de L=[9,6,1,4,8]. On
noteraLtrila liste tri´ee.
Exemple 3 :
On obtient alors les ´etapes suivantes :
•Ltri= [9]
•Ltri= [6,9]
•Ltri= [1,6,9]
•Ltri= [1,4,6,9]
•Ltri= [1,4,6,8,9]
2 -
a)
L’id´ee est de trier progressivement le tableau :
•supposons quet[0 : k]est d´ej`a tri´e,
•j’ins`eret[k]`a sa placeiparmi les valeurs det[0 : k]
•on d´ecale les plus grandes valeurs d’un cran vers la droite au besoin
de sorte quet[0 : k + 1]se retrouve tri´e.
Le principe de modularit´e pourrait nous conduire `a ´ecrire une fonction qui d´etermine
la place det[k], puis une deuxi`eme fonction qui se charge de l’insertion.
b) ´el´ement
Le tri par insertion n´ecessite de connaˆıtre la position d’un ´el´ement dans une liste tri´ee.
JB, NG, SR

4. II TRI PAR INSERTION
SoitLtriune liste tri´ee d’´el´ements num´eriques. D´efinir une fonction
position(x,Ltri)ayant pour valeur de retour la positionktelle que :
•k = 0six<Ltri[0]
•k = len(Ltri)six>Ltri[-1]
•Ltri[k-1]≤x<Ltri[k]
Exemple 4 :
On peut proposer le code suivant :
1defposition (x , Ltri ) :
2 forkinrange(len( Ltri )):
3 ifx < Ltri [ k ]:
4 returnk
5 returnlen( Ltri )
c)
SoitLune liste d’´el´ements num´eriques non tri´es. D´efinir une fonction
triinsertion(L) qui renvoie une liste tri´ee. On pourra utiliser la m´ethode
.insert(i,x)qui ins`ere l’´el´ementx`a la positioni.
Exemple 5 :
On peut proposer
1deftri_insertion ( L ):
2 Ltri = [ L [0] ]
3 forkinrange(1 ,len( L )):
4 x = L [ k ]
5 Ltri . insert ( position (x , Ltri ) , x )
6 returnLtri
3 -
a)
On obtient un code plus compact en d´ecalant les valeurs au fur et `a mesure de la
recherche de la place det[k]. Plus pr´ecis´ement, pour k allant de 1 `a n - 1 :
•on stocke la valeur det[k]dans une variable temporairetempet la position
d’insertionjest initialis´ee `a la valeurk
•tant que j ¿ 0 ettemp < t[j - 1]
–on d´ecalet[j - 1]d’un cran vers la droite
–on d´ecr´ementej
•`a la sortie de la boucle on ins`eretemp`a sa place.
1deftri_ins ( t ):
2 forkinrange(1 ,len( t )):
3 temp = t [ k ]
4 j = k
5 whilej >0andtemp < t [j -1]:
6 t [ j ]= t [j -1]
7 j -=1
8 t [ j ]= temp
b) ´e
Le pire des cas correspond `a une liste tri´ee par ordre d´ecroissant. La pr´esence de deux
boucles for imbriqu´ees : l’une dansT riInsertionl’autre danspositionconduisent `a
une complexit´e enO(n
2
).
On peut avantageusement utiliser ladichotomie. Une am´elioration pour obtenir la
position d’un ´el´ement dans une liste d´eja tri´ee est d’effectuer des tests de comparaison
par dichotomie comme repr´esent´e sur la figure ci-dessous. Le nombre de test pour
parvenir `a la bonne place est alors beaucoup plus petit. Pour une liste de tailleN= 2
p
,
le nombre d’it´eration estpdans le pire des cas et nonN.
Figure 3: Illustration de la recherche dichotomique
JB, NG, SR

5. III TRI RAPIDE
En utilisant la recherche dichotomique, la complexit´e du tri est nette-
ment meilleur. Elle passe deO(n
2
) `aO(nlnn). En effet, on effectuenin-
sertion, et pour chaque insertion, on effectue une recherche dichotomique
dont la complexit´e est enO(lnn).
Propri´et´e :
Il faut cependant faire attention aux bords. Si l’´el´ement `a placer est en dehors de
l’intervalle, il faut pouvoir renvoyer 0 ou la taille de la liste. On obtient alors :
1defposition_dich (x , Ltri ) :
2 N =len( Ltri )
3 a , b = 0 ,N -1
4 ifx > Ltri [ -1] :returnN
5 elifx < Ltri [0] :return0
6 while(b - a ) >1:
7 m = ( b + a )//2
8 ifx > Ltri [ m ] :
9 a = m
10 else: b = m
11 returnb
Pour fixer les id´ees, supposons qu’une op´eration ´el´ementaire dure 1µs, un tri pour
une liste contenantN= 10
5
´el´ements dure :
•(10
5
)
2
×10
−6
= 10
4
s≈3h
•10
5
×log(N)×10
−6
≈1s
c) ´e
Avec une recherche dichotomique, la perte du parcours syst´ematique par ordre croissant
pour trouver le minimum conduit `a une instabilit´e. L’ordre de deux valeurs identiques
peut ˆetre ´echang´e.
III.
1 -
Le tri rapide - aussi appel´e ”tri de Hoare” (du nom de son inventeur Tony Hoare) ou ”tri
par segmentation” ou ”tri des bijoutiers” ou, en anglais ”quicksort” - est certainement
l’algorithme de tri interne le plus efficace.
Le principe de ce tri est d’ordonner le tableau en cherchant dans celui-ci une cl´e pivot
autour de laquelle r´eorganiser ses ´el´ements. Il est souhaitable que le pivot soit aussi
proche que possible de la cl´e relative `a l’enregistrement central du vecteur, afin qu’il y
ait `a peu pr`es autant d’´el´ements le pr´ec´edant que le suivant, soit environ la moiti´e des
´el´ements du tableau. On applique ensuite le tri r´ecursivement `a, sur la partie dont les
´el´ements sont inf´erieurs au pivot et sur la partie dont les ´el´ements sont sup´erieurs au
pivot.
Figure 4: Illustration du tri rapide
JB, NG, SR

6. III TRI RAPIDE
1deftri_rapide ( L ):
2 iflen( L )==1:
3 returnL
4 eliflen( L )==0:
5 return[]
6 pivot = L [0]
7 plus_petit = []
8 plus_grand = []
9 forkinrange(1 ,len( L )) :
10 ifx < pivot :
11 plus_petit . append ( L [ k ])
12 else:
13 plus_grand . append ( L [ k ])
14 returntri_rapide ( plus_petit ) + [ pivot ] + tri_rapide ( plus_grand )
Le tri propos´e ici n’est pas en place ´etant donn´e qu’une nouvelle liste est g´en´er´ee.
2 -
L’algorithme est r´ecursif et fait deux appels r´ecursifs. Il faut donc ´etudier la taille
des donn´ees lors de ces appels. SoitNla taille du tableau, lors du premier appel, on
effectue une boucle for soitNop´eration et en supposant que le tableau est scind´e en
deux parties ´equivalentes de taille⌊N/2⌋(en moyenne) , la complexit´e v´erifie :
C(N) =N+ 2×C(⌊N/2⌋)
PosonsN= 2
n
, notonsun=C(2
n
), la relation pr´ec´edente s’´ecrit :
un= 2
n
+ 2un−1
Par r´ecurrence triviale :
un=n×2
n
+ 2u0
Commen= lnN/ln 2, on obtient :
C(N) = Θ(NlnN)
Dans le pire des cas, c’est `a dire si, `a chaque niveau de la r´ecursivit´e le d´ecoupage
conduit `a trier un sous-tableau de 1’´element et un sous-tableau contenant tout le reste,
la complexit´e du tri rapide est en Θ(n
2
).
Figure 5: Tri fusion pour 7 ´el´ements
JB, NG, SR

7. IV TRI FUSION
IV.
1 -
L’algorithme est naturellement d´ecrit de fa¸con r´ecursive.
•Si le tableau n’a qu’un ´el´ement, il est d´ej`a tri´e.
•Sinon, on s´epare le tableau en deux parties (`a peu pr`es ´egales).
•On trie r´ecursivement les deux parties avec l’algorithme du tri fusion.
•On fusionne les deux tableaux tri´es en un tableau tri´e.
2 -
a) ´ees
Impl´ementer une fonctionfusion(L1,L2) de param`etresL1 etL2, deux listes
tri´es, qui renvoie une listeL3 tri´ee `a partir des ´el´ements deL1 etL2. On
supposera que les listes sont non-vides.
Exemple 6 :
Solution 1On attend le code suivant :
1deffusion ( L1 , L2 ):
2 L3 = []
3 i , j = 0 ,0
4 whilei <len( L1 )andj <len( L2 ):
5 ifL1 [ i ] < L2 [ j ]:
6 L3 . append ( L1 [ i ])
7 i +=1
8 else:
9 L3 . append ( L2 [ j ])
10 j +=1
11 ifi ==len( L1 ):
12 L3 += L2 [ j :]
13 else:
14 L3 += L1 [ i :]
15 returnL3
b) ´ees
`
A l’aide de la fonction pr´ec´edente, ´ecrire une fonctionTrifusion(L), qui
effectue le tri de la listeLselon la m´ethode cit´ee plus haut.
Exemple 7 :
L’algorithme de tri-fusion de mani`ere r´ecursive s’´ecrit alors :
1defTrifusion ( L ):
2 N =len( L )//2
3 iflen( L )==1 :
4 returnL
5 else:
6 returnfusion ( Trifusion ( L [0: N ]) , Trifusion ( L [ N :len( L )]) )
3 -
Notonsnle nombre d’´el´ements de la liste `a trier, etT(n) le nombre d’op´erations
utilis´ees dans le tri fusion. Pourn≥2, la relation de r´ecurrence sur la complexit´e est :
T(n) =T(⌊
n
2
⌋) +T(⌊
n
2
⌋) +n+c
o`ucest une constante, etnrepr´esente le coˆut de la fusion de deux listes contenant
au totaln´el´ements.
Pour simplifier, supposonsn= 2
p
, montrer alors que :
T(n) =nT(1) +
lnn
ln 2
×n+ (n−1)×c=O(nlnn)Exemple 8 :
R´e´ecrivons la relation de r´ecurrence pournpair
T(n) = 2T(
n
2
) +n+c soit T(2
p
) = 2T(2
p−1
) + 2
p
+c
De mˆeme :
T(2
p−1
) = 2T(2
p−2
) + 2
p−1
+c
d’o`u :
JB, NG, SR

8. IV TRI FUSION
T(2
p
) = 2×
Γ
2T(2
p−2
) + 2
p−1
+c
∆
+ 2
p
+c
On en d´eduit que :
T(2
p
) = 2
p
T(1) +p×2
p
+ (1 +..+ 2
p−1
)×c
(1 +..+ 2
p−1
) correspond `a la somme des termes d’une suite g´eom´etrique de raison
2. On a alors:
(1 +..+ 2
p−1
) =
2
p
−1
2−1
=n−1
De plus ,p= lnn/ln 2, on en d´eduit que
T(n) =nT(1) +
lnn
ln 2
×n+ (n−1)×c=O(nlnn)
JB, NG, SR