Algorithmes de tri - pageperso.lif.univ-mrs.frpageperso.lif.univ-mrs.fr/~francois.denis/algoL2/chap3.pdf · Chapitre 3 Algorithmes de tri Trier un ensemble d’objets consiste a les

Chapitre 3

Algorithmes de tri

Trier un ensemble d’objets consiste a les ordonner en fonction d’une relationd’ordre definie sur ces objets. Souvent, les objets sont indexes par une cle etla relation d’ordre porte sur cette cle. Par exemple, chaque etudiant inscrita l’universite d’Aix-Marseille recoit un numero qui constitue la cle d’acces ason dossier. On trie des objets lorsqu’ils sont nombreux et qu’on doit pouvoiry acceder rapidement : rechercher un element dans un tableau non trie estune operation de complexite lineaire dans le nombre d’objets, alors que si letableau est trie, la recherche peut etre e↵ectuee en temps logarithmique.

On dit qu’un algorithme de tri est

— en place, s’il n’utilise qu’un espace memoire de taille constante pen-dant son execution, (en plus de l’espace servant a stocker les objetsa trier)

— par comparaison, si le tri s’e↵ectue en comparant les objets entreeux. Lorsque les valeurs prises par ces objets sont peu nombreuses(par exemple, les annees de naissance), il peut etre plus e�cace decomparer chaque objet aux valeurs possibles.

— stable s’il preserve l’ordre d’apparition des objets en cas d’egalite descles. Cette propriete est utile par exemple lorsqu’on trie successive-ment sur plusieurs cles di↵erentes. Si l’on veut ordonner les etudiantspar rapport a leur nom puis a leur moyenne generale, on veut que lesetudiants qui ont la meme moyenne apparaissent dans l’ordre lexico-graphique de leurs noms.

Dans ce chapitre, nous etudions

— des tris simples, tri a bulle, tri par insertion, tri par selection, decomplexite O(n2) en moyenne,

— des tris plus sophistiques, tris par fusion, tri par tas et tri rapide, de

39

40 CHAPITRE 3. ALGORITHMES DE TRI

complexite O(n log n) en moyenne— et quelques tris particuliers, parfois tres e�caces mais pas toujours

applicables, tri par denombrement et tri par base.Des travaux pratiques permettront d’etudier experimentalement et de

comparer la complexite de ces algorithmes.En general les objets a trier sont stockes dans des tableaux, mais ce n’est

pas toujours le cas. Lorsque les objets sont stockes dans des listes chainees,on peut soit les recopier au prealable dans un tableau temporaire, soit utiliserun tri adapte comme le tri par fusion.

3.1 Tri par selection, tri par insertion, tri a bulle.

Le tri par selection consiste simplement a selectionner l’element le pluspetit de la suite a trier, a l’enlever, et a repeter iterativement le processustant qu’il reste des elements dans la suite. Au fur et a mesure les elementsenleves sont stockes dans une pile. Lorsque la suite a trier est stockee dansun tableau on s’arrange pour representer la pile dans le meme tableau quela suite : la pile est representee au debut du tableau, et chaque fois qu’unelement est enleve de la suite il est remplace par le premier element quiapparaıt a la suite de la pile, et prends sa place. Lorsque le processus s’arretela pile contient tous les elements de la suite tries dans l’ordre croissant. Letri par selection est en ⇥(n2) dans tous les cas.

Algorithme 12: TriParSelection

entree : T [1, n] est un tableau d’entiers, n � 1.resultat : les elements de T sont ordonnes par ordre croissant.debut

pour i := 1 a n� 1 fairej := IndMin(T [i, n]) # indice du plus petit element de T [i, n]permuter T [i] et T [j]

Exercice 1 Quel est l’invariant du tri par selection ? La complexite del’algorithme depend-elle des donnees d’entree ? Pourquoi la complexite est-elle quadratique dans tous les cas ?

Le tri par insertion consiste a inserer les elements de la suite les unsapres les autres dans une suite triee initialement vide. Lorsque la suite eststockee dans un tableau la suite triee en construction est stockee au debut

3.1. TRI PAR SELECTION, TRI PAR INSERTION, TRI A BULLE. 41

du tableau. Lorsque la suite est representee par une liste chainee on insereles maillons les uns apres les autres dans une nouvelle liste initialement vide.

Algorithme 13: TriParInsertion<


pour i := 2 a n fairej := i # indice de l’element a inserer dans T [1, i� 1]v := T [i] # valeur de l’element a inserertant que j > 1 et v < T [j � 1] faire

T [j] := T [j � 1] # j � 1 est une case librej := j � 1 # j est une case libre

T [j] := v

Le tri e↵ectue n � 1 insertions. A la ieme iteration, dans le pire des cas,l’algorithme e↵ectue i� 1 recopies. Le cout du tri est donc

nX

i=2

(i� 1) =n(n� 1)

2= O(n2).

Dans le meilleur des cas le tri par insertion requiert seulement O(n) traite-ments. C’est le cas lorsque l’element a inserer reste a sa place, donc quand lasuite est deja triee.On peut montrer que le tri par insertion est quadratiqueen moyenne.

Exercice 2 (di�cile) On considere toutes les permutations de l’ensembleSn

= {1, . . . , n}. On veut montrer que le tri par insertion sera quadratiqueen moyenne sur l’ensemble de ces permutations.

1. Soit T une permutation de Sn

et soient 1 i < j n. On definitIi,j

(T ) = 1 si T [i] > T [j] et Ii,j

(T ) = 0 sinon, et I(T ) =P

i<j

Ii,j

(T )(nombre d’inversions dans T ). Montrez que I(T ) est exactement egalau nombre de fois que l’instruction T [j] := T [j � 1] est executee parl’algorithme de tri par insertion.

2. On choisit une permutation T de Sn

au hasard, toutes les permuta-tions ayant la meme probabilite. Soit i < j. I

i,j

(T ) est une variablealeatoire. Montrez que son esperance est egale a E(I

i,j

(T )) = 1/2.Montrez que E(I(T )) = n(n� 1)/4.

3. Comparez la complexite en moyenne et la complexite dans le pire descas. Montrez que la complexite en moyenne est en ⇥(n2).


Le tri a bulle consiste a parcourir le tableau, tant qu’il n’est pas trie,et a permuter les couples d’elements consecutifs mal ordonnes. On sait quele tableau est trie si lors d’un parcours, aucun couple d’elements n’a etepermute.

Algorithme 14: TriBulle


M := n� 1tant que le tableau n’est peut-etre pas trie faire

pour i := 1 a M fairesi T [i] > T [i+ 1] alors

permuter T [i] et T [i+ 1]

M = M � 1

Exercice 3 Dans l’algorithme du tri a bulle,

1. montrez qu’apres k parcours du tableau (boucle interne), au moins kelements sont a leur place,

2. deduisez-en que la complexite dans le pire des cas est en ⇥(n2),

3. montrez qu’apres chaque parcours, le plus petit element du tableaureste a sa place ou recule au plus d’une case,

4. deduisez-en que la complexite moyenne est en ⇥(n2) (pour tout entier1 i n, avec une probabilite 1/n, l’element minimal du tableauest situe a l’indice i),

5. montrez que dans le meilleur des cas, l’algorithme est lineaire,

6. montrez que le tri est stable et identifiez precisement la raison decette propriete.

3.2 Tri par fusion et tri rapide

3.2.1 Tri par fusion (ou par interclassement)

Le tri par fusion (merge sort en anglais) implemente une approche detype diviser pour regner tres simple : la suite a trier est tout d’abord scindeeen deux suites de longueurs egales a un element pres. Ces deux suite sont

3.2. TRI PAR FUSION ET TRI RAPIDE 43

ensuite triees separement avant d’etre fusionnees (ou interclassees). L’e�ca-cite de ce tri vient de l’e�cacite de la fusion : le principe consiste a parcourirsimultanement les deux suites triees dans l’ordre croissant de leur elements,en extrayant chaque fois l’element le plus petit. La fusion peut-etre e↵ec-tuee en conservant l’ordre des elements de meme valeur (le tri par fusion eststable)

Le tri par fusion est bien adapte aux listes chainees : pour scinder la listeil su�t de la parcourir en liant les elements de rangs pairs d’un cote et leselements de rangs impairs de l’autre. La fusion de deux listes chainees se faitfacilement. Inversement, si la suite a trier est stockee dans un tableau il estnecessaire de faire appel a un tableau annexe lors de la fusion, (au moinsdans ses implementations les plus courantes).

Algorithme 15: TriParFusion

entree : T [m,n] est un tableau d’entiers, m n.resultat : les elements de T sont ordonnes par ordre croissant.debut

si m < n alorsTriFusion(T [m, bm+n

2

c])TriFusion(T [bm+n

2

c+ 1, n])Interclassement(T[m, n])

La complexite de l’interclassement est O(n) dans tous les cas. La com-plexite du tri par fusion verifie donc l’equation recursive suivante :

T (n) = 2⇥ T (n/2) +O(n).

On en deduit que le tri par fusion est en O(n log n).

On le verifie en cumulant les nombres de comparaisons e↵ectuees achaque niveau de l’arbre qui represente l’execution de la fonction (voir figureci-dessous) : chaque nœud correspond a un appel de la fonction, ses fils cor-respondent aux deux appels recursifs, et son etiquette indique la longueurde la suite. La hauteur de l’arbre est donc log

2

n et a chaque niveau le cumuldes traitements locaux (scission et fusion) est O(n), d’ou on deduit un couttotal de O(n)⇥ log

2

n = O(n log n).


Algorithme 16: Interclassement

entree : T [m,n] est un tableau d’entiers, m n, T [m, bm+n

2

c] etT [bm+n

2

c+ 1, n] sont tries par ordre croissant.resultat : les elements de T sont ordonnes par ordre croissant.debut

i := m, j := bm+n

2

c+ 1, k := mtant que i bm+n

2

c ET j n fairesi T [i] T [j] alors

S[k] := T [i], i := i+ 1sinon

S[k] := T [j], j := j + 1k := k + 1

# un des deux tableaux est videtant que i bm+n

2

c faireS[k] := T [i], i := i+ 1, k := k + 1# recopie de la fin du premier tableau ; la fin du second est enplace

pour i := m a k � 1 faireT [i] := S[i] # recopie de S dans T

n

2x

n2x

n2x

n

n/2 n/2

n/4n/4n/4n/4

n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8

1 1 1 ....

log

n

Exercice 4

1. Qu’est-ce qui, dans l’algorithme d’interclassement, garantit la stabi-lite du tri fusion ?

2. Ecrivez l’algorithme de fusion lorsque les donnees sont stockees dansune liste chaınee.

3.2. TRI PAR FUSION ET TRI RAPIDE 45

3.2.2 Tri rapide

Le tri rapide (quicksort) est une methode de type diviser pour regner quiconsiste, pour trier un tableau T , a le partitionner en deux sous-tableaux T

1

et T2

contenant respectivement les plus petits et les plus grands elements deT , puis a appliquer recursivement l’algorithme sur les tableaux T

1

et T2

.

Il existe plusieurs methodes pour partitionner un tableau. Le principegeneral consiste a utiliser un element particulier, le pivot, comme valeur departage.

Dans l’algorithme qui suit, le pivot est le premier element du tableau.On peut egalement choisir aleatoirement un element quelconque du tableau(voir TD).

L’algorithme partition prend en entree un tableau T [m,n] (avec m n) et reordonne T de facon a

— mettre en debut de tableau les elements T [i] de T [m+ 1, n] tels queT [i] T [m],

— mettre en fin de tableau les elements T [i] de T [m + 1, n] tels queT [i] > T [m],

— placer T [m] entre les deux.

Il retourne l’indice de T [m] dans le nouveau tableau : T [m] s’appelle le pivot.

Algorithme 17: partition

entree : T [m,n] est un tableau d’entiers.sortie : l’indice du pivot dans le tableau rearrangedebut

pivot := T [m]i := m+ 1 # indice ou inserer le premier element T [m]pour j := m+ 1 a n faire

# j est l’indice de l’element courantsi T [j] pivot alors

permuter T [i] et T [j]i := i+ 1

permuter T [m] et T [i� 1]retourner i� 1

Le QuickSort consiste a partitionner un tableau T [m,n] autour du pivotT [m] puis a trier recursivement chacune des deux parties T [m, IndPivot�1]et T [IndPivot+ 1, n] a l’aide du QuickSort.


Algorithme 18: QuickSort

entree : T [m,n] est un tableau d’entiers.sortie : T est trie par ordre croissantdebut

si m < n alorsIndPivot = partition(T [m,n])QuickSort(T[m, IndPivot� 1])QuickSort(T[IndPivot + 1, n])

On peut montrer que la complexite du tri rapide estO(n log n) en moyenne,mais aussi O(n2) dans le pire des cas (voir une etude de la complexite enTD). En pratique, c’est l’algorithme le plus utilise et tres souvent, le plusrapide.

3.3 Complexite optimale d’un algorithme de tri

par comparaison

L’arbre de decision d’un tri par comparaison represente le comporte-ment du tri dans toutes les configurations possibles. Les configurations cor-respondent a toutes les permutations des objets a trier, en supposant qu’ilssoient tous comparables et de cles di↵erentes. S’il y a n objets a trier, ily a donc n! configurations possibles. On retrouve toutes ces configurationssur les feuilles de l’arbre, puisque deux permutations initiales distinctes nepeuvent pas produire le meme comportement du tri : en e↵et, dans ce cas letri n’aurait pas fait son travail sur un des deux ordonnancements. Chaquenœud de l’arbre correspond a une comparaison entre deux elements et adeux fils, correspondants aux deux ordres possibles entre ces deux elements.

3.3. COMPLEXITE OPTIMALE D’UN ALGORITHMEDE TRI PAR COMPARAISON47

cba

cba

cb a

b c acb a

b c a bc ac a ba c b

a c b

cba

e1 > e2e1 <= e2

e2 > e3e2 <= e3

321

<= >

<= > <=

><=

>

><=

Sur la figure ci-dessus nous avons represente l’arbre de decision du tripar insertion sur une suite de trois elements. A la racine de l’arbre le tricompare tout d’abord les deux premiers elements de la suite a et b, afind’inserer l’element b dans la suite triee constituee uniquement de l’elementa. Suivant leur ordre les deux elements sont permutes (fils droit) ou laissesen place (fils gauche). Au niveau suivant l’algorithme compare les elementsde rang 2 et de rang 3 afin d’inserer l’element de rang 3 dans la suite trieeconstituee des 2 premiers elements, et ainsi de suite. Les branches de l’arbrede decision du tri par insertion n’ont pas toutes la meme longueur du fait quedans certains cas l’insertion d’un element est moins couteuse, en particulierquand l’element est deja a sa place.

Les feuilles de l’arbre representent toutes les permutations du tableauen entree. Puisque le nombre de permutations de n elements est n!, l’arbrede decision d’un tri a donc n! feuilles. On peut montrer facilement, parrecurrence sur h, que le nombre de feuilles n

f

d’un arbre binaire de hauteurh, verifie n

f

2h. On en deduit que la hauteur h de l’arbre de decisionverifie

h � log(n!)

or, d’apres la formule de Stirling 1

log(n!) ⇠ logp2⇡n+ log

⇣ne

⌘n

= ⇥(nlog n)

1. sans utiliser la formule de Stirling, on peut remarquer que (n2

)n2 n! nn, ce qui

conduit directement a log(n!) = ⇥(n log n).


et donc la hauteur minimale de l’arbre est en ⌦(nlog n).Comme la hauteur de l’arbre est aussi la longueur de sa plus longue

branche, on en conclut qu’aucun tri par comparaison ne peut avoir unecomplexite dans le pire des cas inferieure a O(n⇥ log n).

3.4 Tri par tas.

Un tas (heap en anglais) est un arbre binaire etiquete presque complet : tousses niveaux sont remplis sauf peut-etre le dernier, qui est rempli a partir dela gauche jusqu’a un certain nœud. Cette disposition entraıne que l’arbreest forcement presque completement equilibre (i.e. toutes ses branches ontla meme longueur a un element pres), et les plus longues branches sonta gauche. La hauteur d’un tas contenant n elements, i.e. son nombre deniveaux, est donc blog

2

nc+1 (le nombre de fois que l’on peut diviser n par2 avant d’obtenir 1).

2hauteur log n

7

15

11

3

84 2

7

13

10

0

2

3

1

4 5 6

98

Habituellement les tas sont representes dans des tableaux. Les valeurs dutas sont stockees dans les premieres cases du tableau. Si le tas est composede n elements, ces derniers apparaissent donc aux indices 0, 1,. . . , n � 1.La racine du tas figure dans la case d’indice 0. La disposition des elementsdu tas dans le tableau correspond a un parcours de l’arbre par niveau, enpartant de la racine et de gauche a droite. Le fils gauche du nœud qui figurea l’indice i, s’il existe, se trouve a l’indice FilsG(i) = 2 ⇥ i + 1, et son fils

3.4. TRI PAR TAS. 49

droit, s’il existe, se trouve a l’indice FilsD(i) = 2 ⇥ i + 2. Inversement, lepere du nœud d’indice i non nul se trouve a l’indice b i�1

2

c.

n−1

5 1 4 8 2 0 5

21 3 4 5 7 8 9 10 110

6

fils droit

fils gauche

31071113

Si le dernier nœud du tas se trouve a la position n�1, son pere se trouvea la position bn

2

�1c. C’est le dernier nœud qui a au moins un fils. Les feuillesde l’arbre se trouvent donc entre la position bn

2

c et la position n� 1 dans letableau puisqu’il n’y a pas de feuilles avant le dernier pere.

On definit ensuite une propriete sur les tas : chaque nœud est dans unerelation d’ordre fixee avec ses fils.

Un tas possede la propriete max-heap (resp. min-heap) si tout nœudporte une valeur superieure ou egale (resp. inferieure ou egale) a celle de sesfils : T [pere(i)] � T [i] (resp. T [pere(i)] T [i]). Un tax-max (resp. tas-min)est un tas qui verifie la propriete max-heap (resp. min-heap).

Le plus grand element d’un tas-max T est T [0] ; son plus petit elementest sur une feuille.

Pour le tri par tas on utilise des tas-max. Les operations et les techniquespresentees dans ce chapitre s’appliquent de la meme facon a des tas basessur l’ordre inverse. Les operations essentielles sur les tas sont :

— la construction du tas,— l’extraction du maximum,— l’ajout d’une nouvelle valeur,— la modification de la valeur d’un nœud.

L’operation Entasser est une operation de base sur les tas. Elle est utiliseenotamment pour la construction des tas ou encore pour l’extraction de lavaleur maximale. Elle consiste a reconstruire le tas lorsque seule la racineviole (eventuellement) la propriete de superiorite entre un nœud et ses fils,en faisant descendre dans l’arbre l’element fautif par des echanges successifs.


14

1

284

1

284

9

7

510

14

13 1

284

7

5

9

10 13

7

5

13

910

14

Fonction Entasser(i,T ,n)

entree : T est un tas ; le fils gauche et le fils droit du noeud d’indice iverifient la propriete Max-heap ; ce n’est pas forcement lecas du noeud d’indice i.

sortie : La propriete max-heap est verifiee par le noeud d’indice i.debut

iMax isi (FilsG(i) < n) ET (T [FilsG(i)] > T [iMax]) alors

iMax := FilsG(i)

si (FilsD(i) < n) ET (T [FilsD(i)] > T [iMax]) alorsiMax := FilsD(i)

si (iMax 6= i) alorsEchanger T [i] et T [iMax]Entasser(iMax,T ,n)

— la condition (FilsG(i) < n) signifie que le fils gauche du nøeud iexiste ;

— si le nœud i est une feuille ou si T [i] est superieure aux valeurs porteespar ses fils, l’algorithme ne fait rien ;

— si le nœud i a des fils qui portent des valeurs superieures a T [i], lafonction echange cette valeur avec la plus grande des valeurs de sesfils et e↵ectue un appel recursif sur le fils qui porte la valeur T [i].

La fonction Entasser a un cout en O(log2

n) puisque, dans le pire descas, il faudra parcourir une branche entierement.

Extraction de la valeur maximale. La valeur maximale d’un tas quiverifie la propriete Max-heap est a la racine de l’arbre. Pour un tas de taillen stocke dans le tableau T c’est la valeur T [0] si n est non nul. L’extractionde la valeur maximale consiste a recopier en T [0] la derniere valeur du tas

3.4. TRI PAR TAS. 51

T [n�1], a decrementer la taille du tas, puis a appliquer l’operation Entassera la racine du tas, afin que la nouvelle valeur de la racine prenne sa place.

Fonction ExtraireLeMax(T, n)

entree : T est un tableau, n est la taille du tas stocke dans T .sortie : Retourne la valeur maximale et met a jour le tas.debut

max := T [0]T [0] := T [n� 1]Entasser(0, T, n� 1)retourner hmax, T, n� 1i

fin

Exercice 5 Ecrivez les algorithmes

1. InsertVal(T, n, v) qui insere une valeur v dans un tasmax T de nelements (on suppose que l’on peut acceder a T [n])

2. SupprimeNoeud(T, n, i) qui supprime le nœud i dans le tasmax Tde n elements.

Dans les deux cas, le tas resultant et un tasmax.

Principe general du tri par tas. Supposons que l’on ait a trier unesuite de n valeurs stockee dans un tableau T . On commence par construireun tas dans T avec les valeurs de la suite. Ensuite, tant que le tas n’est pasvide on repete l’extraction de la valeur maximale du tas. Chaque fois, lavaleur extraite est stockee dans le tableau immediatement apres les valeursdu tas. Lorsque le processus se termine on a donc la suite des valeurs trieedans le tableau T .

Construction du tas.

Les valeurs de la suite a trier sont stockees dans le tableau T . La proce-dure consiste a parcourir les noeuds qui ont des fils et a leur appliquer l’ope-ration Entasser, en commencant par les noeuds qui sont a la plus grandeprofondeur dans l’arbre. Il su�t donc de parcourir les noeuds dans l’ordredecroissant des indices et en partant du dernier noeud qui a des fils, le noeudd’indice b(n/2)c�1. L’ordre dans lequel les noeuds sont traites garantit queles sous-arbres sont des tas.


Fonction ConstruireUnTas(T, n)

entree : T est un tableau, n est un entier.sortie : Structure les n premiers elements de T sous forme de tas.debut

pour i := bn/2� 1c a 0 faireEntasser(i, T, n)

finpourretourner T

fin

Invariant : tous les nœuds de T d’indice > i verifient la propriete max-heap.Complexite de la construction. De facon evidente la complexite est auplus O(n log n). En e↵et la hauteur du tas est log n et on e↵ectue n/2 foisl’operation Entasser. En fait le cout de la construction est O(n). En e↵et, lafonction e↵ectue un grand nombre d’entassements sur des arbres de petiteshauteur (pour les noeuds les plus profonds), et tres peu d’entassements surla hauteur du tas.

Soit h la hauteur du tas construit T . Il a 1 noeud de hauteur h, auplus 2 noeuds de hauteur h � 1, . . . , et au plus 2h�1 noeuds de hauteur 1.Soit K une constante telle que la complexite de Entasser(i, T, n) soit Kh

i

, ou hi

est la hauteur du sous-arbre de racine i. La complexite C(n)de l’algorithme ConstruitTas verifie donc :

C(n) K(h+2(h�1)+4(h�2)+ · · ·+2h�1) K2h(h

2h+

h� 1

2h�1

+ · · ·+ 1

2).

La serieP1

k=0

k

2

k converge vers 2. En e↵et,

S =1X

k=0

k

2k=

1X

k=1

k � 1 + 1

2k=

1

2

1X

k=1

k � 1

2k�1

+1X

k=1

1

2k=

S

2+ 1.

Comme 2h n, on en deduit que C(n) 2Kn. L’algorithme ConstruitTasMaxest lineaire dans le pire des cas. Cette complexite est atteinte si T est stric-tement croissant.Exercice 6 Construisez un tas a partir de T = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

Exercice 7 Si l’on utilise l’algorithme InsertVal pour construire un tas-max de n elements, quel est la complexite de l’algorithme ?

3.5. TRI PAR DENOMBREMENT, TRI PAR BASE. 53

Tri par tas.

On construit un tas. On utilise le fait que le premier element du tas est leplus grand : autant de fois qu’il y a d’elements, on extrait le premier du tas eton reconstruit le tas avec les elements restants. Enlever le premier elementconsiste simplement a l’echanger avec le dernier du tas et a decrementerla taille du tas. On retablit la propriete de tas en appliquant l’operationEntasser sur ce premier element.

Fonction TriParTas(T, n)

entree : T est un tableau de n elements.sortie : Trie le tableau T par ordre croissant.debut

ConstruireUnTas(T, n)pour i := n� 1 a 1 faire

Echanger(T, 0, i)Entasser(0, T, i)

retourner T

La construction du tas coute O(n). On e↵ectue ensuite n fois un echange etl’operation Entasser sur un tas de hauteur au plus log n. La complexite dutri par tas est donc O(n log n).

3.5 Tri par denombrement, tri par base.

3.5.1 Tri par denombrement

Le tri par denombrement (counting sort) est un tri sans comparaisonsqui est stable, c’est-a-dire qu’il respecte l’ordre d’apparition des elementsdont les cles sont egales. Le tri par denombrement commence par recenserles elements pour chaque valeur possible des cles. Ce comptage preliminairepermet de connaıtre, pour chaque cle c, la position finale du premier elementde cle c qui apparaıt dans la suite a trier. Sur l’exemple ci-dessous on arecense dans le tableau T , 3 elements avec la cle 1, 4 elements avec la cle 2et 3 elements avec la cle 3. On en deduit que le premier element avec la cle1 devra etre place a la position 1, le premier element avec la cle 2 devra etreplace a la position 4, et le premier element avec la cle 3 devra etre place ala position 8. Il su�t ensuite de parcourir une deuxieme fois les elements atrier et de les placer au fur et a mesure dans un tableau annexe (le tableauR de la figure), en n’oubliant pas, chaque fois qu’un element de cle c est


place, d’incrementer la position de l’objet suivant de cle c. De cette faconles elements qui ont la meme cles apparaissent necessairement dans l’ordrede leur apparition dans le tableau initial.

T

4 93placement de T[3] en R[2]

placement de T[2] en R[8] 4 92

placement de T[1] en R[1] 4 82

1 3 1 2 3 2 1 3 2 2

Nombres d’apparitions 3 4 3

Indices des premiers à placer 41 8

321

1 2 3 4 5 6 7 8 9 10

1 2 3T

R 1 1 2 2 31 2 2 3 3

1 3 1 2 3 2 1 3 2 2

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

La suite des objets a trier est parcourue deux fois, et la table Nb conte-nant le nombre d’occurrences de chaque cle est parcourue une fois pourl’initialiser. La complexite finale est donc O(n + k) si les cles des elementsa trier sont comprises entre 1 et k. Le tri par denombrement est dit lineaire(modulo le fait que k doit etre comparable a n).

Exercice 8 [CLRS] Decrivez un algorithme de complexite O(n + k) quiprend en entree un tableau T comprenant n entiers compris entre 0 et k etqui pre-traite T de maniere a pouvoir repondre a n’importe quelle requetedu type Combien le tableau T a t-il d’elements dans l’intervalle [a, b] ? entemps O(1).

3.5.2 Tri par base.

Le tri par denombrement n’est pas applicable lorsque les valeurs quepeuvent prendre les cles sont tres nombreuses. Le principe du tri par base(radix sort) consiste, dans ce type de cas, a fractionner les cles, et a e↵ectuerun tri par denombrement successivement sur chacun des fragments des cles.

3.5. TRI PAR DENOMBREMENT, TRI PAR BASE. 55

Fonction TriParDenombrements(T, n, k)

entree : T est un tableau de n elements 2 {1, . . . , k}.sortie : R contient les elements de T tries par ordre croissant.debut

/* Initialisations */pour i := 1 a k faire

Nb[i] := 0

/* Calcul des nombres d’apparitions */pour i := 1 a n faire

Nb[T [i]] := Nb[T [i]] + 1

/* Calcul des indices du premier */Nb[k] := n�Nb[k] + 1/* Element de chaque categorie */pour i := k � 1 a 1 faire

Nb[i] := Nb[i+ 1]�Nb[i]

/* Recopie des elements originaux du tableau T dans R */pour i := 1 a n faire

R[Nb[T [i]]] := T [i]Nb[T [i]] := Nb[T [i]] + 1

retourner R

Si on considere les fragments dans le bon ordre (i.e. en commencant parles fragments de poids le plus faible), apres la derniere passe, l’ordre deselements respecte l’ordre lexicographique des fragments, et donc la suite esttriee.

Considerons l’exemple suivant dans lequel les cles sont des nombres en-tiers a au plus trois chi↵res. Le fractionnement consiste simplement a prendrechacun des chi↵res de l’ecriture decimale des cles. La colonne de gauchecontient la suite des valeurs a trier, la colonne suivante contient ces memesvaleurs apres les avoir triees par rapport au chi↵re des unites, . . . Dans laderniere colonne les valeurs sont e↵ectivement triees. Du fait que le tri pardenombrement est stable, si des valeurs ont le meme chi↵re des centaines,alors elles apparaıtront dans l’ordre croissant de leurs chi↵res des dizaines,et si certaines ont le meme chi↵re des dizaines alors elles apparaıtront dansl’ordre croissant des chi↵res des unites.


536 592 427 167893 462 536 197427 893 853 427167 853 462 462853 536 167 536592 427 592 592197 167 893 853462 197 197 893

Supposons que l’on ait n valeurs dont les cles sont fractionnees en cfragments avec k valeurs possibles pour chaque fragment. Le cout du tri parbase est alors O(c⇥n+c⇥k) puisqu’on va e↵ectuer c tris par denombrementsur n elements avec des cles qui auront k valeurs possibles.

Si k = O(n) on peut dire que le tri par base est lineaire. Dans la pratique,sur des entiers codes sur 4 octets que l’on fragmente en 4, le tri par base estaussi rapide que le Quick Sort.

Exercice 9 [CLRS] Montrez comment trier n entiers compris entre 0 etn2 � 1 en temps O(n).

Documents

Algorithmes de tri - pageperso.lif.univ-mrs.frpageperso.lif.univ-mrs.fr/~francois.denis/algoL2/chap3.pdf · Chapitre 3 Algorithmes de tri Trier un ensemble d’objets consiste a les