ramatouFinal

7/23/2019 ramatouFinal

1/54

Implementation of a variety of sorting algorithms, and

Ramatou ABIBOUSemestre 5 unication

Emai

Assistant Responsable : Andrew BROWN

Professeur : Amin SHOKROLLAHI

Semestre dHiver 2004

Sorting Algorithms

look at their behavior and running times on different

inputs.

, Systmes de Comm

Facult I&C, EPFL

l : [email protected]

1
http://www.epfl.ch/


2/54

Rsum

Un sujet majeur dalgorithmique est le tri dobjets tels que les tableaux. Le choix du

meilleur algorithme pour une tache particulire peut tre un processus compliqu, qui exigesouvent des analyses mathmatiques sophistiques.

La plupart des algorithmes de tri consistent simplement ranger des nombres dun tableau

dans lordre numrique ou des caractres par ordre alphabtique : il est donc important de

comprendre que les algorithmes sont trs largement dpendant du type des lments trier,

et quen fin de compte il nest pas difficile de passer une gnralisation.

Les algorithmes de tri prsents dans ce document sont soit :

- lmentaires: tri bulles, tri par slection, tri par insertion et tri par shell

- complexes: tri rapide (quicksort), tri trois-mdiane, tri par tas (heapsort)

Il est aussi important de prciser quil sagit ici dalgorithmes de tri internes qui

supposent que laccs alatoire chaque lment est possible avec le mme cot, cest par

exemple le cas si les donnes sont stockes dans la mmoire vive.

Ces algorithmes sont tudis sous laxe danalyse et de la performance. Cette performance

a t mesure sur les mmes outils et dans les mmes conditions (mme ordinateur, mme

compilateur) pour chaque mthode afin de ne pjorer lune dentre elles et avoir une base

de comparaison fiable. La performance dans notre cas se dfinit par le temps que prend

lalgorithme pour excuter le tri dun tableau et le nombre total de comparaisons et de

mouvements (un change correspond trois mouvements) que lalgorithme effectue pour

trier lobjet soumis (dans notre cas un tableau)

Pour analyser les diffrents algorithmes de tri, nous avons implment en langage de

programmation C et calcul le nombre doprations fondamentales effectu par chaque

mthode de tri ci-dessus cit en fonction des lments trier. Cette mthode nous a permis

danalyser le comportement de chaque algorithme de tri appliqu un tableau presque tri,

non tri, et tri dans lordre inverse. Cette mthodologie nous a permis darriver aux

conclusions suivantes :

- de manire gnrale, les tris complexes sont plus performants que les mthodes de

tri lmentaires en regard dun volume de donnes important

- Le choix de la mthode de tri dpend fortement du volume de donnes trier.

Leffort dimplmentation des mthodes de tri complexes doit tre mis dans labalance avec leur performance afin deffectuer le choix le plus adquat et le plus

optimal

- Le tri Shell qui requiert peu de code est un bon compromis performance Versus

Volume de donnes si les incrments sont bien dfinis.

2


3/54

Table des Matires

RESUME ---------------------------------------------------------------------------------------------- 2

TABLE DES MATIRES-------------------------------------------------------------------------- 3

1. INTRODUCTION ------------------------------------------------------------------------------ 5

1.1 Historique des Algorithmes de Tri.---------------------------------------------------------------------------------6

1.2 Situation actuelle et perspectives des Algorithmes de Tri. ---------------------------------------------------6

2. TRIS ELEMENTAIRES --------------------------------------------------------------------- 82.1 Tri Bulles (Bubble Sort)--------------------------------------------------------------------------------------8

2.1.1 Mthode et Implmentation-------------------------------------------------------------------------------------82.1.2 Analyse et Performance Thoriques du Tri bulles ----------------------------------------------------102.1.3 Rsultats des Tests Effectus---------------------------------------------------------------------------------- 122.1.4 Courbes Obtenus---------------------------------------------------------------------------------------------122.1.5 Observations et Conclusions sur lAlgorithme du Tri Bulles ----------------------------------------15

2.2 Tri par Slection (Selection Sort)-------------------------------------------------------------------------------- 152.2.1 Mthode et Implmentation du Tri par Slection------------------------------------------------------------ 152.2.2 Analyse et Performance Thoriques du Tri par Slection ------------------------------------------------- 172.2.3 Rsultats des Tests Effectus---------------------------------------------------------------------------------- 18

2.2.4 Courbes Obtenus------------------------------------------------------------------------------------------------182.2.5 Observations et Conclusions sur le Tri par Slection ------------------------------------------------------20

2.3 Tri par Insertion (InsertionSort)---------------------------------------------------------------------------------- 212.3.1 Mthode et Implmentation ----------------------------------------------------------------------------------- 212.3.2 Analyse et Performance Thoriques du Tri par Insertion -------------------------------------------------- 222.3.3 Rsultats des Tests Effectus---------------------------------------------------------------------------------- 242.3.4 Courbes Obtenus------------------------------------------------------------------------------------------------242.3.5 Observations et Conclusions sur lAlgorithme du Tri par Insertion-------------------------------------- 25

2.4 Tri par Shell (Shell Sort) ------------------------------------------------------------------------------------------- 262.4.1 Mthode et Implmentation ------------------------------------------------------------------------------------ 262.4.2 Analyse et performance Thoriques du Tri ------------------------------------------------------------------ 28

2.4.3 Rsultats des Tests Effectus---------------------------------------------------------------------------------- 282.4.4 Courbes Obtenus------------------------------------------------------------------------------------------------282.4.5 Observations et Conclusions sur lAlgorithme du Tri Shell-----------------------------------------------28

2.5 Comparaisons des Tris Elmentaires---------------------------------------------------------------------- 29

3. TRIS SOPHISITIQUES OU COMPLEXES-----------------------------------------------31

3.1 Tri Rapide (quiksort)------------------------------------------------------------------------------------------------ 313.1.1 Mthode et Implmentation----------------------------------------------------------------------------------- 313.2.2 Analyse et performance du Thoriques du Quicksort------------------------------------------------------- 333.2.3 Rsultats des Tests Effectus---------------------------------------------------------------------------------- 35

3.1.4 Courbes Obtenus---------------------------------------------------------------------------------------------353.1.5 Observations et Conclusions sur lAlgorithme du Quicksort---------------------------------------------- 36

3


4/54

3.2 Tri Trois-Mediane : Amlioration du tri rapide par la stratgie du choix du pivot ------------------ 363.2.1 Mthode et Implmentation ----------------------------------------------------------------------------------- 373.2.2 Analyse et performance Thoriques du Tri------------------------------------------------------------------ 383.2.3 Rsultats des Tests Effectus---------------------------------------------------------------------------------- 393.2.4 Courbes Obtenus------------------------------------------------------------------------------------------------393.2.5 Observations et Conclusions sur lAlgorithme du Tri 3-mediane ---------------------------------------- 40

3.3 Tri par Tas ( Heapsort )------------------------------------------------------------------------------------------- 403.3.1 Mthode et Implmentation ------------------------------------------------------------------------------------ 413.3.2 Analyse et Performance Thoriques du Heapsort ---------------------------------------------------------- 453.3.3 Rsultats des Tests Effectus---------------------------------------------------------------------------------- 463.3.4 Courbes Obtenus------------------------------------------------------------------------------------------------463.3.5 Observations et Conclusions sur lAlgorithme du Heapsort ---------------------------------------------- 47

3.4 Comparaisons des Tris Sophistiqus----------------------------------------------------------------------- 48

4. CONCLUSION GENERALE -----------------------------------------------------------------48

5. ANNEXE DES RESULTATS DES TESTS ----------------------------------------------53

4


5/54

1.INTRODUCTIONUn algorithmedcrit un traitement sur un certain nombre fini de donnes. Il est fait dun

ensemble fini dtapes.

Quest-ce quun tri ?On suppose quon se donne un suite de N nombres entiers, et on veut

les ranger en ordre croissant (ou dcroissant) au sens large. Ainsi, pour n = 7, la suite

(5, 2, 3, 0, 6, 1, 1) devra devenir (0, 1, 1, 2, 3, 5, 6).

Cest ainsi que plusieurs algorithmes de tri sont dvelopps. Ils permettent de trier

ou ranger une srie de donnes dans un ordre prcis (Par exemple dans un ordre

alphabtique). Les algorithmes de tri sont trs importants en pratique, en particulier sur les

graphes (tri topologique ou TopSort en Anglais, Kushukal, etc), dans les systmes

dexploitation et aussi dans le domaine de linformatique de gestion o beaucoup

dapplications consistent trier des fichiers.

De plus on estime que plus que 25% du temps de calculs utilis commercialement estconsacr aux oprations de tri (sorting). Ceci illustre limportance dudveloppement des

mthodes de tri puissantes. Mais ces dernires peuvent tre lentes ou rapides selon la taille

des donnes trier ou si le tableau est presque tri, non tri et tri dans lordre inverse.

Afin de contribuer en partie la rduction de temps de calcul (25%), le but de ce projet est

danalyser et de comparer des algorithmes pour prdire quelle mthode de tri conviendrait

le mieux aux donnes trier : do le problme du choix optimal des mthodes de tris.

Dans tout ce qui suit, on suppose que lon trie des nombres entiers et que ceux-ci se

trouvent dans un tableau.

Complexit dun algorithme :

Analyser un algorithme revient prvoir les ressources (i.e. la quantit de mmoire)

ncessaires cet algorithme et mesurer son temps dexcution. En gnral, quand on

analyse plusieurs algorithmes candidats pour un problme donn, on arrive aisment

identifier le candidat le plus efficace. Ce type danalyse peut rvler plusieurs candidats

valables et permet dliminer les autres.

Comme la plupart des mthodes de tri interne, les algorithmes effectuent deux types

doprations : des comparaisons entre cls et des changes dlments.

On compte le nombre de ces oprations fondamentales pour un tableau de N lments, ce

qui donne une ide de la complexit.

Si on sintresse lapplication des tris dans la ralit, souvent on a des donnes de grandes

tailles trier, cest donc ncessaire de voir comment ces mthodes de tri se comportent

quand la taille du tableau devient grande. Do le nom de la complexit : bonne infrieure

et suprieure. Plusieurs chercheurs ont travaill sur la complexit des algorithmes de tri et

ont confirm les rsultas ci-dessus que nous avons tester au cous de ce projet et a savre

vrai

Lanalyse dun algorithme, mme simple, peut savrer difficile. Il est donc ncessaire de

se donner des outils mathmatiques pour parvenir nos fins.

5


6/54

Notation asymptotique

Les fonctions que lon considre dans cette section sont des fonctions de N dans N. Soient

f et g deux fonctions.

Dfinition 1 : On dira que f est O(g) si et seulement si il existe c > 0 et n0 tel que

f(n) 0 et n0 tel que f(n) > c g(n)

Dfinition 3 : On dira que f est o(g) si et seulement si lim (f(n)/g(n))= 0,si n tend vers

linfini.

Dfinition 4 : On dira que f est (g) si et seulement sil existe c1, c2 > 0 et n0 tel que

c1g


7/54

Dans la pratique, les fichiers trier sont soit de petite taille mais trs nombreux, soit alors

partiellement tris ou mme dj, ou alors contiennent un grand nombre de cls dupliqus :

pour ces fichiers, les algorithmes lmentaires savrent mieux adapts, tandis que les

algorithmes sophistiqus entranent des surcharges les rendant moins efficaces.

De nos jours, on continue optimiser les algorithmes de tris en amliorent leur

implmentation mais sans pour pouvoir changer radicalement leur complexit, cest--dire

les bornes suprieures et infrieures.

Au lieu de penser dvelopper de nouveaux algorithmes de tris hyper-sophistiqus dans le

futur, il serait srement intressant de contourner ou rgler les failles ou carences des

algorithmes lmentaires, ceci afin desprer viter les ventuels problmes de surcharge

tout en bnficiant dune bonne complexit.

7


8/54

2.TRIS ELEMENTAIRESIls sont au nombre de quatre tudis dans ce projet, leur implmentation est facile et

requiert trs peu de code.

Les tableaux trier sont reprsents comme suit : a[0],a[1],a[i]a[N-1] avec N la

taille du tableau o i est lindice du ime lment du tableau.

Par convention dans ce rapport, on note par :

- MoyC, MaxC et MinC respectivement le nombre de comparaisons moyen (cas

moyen), maximal (pire des cas) et minimal (meilleur des cas).

- MoyE, MaxEet MinE respectivement le nombre dchanges moyen, maximal et

minimal.

- MoyM, MaxM et .MinM respectivement le nombre de mouvements moyen,

maximal et minimal.

Un change correspond trois mouvements.

2.1 Tri Bul les (Bubble Sort)

Le nom de ce tri vient de ce que les lments les plus grands (lourds) remontent vers la

fin du tableau comme les bulles vers le haut dun tube essai.

Cest le tri le plus simple que nous allons tudier.

2.1.1 Mthode et ImplmentationLe tri Bulle est une mthode de tri qui consiste comparer successivement tous les

lments adjacents dun tableau et les changer si le premier lment est suprieur au

second. On recommence cette opration tant que tous les lments ne sont pas tris. A

chaque tape de lalgorithme llment maximal est dplac la fin de la suite.

Voici un exemple dapplication de cette mthode sur un tableau de taille N=6

a[0] a[1] a[2] a[3] a[5]Donnes : 115 101 30 63 20 47

1repassage:Echanges : 101115

3011563115

8


9/54

2011547115

Rsultat du 1er passage 101 30 63 20 47 115

Au 1erpassage llment (115) ,le plus grand du tableau est dplac en N-1 (ici 5

me) position

2me passage:Echanges: 30101

6310120101

47101

Rsultat du 2me passage 30 63 20 47 101 115

Au 2mepassage llment (101),deuxime plus grand lment du tableau est dplac en N-2( ici 4me) position

3me passage:pas dechanges: 30 < 63

Echanges: 206

4763

30 20 47 63 101 115Rsultat du 3me passage

Au 3mepassage llment (63) , 3me plus grand lment du tableau est dplac en N-3 (ici 3me) position

4me passage :Echanges:

2030pas dechanges: 30 < 47

Rsultat du 4me passage20 30 47 63 101 115

Au 4mepassage llment (47),4me plus grand lment du tableau est dplac en N-4 (ici 2me) position

5me

passage:Pas dechanges: 20 < 30

20 30 47 63 101 115Rsultat du 5me passage

Au 5me le tableau est tri et lalgirithme sarrte et on saperoit quil y a N-1 (5 passages)

Code Source de tri bulle en Langage C#i ncl ude

9


10/54

voi d Bubbl eSort ( i nt *a , i nt N, l ong l ong *echanges, l ong l ong*compar ai son){bool condi t i on =f al se;

i nt r = N- 1;whi l e( ! condi t i on) {

condi t i on = true;f or ( i nt i =1; i


11/54

Les complexits en nombre de comparaisons pour le tri bulle sont donc :

MaxC(N)= N(N-1)/2)=O(N^2)

MoyC(N)=O(N^2)

MinC(N) = N-1=O(N)

Nombre de Mouvements :

Le nombre dchanges maximal (MaxE) :

Le nombre dchanges peut tre au maximal N-1 au premier parcours de la while de la

mthode BubbleSort implmente ci-dessus, N-2 au deuxime parcours, ainsi de suite

jusqu 1 change au N-1 parcours. Cest le cas si le tableau est tri en ordre dcroissant.

On a donc:

N-1

MaxE(N) = (N-i) = N(N-1)/2 MaxM(N) =3* N(N-1)/2i=1

La complexit au pire en nombre de mouvements du tri bulle est en O(N^2) .Notons que

si le tableau est tri, on ne fait aucun mouvement.

MinM(N)=0

Calcul par dnombrements du nombre dchanges moyen (tableau non tri).

Soit t un tableau de taille N et t son miroir (t[1]=t[N],t[2]=t[N-1],.t[N]=t[1])

Si on excute lalgorithme sur t et t, chaque paire dlments est change, soit dans t, soit

dans t, jamais dans les deux. Donc pour le tri de t et t on a en tout autant dchanges quil

y a de paires dlments dindices diffrents, soit N(N-1)/2 changes, donc 3*N(N-1)/2

mouvements.

Considrons lensemble T de tous les tableaux de taille N, ne comportant pas dlments

gaux. Supposons quils sont tous quiprobables. Daprs la dfinition de la complexit en

moyenne, si cot E(t) est le nombre dchanges effectus pour trier le tableau t, et si p(t) est

la probabilit du tableau t ,on a :

MoyE(n) = p(t).cotE(t)

t

T

11


12/54

On peut partitionner T en Tc, ensembles des tableaux de taille N tels que t[1]< t[N] et Td ,

ensemble des tableaux de taille N tels que t[1]>t[N] . Si t Tc, alors t Td et

rciproquement. Do :

MoyE(N) = p(t).cotE(t) + p(t).cotE(t)

t Tc t Td

Tous les tableaux tant quiprobable, posons pour tout t, p(t) =p. On obtient :

MoyE(n) = p*( cotE(t) + cotE(t))

t Tc t Td

= p*(cotE(t) + cotE(t))

t Tc

= p *N(N-1)/2 = p *card(Tc)* N(N-1)/2

Il existe une bijection entre Tc et Td, ils sont donc de mme cardinalit, do :

P *card(Tc)=1/2

Par consquent :

MoyE(N) = 1/2 * N(N-1)/2 = N(N-1)/4

Dans le cas o les lments sont distincts, et o les listes ont de mme probabilit, on a

en nombre de mouvements :

MoyM(N) = 3* N(N-1)/4 = O(N^2)

Par consquent, la complexit en moyenne en nombre de mouvements du tri bulles est en

O(N^2).

Pour le tri bulle, le comportement pire des cas, moyen des cas et meilleur des cas

sobtiennent respectivement avec un tableau tri dans lordre inverse, non tri et presque

tri

2.1.3 Rsul tats des Tests Effectus

-Voir annexe1

2.1.4 Courbes Obtenus

12


13/54

Bubble

0

100000000000

200000000000

300000000000

400000000000

500000000000

600000000000

1 100 10000 1000000

N

Nbredemouvements+Nbre

decomparaisons

Tableau non tri (moyen

des cas)

Tableau tri dans l'ordre

inverse (pire des cas)

Tableau dj tri (meilleur

des cas)

Bubble

0

0.5

1

1.5

2

2.5

1 10 100 1000 10000 10000

0

1E+06

N

(Nbredem

ouvements+

compara

isons)/N^2

Tableau non tri (moyen descas)


inverse (pire des cas)Tableau dj tri (meilleurdes cas)

13


14/54

Bubble

0.000000

20000.000000

40000.000000

60000.000000

80000.000000

100000.000000

120000.000000

140000.000000

1 100 10000 1000000

N

Temps

Tableau non tri(moyen des cas)

Tableau tri dansl'ordre inverse (pire descas)

Tableau dj tri(meilleur des cas)

Bubble

0.0000000.000020

0.000040

0.000060

0.000080

0.000100

0.000120

1 100 10000 1000000

N

Temps/N^2 Tableau non tri

(moyen des cas)

Tableau tri dansl'ordre inverse (pire

des cas)Tableau dj tri(meilleur des cas)

14


15/54

2.1.5 Observations et Conclusions sur lAlgori thme du Tri Bulles

Etant donn que sa complexit en nombre moyen et maximal de mouvements est assez

leve, le tri bulles a peu dintrt en pratique.

Pour un tableau presque tri, thoriquement cette mthode semble intressante et bonne carelle moins coteuse en comparaisons. Mais si on regarde loin dans la ralit et dans les cas

pratiques, on ignore ce bon comportement de la mthode de tri bulle car on cherche

toujours mettre dans lordre une suite dobjets disposes en dsordre.

Selon la thorie, la complexit du tri bulles est quadratique : il trie un tableau en un

temps 0(N^2), cest--direque le temps pour trier un tableau de taille N (N lments) est

proportionnel au carr de la taille. Ce rsultat est parfaitement illustr et confirm par les

tests effectus ci-dessus.

Une piste damlioration du tri bulles serait, lors du parcours de la boucle interne FOR, de

vrifier que llment i se trouve la bonne position ( a[i] ).

Dans les paragraphes suivants, on analysera dautres algorithmes de tri qui tiennent compte

de lordre des lments dans le tableau initial.

2.2 Tri par Slection (Selection Sort)

2.2.1 Mthode et Implmentation du Tri par Slection

Lide est de trier un tableau en dterminant son plus petit, son deuxime plus petit,

troisime plus petit, etc. lment. Cest dire trouver la position du plus petit lment

dans le tableau et ensuite changer a[0] et a[i1]. Ensuite, dterminer la position i2 de

llment avec le plus petit des a[1],..a[N-1] et changer a[1] et a[i2]. On continue

de cette manire jusqu ce que tous les lments soient dans la position correcte.

Un avantage de tri par slection est quil est progressif, car ltape i de lalgorithme, le

tableau est tri de a[0] jusqu a[i-1]

Donnes :

Slection 20

115 101 30 63 20 47

Placement 20 101 30 63 115 47

Slection 30Placement

20 30 101 63 115 47

Slection 47Placement20 30 47 63 115 101

15


16/54

Slection 63 : Pas de changement sur le tableau, car 63 est lui-mme le 4imeplus petit lment.

Placement

20 30 47 63 115 101

Slection 101Placement

20 30 47 63 101 115

Dans lexemple de tri par slection ci-dessus, les lments placs dans le bon ordre se trouvent gauche de labarre verticale

Commentaires : Comme on le voit dans lexemple ci-dessus, le dernier lment (115) nest

pas slectionn. En effet, comme cet algorithme se fait de faon progressive et le dernier

lment du tableau tant le plus grand, il est dj la bonne position.

Si tel ntait pas le cas, il aurait t slectionn et chang avec dautres lments dutableau par consquent il ne serait au dernier placement.

16


17/54

Code Source de tri Slection en Langage C

#include

#include

#include "swap.cpp"void selectionSort(int* a, int N, long long* echanges, long long * comparaisons)

{

for (int i = 0; i < N; i++)

{

int min = a[i];

int minIndex = i;

for (int j = i; j < N; j++)

{

(*comparaisons)++;

if (a[j] < min)

{min = a[j];

minIndex = j;

}

}

if (i != minIndex)

(*echanges)++;

swap(a,i,minIndex);

}

}

2.2.2 Analyse et Performance Thoriques du Tri par Slection

Nombre de comparaisons:

Pour tout tableau de taille N, on effectue exactement N-1 comparaisons pour trouver le 1er

minimum, N-2 comparaisons pour trouver le 2me minimum, ainsi de suite. Plus

prcisment, on fait (N-1-i) comparaisons pour trouver le ime minimum du tableau.

Avec le tri par slection, le nombre de comparaisons de cls ne dpendent pas de lanature du tableau (presque tri, non tri et tri dans lordre inverse). Ainsi on a:

N-i

MaxC N)=MinC (N)=MoyC(N)= (N-1- i) = N(N-1)/2

i=1

Les complexits en nombre de comparaisons pour le tri par slection sont donc :

MaxC(N)=MinC (N)=MoyC(N) =N(N-1)/2 = O(N^2)

17


18/54

Nombre de Mouvements:

Aussi pour les changes, la complexit au pire des cas est gale la complexit en

moyenne. Puisquon fait au maximum un seul change chaque parcours de la boucle

FOR interne de lalgorithme implment en paragraphe 2.21. Comme on a N lments dans

le tableau. On a donc :

MaxE(N)= N-1

MaxM(N)= 3*(N-1)

Avec le calcul par dnombrement du nombre dchanges moyen, comme a t fait

pour le tri par bulle au paragraphe 2.12, on peut montrer que le nombre moyen dchanges

est :

MoyE(N)=N/N-1 + (N-1)/(N-2)+ . +2/1 = N- ln(N) + (1)

Le nombre dchanges moyen doit tre multipli par trois pour obtenir le nombre demouvements moyen (MoyM(N)).

Lescomplexits au pire et en moyenne en nombre de mouvements de la slection

sont en O(N).

Pour un tableau presque tri, lchange ne se fait jamais car ce nest pas ncessaire : do

MinE(N) = 0


-Voir annexe2

2.2.4 Courbes Obtenues

18


19/54

0.0000000

200000.0000000

400000.0000000

600000.0000000

800000.0000000

1000000.0000000

1200000.0000000

1 10 100 1000 1000

0

1E+0

5

1E+0

6

N

t(

ms)



Tableau non tri (moyen des

cas)Tableau dj tri (meilleur des

cas)

0.0000000000000

0.0000010000000

0.0000020000000

0.0000030000000

0.0000040000000

0.0000050000000

0.0000060000000

0.0000070000000

0.0000080000000

0.0000090000000

1 100 10000 1000000

N

t(ms)/N^2

Tableau tri dans l'ordreinverse (pire des cas)

Tableau non tri (moyendes cas)

Tableau dj tri (meilleurdes cas)

19


20/54

0.00

20000000000.00

40000000000.00

60000000000.00

80000000000.00

100000000000.00

120000000000.00

140000000000.00

1 100 10000 1000000

N

Nbre

Echange-comparaison

Tableau non tri (pire

des cas)

Tableau tri dans l'ordreinverse (moyen des cas)

Tableau dj tri

(meilleur des cas)

0.0000000000000

0.1000000000000

0.2000000000000

0.3000000000000

0.4000000000000

0.5000000000000

0.6000000000000

0.7000000000000

0.8000000000000

1 10 100 1000 1000

0

1E+0

5

1E+0

6

N

Nbreechange-comparaison/N^2

Tableau non tri (pire des

cas)


inverse (moyen des cas)

Tableau dj tri (meilleur des

cas)

2.2.5 Observations et Conclusions sur le Tri par Slection- En observant les courbes ci-dessus, on se rend compte que les rsultats thoriques de

complexit dmontrs et confirms par plusieurs chercheurs dans le domaine de

lalgorithme reste aussi vrai en pratique, heureusement pour lhistoire des tris.

-Le premier graphe du haut illustrent les rsultats du temps mis par le tri Slection pour

trier un tableau de taille N. Comme a t dmontr thoriquement ci-dessus, les graphes en

temps ont une allure quadratique pour les types de tableaux utiliss dans ce projet (enN^2), ce qui est vrai seulement partir dune certaine valeur trs grande, on voit sur le

graphe que cette valeur correspond N= 10^5. Par ailleurs on saperoit facilement sur le

graphe quil existe une constante k =temps/N^2 39*10^-7 partir de N=10^4.

Les deux derniers graphes illustrent bien que le nombre de comparaisons plus le nombre de

mouvement suivent bien N^2 et la constante K 0.5 partir de N=10^4

b) Avantage par rapport dautres tris:

Aucun autre algorithme ne peut trier un tableau avec aussi peu de mouvements que le tri

par Slection. En effet comme le nombre dchanges en pire des cas et en moyen des cas

est linaire, c'est--dire en O(N), il peut tre intressant pour des entres qui ncessitent

beaucoup plus dchanges et trs peu de comparaisons. Par exemple le tri par Slectionsurpasse beaucoup de mthodes plus sophistiques dans un type important dapplication :

20


21/54

Dans la pratique, cest la mthode choisir pour trier un nombre important de petits

fichiers (quivalent un tableau de petite taille associ de grandes cls.

-Dsavantage par rapport dautres tris:

Lun des inconvnients de ce tri est que son temps dexcution ne dpend pas de la nature

de lentre trier. IL passe quasiment le mme temps pour trier un tableau dj tri, un

tableau gnr de faon alatoire et un tableau tri dans lordre inverse.

Remarquons aussi que la mthode par Slection est peu pratique pour les tableaux

partiellement tri et dj tri contrairement tri bulle qui a une complexit O(n) pour le

meilleur des cas. On verra au paragraphe suivant une mthode qui trie tout en accordant une

attention particulire aux types de tableau partiellement tri.

2.3 Tri par Insertion (InsertionSort)

2.3.1 Mthode et Implmentation

Lide est de trier successivement les premiers lments du tableau. A la ime tape on

insre le ime lment son rang parmi les i-1 lments prcdents qui sont dj tris entre

eux. Lalgorithme commence par sexcuter partir du 2me lment du tableau. Cette

mthode sappelle aussi la mthode du joueur de cartes. Les tapes successives sont

dcrites ci-dessous.

Voici un exemple dapplication de cette mthode sur un tableau de taille N=6

a[0] a[1] a[2] a[3] a[4] a[5]Donnes: 115 101 30 63 20 47

1reinsertion : 101 115 30 63 20 47

2meinsertion: 30 101 115 63 20 47

3reinsertion:

30 63 101 115 20 47

4reinsertion

: 20 30 63 101 115 47

21


22/54

5me

insertion: 20 30 47 63 101 105

Le tableau est trijusqu la barre verticale ; llment insrer est encercl

#include

void Insertion ( int *a, int N,long long *echanges ,long long * comparaisons,long long *mouvements)

{

for (int i= 1;it && j>=0){a[j+1]=a[j];

(*mouvements)++;j=j-1;(*comparaisons)++;

}

a[j+1]=t;(*mouvements)++;

}}

2.3.2 Analyse et Performance Thoriques du Tri par Insertion

Nombre de comparaisonsPour insrer le ime lment, nous avons au moins 1 et au plus i-1 comparaisons faire.

On a donc:

N

MaxC(N ) = (i -1) =O(N^2)i=2

22


23/54

MinC(N)=N-1

On peut montrer comme a t dmontr pour le tri bulle que :

MoyC(N)= O(N^2)

Nombre de MouvementsContrairement aux autres algorithmes o on compte le nombre dchanges, la mthode de

tri par insertion fait uniquement des mouvements.

Cet algorithme est facile analyser. Ainsi :On compte i-1 mouvements dans le meilleur des cas (le comportement avec le tableau dj

tri). Do :

MinM(N)=0

Avec un tableau tri dans lordre inverse, ce qui, pour ce tri, est le pire des cas :

La boucle interne WHILE qui se trouve dans limplmentation ci-dessus fait au maximum

N-i itrations si on est la ime insertion, comme on commence le tri partir de i=2 (

deuxime lment du tableau.) en plus on a N lments au total dans le tableau.

Le nombre de mouvements maximal se calcule comme suit :

N

MaxM(N)=(i-2) = O(N^2)

i=2

La complexit du nombre de mouvements maximal est : MoyM(N) ==O(N^2)

Avec le calcul par dnombrement du nombre dchanges moyen, comme a t fait

pour le tri par bulle au paragraphe 2.12 , on peut montrer que le nombre moyens dchanges

est :

MoyM(N)=N*(N+3)/4

La complexit du nombre moyen de mouvements est : MoyM(N) ==O(N^2)

La complexit en O(n^2) qui est prouver thoriquement seront justifis par les rsultats destests et les graphes ci-dessous..

23


24/54


-Voir annexe 3


InsertionSort

0.00000

500000.00000

1000000.00000

1500000.00000

2000000.00000

1 100 10000 1000000

N

t(ms)


des cas)




des cas)

InsertionSort

0

0.000002

0.000004

0.000006

0.000008

0.00001

1 100 10000 1000000

N

t(ms)


des cas)




des cas)

24


25/54

insertionSort

0

5E+10

1E+11

1.5E+1

1

2E+11

2.5E+1

1

3E+11

1 100 10000 1000000

N

NbreEchange-

comparaison


des cas)Tableau tri dans l'ordre



des cas)

InsertionSort

0

0.2

0.4

0.6

0.8

1

1.2

1 100 10000 1000000

N

Nbre

echange

+comparaison/N^2

Tableau non tri (moyendes cas)

Tableau tri dans l'ordreinverse (pire des cas)

Tableau dj tri

(meilleur des cas)

2.3.5 Observations et Conclusions sur l Algorithme du Tri par Insertion

Avantages du tri Insertion par rapport dautres tris:

A la diffrence du tri par Slection, le temps dexcution du tri par Insertion dpend

essentiellement de lordre initial des cls dans le tableau. Par exemple si le tableau est

grand et que les cls sont dj ordonnes (ou presque ordonnes), le tri par insertion est

rapide, tandis que le tri par slection est lent.

Dsavantages du tri Insertion par rapport dautres tris:

Pour un tableau tri dans lordre inverse ; le fait que le tri par Slection fait au maximum

N-1 changes (=3*(N-1) mouvements) fait que quand N devient trs grand, par exemple on

le voit sur les graphes que pour N= 5*10^5, le tri Par Slection est plus rapide que le tri par

insertion.

25


26/54

En conclusion, il est noter quon pourrait amliorer le temps de calcul de tri par insertion

pour amliorer son comportement dans le meilleur des cas en vitant les transferts inutiles

pour un tableau dj tri .

Jai remarqu ceci lors des tests pratiques, jai rflchi ce problme et jai abouti la

conclusion que seul le tableau dj tri en bnficie, le cas moyen trs peu car les nombres

utiliss pour les tris dans ce projet sont gnrs alatoirement. Ainsi on ne gagne pasbeaucoup en optimisant de cette manire et surtout parce que cest en faveur des tableaux

dj tris qui ne refltent pas les problmes de tri dans la ralit.

2.4 Tri par Shell (Shell Sort)Cet algorithme de tri a t dvelopp en 1950 par D. L. Shell

2.4.1 Mthode et ImplmentationRappel : La lenteur du tri par insertion est due au fait que les seules permutations ralises

le sont avec des lments adjacents. Les lments peuvent donc parcourir tout le tableau

mais en ne se dplaant que dune place la fois. Par exemple, si llment de plus petite

cl est la fin du tableau, N tapes sont ncessaires pour le placer correctement.

Le tri Shell est une extension du tri par insertion qui entrane un gain de temps en

permutations dlments ventuellement trs loigns.

Il faut rorganiser le tableau de manire obtenir un sous tableau ordonn en slectionnant

tous les h-imes lments ( partir de nimporte quelle position initiale)

Un tel tableau est dit h-ordonn et il est constitu de h sous tableaux ordonnsindpendants, entrelacs. En h-ordonnant le tableau pour une grande valeur de h, on

change les lments trs distants dans le tableau, afin de faciliter la mme opration pour

les valeurs infrieures de h. Lutilisation dune telle mthode avec une srie dcroissante

de h termine par 1 donne un tableau tri : Cest le principe du tri Shell.

Une manire dimplmenter le tri Shell serait dutiliser, pour chaque valeur de h un tri par

insertion de manire indpendante sur chacun des h tableaux. En dpit de lapparente

simplicit de ce processus, il est possible dutiliser une approche encore plus simple

prcisment parce que les sous tableaux sont indpendants.

Comment dcider de lincrment utiliser ?En gnral, il est assez difficile de donner une rponse. Les proprits de nombreuses

squences dincrments ont t tudies et beaucoup dentre elles fonctionnent trs bien

dans la pratique, sans quil soit toutefois possible de trouver la meilleure dentre elles. En

pratique ,on utilise des squences qui dcroissent de manire de manire gomtrique ,ce

qui fait que le nombre dincrments est fonction du logarithme de la taille du tableau .Par

exemple ,si chaque incrment est environ la moiti du prcdent, on a seulement besoin de

20 incrments pour trier un tableau dun million dlments et si le rapport est de 1 4

seulement de 10 incrments pour le mme tableau..

Lutilisation daussi peu dincrments que possible est une caractristique importante qui

est facile respecter. Il est galement ncessaire de considrer les interactions

26


27/54

arithmtiques entre ces incrments comme la taille de leurs diviseurs communs et dautres

proprits.

Lutilisation dun bon incrment pour effet pratique daugmenter la vitesse denviron

25%, mais ce problme est un vritable casse-tte qui donne un bon exemple de la

complexit dun algorithme apparemment simple.

La squence dincrments 1, 4, 13, 40, 121, 364, 1093, 3280, 984... utilise danslimplmentation du tri Shell dans ce projet, dont le ratio entre les incrments est denviron

un tiers , a t propose par Knuth en 1969 .Celle -ci est facile gnrer (on dmarre avec

1 ,on calcule le prochain incrment en multipliant le prcdent par trois et en ajoutant1) et

donne un tri relativement efficace ,mme pour des fichiers de taille plus petite.

Peut on encore faire mieux ?Beaucoup dautres squences dincrments donnent un tri plus efficace, mais il est difficile

davoir un gain de plus de 20% du rsultat obtenu par la squence des incrments de Knuth,

mme pour les valeurs de N trs grandes.

Notons que la squence 4^(i+1)+ 3*2^i +1 pour i>0 , qui donne 1, 8 (pour i=0),23(pour

i=1), 77(pour i=2),281,1076,4193,16577, est vraiment la plus rapide dans le pire des cas.Les squences dincrments encore meilleures peuvent trs bien exister. Il faut juste se

baser sur les squences de bases et essayer de les amliorer. Dun autre ct, il existe de

mauvaises squences : par exemple la suite gomtrique de raison 2 (1,2,4.) qui est la

squence originale propose par Shell en 1959 donne de mauvaises performances parce

que les lments de position impaire ne sont pas compars avec ceux de position paire

jusqu la passe finale.

Code en C du tri Shell

#include "methods.h"

void Shellsort (int *a,int l,int r,long *comparaisons,long*mouvements){

for (int h = 1; h 1;h /=3)

printf("%d\n",h);

for(int i=l+h;i=h+l)&&(v


28/54

2.4.2 Analyse et performance Thoriques du TriShell

La description de lefficacit du tri Shell est forcment imprcise parce que personne

na jamais russi analyser cet algorithme. Cette lacune dans la connaissance rend difficile

non seulement lvaluation de diffrentes squences dincrments mais aussi lacomparaison analytique de ce tri avec les autres mthodes. Bien que la modlisation

formelle du temps dexcution de ce tri Shell ne soit pas connue (il dpend en effet de la

squence utilise). Knuth trouver que la modlisation formelle donne par N(log(N))^2 et

N^1.25 donne de bons rsultats.

Complexit de lalgorithme tri Shell implment dans ce projet est :

-Pour le nombre de comparaisons

MoyC(N)=O(N^3/2)

MaxC(N)=O(N^3/2)

MinC(N)=O(N^3/2)

-Pour le nombre de mouvements

MoyM(N)=O(N^3/2)

MaxM(N)=O(N^3/2)

MinM(N)=O(N^3/2)

2.4.3 Rsul tats des Tests Effectus-Voir annexe 4

2.4.4 Courbes Obtenues

Shell Sort

0.00

100000.00

200000.00

300000.00

400000.00

500000.00

600000.00

700000.00

800000.00

0 200000 400000 600000

Taille du tableau

Temps(ms)

Temps dans le casmoyen

2.4.5 Observations et Conclusions sur lAlgorithme du Tri Shell

La courbe ci-dessus suit bien lallure de N^3/2. On peut donc dire que son temps de tri croit

moins vite que les algorithmes de complexit O(N^2). On a galement vu que le tri Shellpeut devenir trs mauvais si le choix de lincrment nest pas judicieux. Lalgorithme est

28


29/54

trs facile coder, mais le choix de lincrment optimal est plus complexe, ce qui rend

difficile une gnralisation de sa performance.

Pour conclure, voquons certains aspects connus de lanalyse de ce tri. Lobjectif ici est de

montrer que mme des algorithmes apparemment simples peuvent avoir des performances

comparables celles des tris complexes.

2.5 Comparaisons des Tris Elmentaires

Voici un tableau rcapitulatif de leurs complexits

Nombre de comparaisons Nombre de mouvementsAlgorithme

Min Moy Max Min Moy Max

Tri bulle N-1 N(N-1)/2 N(N-1)/2 0 3*N(N_1)/4 N(N-3)/2

Tri

Slection

N(N-1)/2 N(N-1)/2 N(N-1)/2 0 N ln(N) + (1) 3*(N-1)

Tri

Insertion

N-1 N*(N+3)/4 N(N-3)/2 0 N*(N+3)/4 N(N-5)/2

Tableau contenant le nombre de comparaisons et de mouvements des tris lmentaires

Nombre de comparaisons Nombre de mouvementsAlgorithme

Min Moy Max Moy Max

Tri bulle O(N) O(N^2) O(N^2) O(N^2) O(N^2)

Tri

Slection

O(N^2) O(N^2) O(N^2) O(N) O(N)

Tri

Insertion

O(N) O(N^2) O(N^2) O(N^2) O(N^2)

Tri Shell O(N(log(N))^2)

Tableau contenant les performances des tris lmentaires

29


30/54

On sait que la plus part des tris lmentaires (Bulle, Insertion, Slection) ont une

complexit quadratique en O(N^2) except le tri par Shell.Mais Le tri Bulle est gnralement plus lent que les deux autres (Insertion et Slection)

on peut amliorer cet algorithme de manire viter les parcours sans changes.

Jusquici, mon rapport a prsent quatre mthodes de tri simples ; Un lment de

comparaison entre ces mthodes est que les mthodes de slection donnent ltape i, le

dbut du futur tableau trier. On dit que ce tri est progressif. Cela permet de commencer

ventuellement un traitement en parallle sur ce tableau. Cela nest pas possible si on utilise

une mthode par Insertion.

Pour un tableau alatoire (non tri): Le temps dexcution de tri bulle est environ 2 fois

celui de tri par Slection dont le temps est environ une fois et demi celui de Insertion.

On peut donc conclure que le tri par insertion est le meilleur, suivi par le tri Slection et en

dernier le tri par Bulle qui est vraiment lent pour les entres alatoires.

Par contre pour les entres spciales, par exemple :

Pour un tableau presque tri: le tri bulle est 10 fois mieux que Slection partir de N

=10000 mais Insertion reste toujours le meilleur car le temps total dexcution est linaire

(O(N))

Pour un tableau tri dans lordre inverse: Pour les N trs grand, le tri est slection est le

plus rapide, suivi du tri par bulles cause du fait quil fait les changes entre deux lmentsadjacents tandis que le tri par Insertion fait des mouvements sur tout le tableau chaque

fois si un lment nest pas la bonne place.

Parmi ces quatre tris lmentaires, le tri Shell est le choix idal faire pour beaucoup

dapplications de tri parce quil a un temps dexcution raisonnable quelque soit le type de

tableau trier.

Vu limportance des tris dans plusieurs domaines, il existe des mthodes de tri plus

performantes que les tris lmentaires, leur fonctionnement fera le sujet des paragraphes

suivants.

30


31/54

3. TRIS SOPHISITIQUES OU COMPLEXES

Quand les lments du tableau associs aux cls sont grands, les tris lmentairesdeviennent mauvais. Mais il existe des tris plus volus qui prsentent des complexits en

O(NlogN) en moyenne et mme dans le pire des cas en ce qui concerne le tri par tas

(heapsort en anglais) : ce sont lestris sophistiqus.

3.1 Tri Rapide (quiksort)

La version initiale de lalgorithme quicksort a t invente en 1962 par C. A. R. Hoare. Il

doit son nom au fait quil est lun des algorithmes de tri connus les plus rapides. Il

fonctionne bien pour de nombreux types de donnes en entre.

Lalgorithme du tri rapide a pour avantage de se faire sur place (il transforme une

structure de donnes en utilisant une quantit de mmoire supplmentaire minimale et

constante, les entres sont crases par les sorties)

3.1.1 Mthode et ImplmentationOn choisit un lment arbitraire b appel le pivot parmi les lments du tableau. On

subdivise le tableau en deux sous tableaux, S1 contient les lments du tableau qui sont

plus petits ou gaux au pivot et dans S2, les lments du tableau qui sont plus grands ou

gaux au pivot. Lalgorithme de tri rapide est ensuite appliqu rcursivement ces deuxsous suites. Si un sous tableau contient un lment, on ne fait rien.

Un sous tableau du tableau original est dtermin de faon unique par deux indices i et j

(voir limplmentation ci-dessus). A chaque appel rcursif de la mthode quicksort, nous

appelons la routine en spcifiant l (de llment de plus gauche) et r (de llment de plus

droit).

Comment crer les sous tableaux:

Pour le tri rapide implment dans ce projet, nous avons utilis la stratgie gnrale

suivante pour la mthode de partition. On choisit arbitrairement a[r] pour quil soit le

pivot de la partition. Il ira donc sa place finale. On parcourt ensuite le tableau en partant

de la gauche jusqu ce quon trouve un lment plus grand que le pivot, de mme on

parcourt le tableau en partant de la droite jusqu ce quon trouve un lment plus petit quele pivot. Ces deux lments ntant pas leur place, on les permute. En continuant de cette

manire, on sassure quaucun lment du tableau gauche de lindice de gauche nest plus

grand que le pivot et quaucun lment du tableau droite de lindice droit nest plus petit

que le pivot, comme dcrit dans le diagramme suivant.

Plus petit ou gal v Plus grand ou gal v V

l i j r-1

31


32/54

Lorsque les indices se croisent, on complte le processus de partition en changeant a[r-1]

avec llment le plus gauche de la partie de la partie droite du sous tableau (cest--direllment dont le rang est gal lindice de gauche: a[i] et a[r-1]).

Code en Langage C de la mthode quicksort

#include "partition.cpp"

void quickSort(int* a, int l, int r,long long *echanges, long long

*comparaisons){

if (r a[r-1])

{

swap(a,l,r-1);

(*echanges)++;

}

return;

}

if (r >= l+3)

int k= partition(a,l,r,echanges,comparaisons);

quickSort(a,l, k,echanges,comparaisons);

quickSort(a,k+1,r,echanges,comparaisons);

}

}

Code en Langage C de la mthode partition

//#include "swap.cpp"

int partition(int* a, int l, int r , long long *echanges, long long

*comparaisons){

int i = l;

int j = r-1;

int pivot = a[r-1];

while (i < j)

{

(*comparaisons)++;while(a[j]>=pivot && j > l){

32


33/54

j--;

(*comparaisons)++;

}

(*comparaisons)++;

while (a[i]


34/54

Voici un exemple de tri rapide (quicksort)

3.2.2 Analyse et performance du Thoriques du QuicksortMalgr ses nombreux atouts, le programme du tri rapide tendance tre

inefficace pour certains tableaux.

Nombre de comparaisons et Nombre de mouvements

34


35/54

Si on lexcute, par exemple, sur un tableau tri dans lordre inverse ou presque tri, de

taille N, toutes les partitions sont dgnres et le programme sappelle N fois, en enlevant

seulement un lment chaque appel (le pivot). Ainsi le nombre de comparaisons dans le

pire des cas est:

MaxC(N)=N+ (N-1)+(N-2)+.+2+1 =(N+1)N/2La complexit en comparaisons et en mouvement dans le pire des cas est :

MaxC(N)= MaxM(N)=(N^2)

Le cas le plus favorable au tri rapide est celui dans lequel ltape de partition scinde le

tableau exactement en deux. Cela permet au nombre de comparaisons effectues de vrifier

lquation de rcurrence propre au principe diviser pour rgner :

MinC(N)=2*MinC(N/2) + N

Le terme 2*MinC(N/2) correspond au cot du tri des deux sous tableaux et N celui de

lexamen de chaque lment cause de lutilisation de lindice de partition. Cette quation

de rcurrence admet comme solution :MinC(N) ~N/log(N)

Le nombre de mouvements en meilleur des cas est 0 :

MinM(N)=0

Dans le meilleur des cas, On en dduit que la complexit est :

MinC(N)=O(NlogN)

Dans le cas moyen, le nombre de comparaisons et mouvements effectus par le tri rapide

est de lordre de 2Nln(N).

Il est signaler que les complexits en nombre de mouvements sont du mme ordre ou

dordre infrieur, car on change trs peu dans lalgorithme mais la comparaison reste trscoteuse pour ce tri.

Bien que la ralit ne corresponde pas toujours la thorie, il est vrai que les pivots

partagent les tableaux au centre en moyenne. La prise en compte de la probabilit exacte de

chaque de chaque position du pivot complique la relation de rcurrence, mais le rsultat

final est similaire.


-Voir annexe 5


35

QuickSort

1.00000

100.00000

10000.00000

1000000.00000

1 10 100 1000 10000 100000

t[m

s]

0.01000

N

tableau nontri

Tableau tridans l'ordreinverseTableaupresque tri


36/54

Quicksort

0.000001

0.00001

0.0001

0.001

0.01

0.1

1

1 100 10000 1000000 10000000

0

N

K


des cas) K=Temps / NlogN



K=Temps / N^2

Tableau presque tri(pire

des cas ) K=Temps/N^2

3.1.5 Observations et Conclusions sur lAlgor ithme du Quicksort

Comportement du tri rapide en face de diffrentes entres possibles :

On peut aussi remarquer quen dessous dune certaine taille des tableaux, le cot en temps

et en place des appels rcursifs devient significatif par rapport aux nombres de

comparaisons. Au-dessous dun certain seuil, il devient plus avantageux dutiliser la

version itrative dune mthode de tri simple (tri par Slection par exemple).

Exprimentalement on saperoit que la valeur de ce seuil est de lordre de 10.

Notons que le tri rapide est quasiment 3 fois plus rapides que le tri shell.

Contrairement au tri par tas, le tri rapide ncessite une pile auxiliaire de (mmoire) de taille

maximum log (N).

La performance du tri rapide dpend du choix du pivot. Durant le projet, Nous avons

essay quelques stratgies de pivots tel que trois-mdiane et neuf-mdiane.

Pendant le test dexcution, on sest rendu compte que la stratgie des neufs na aucun

intrt, au lieu damliorer les performances du tri rapide, elle la dtriore. Ceci se justifie

par le calcul des neufs mdianes qui est compliqu par consquent la mthode prend du

temps. Cependant la stratgie trois mdiane quon abordera au paragraphe suivant est

dune grande importance.

3.2 Tri Trois-Mediane : Amlioration du tri rapide par lastratgie du choix du pivot

Pour viter les cas limites pour lesquels la complexit au pire du nombre de comparaisons

est en O(N^2).On peut, par exemple chercher le trois- mdianes du tableau (C'est--dire ,le

premier lment du tableau, llment milieu et le dernier lment .On tri ces trois lments

et on prend comme pivot llment milieu des trois.

36


37/54


Ce tri rapide amlior la mme implmentation que quicksort, sauf que le pivot ici est

trois-mediane. Le principe de diviser le tableau en 2 sous tableaux chaque tape reste lemme.

Les expriences que nous avons faites sur diffrentes entres possibles montrent que la

stratgie trois-mediane et la limite sur les petits sous tableaux rduisent encore plus le

temps dexcution du tri rapide.

Code en langage C de la mthode partition

#include "getmedian.cpp"

int partition(int* a, int l, int r , long long *echanges, long long *comparaisons){

int p = r-1;

int q = l;

int pivot;

int medIndex = getMedian(a[l], a[(r-1+l)/2], a[r-1]);

if (medIndex == 1)

medIndex = l;

if (medIndex == 2)

medIndex = (l+r-1)/2;

if (medIndex == 3)

medIndex = r-1;

swap(a,medIndex,r-1);

(*echanges)++;pivot = a[r-1];

while (q < p)

{

//(*comparaisons)++;

while (a[p] >= pivot && p > l){

p--;

(*comparaisons)++;

}

//(*comparaisons)++;

while (a[q]


38/54

}

}

swap(a,q,r-1);

(*echanges)++;return q;

}

Code en Langage C de la mthode partition

#include "partition.cpp"

void quickSort3Median(int* a, int l, int r ,long long *echanges, long

long *comparaisons)

{

if (r a[r-1])

{

swap(a,l,r-1);

(*echanges)++;

}

return;

}

if (r >= l+3)

{

int k= partition(a,l,r,echanges,comparaisons);

quickSort3Median(a,l,k,echanges,comparaisons);

quickSort3Median(a,k+1,r,echanges,comparaisons);

}

}

3.2.2 Analyse et performance Thoriques du TriTrois-Mediane

38


39/54

Cest quasiment, le mme analyse que pour le tri rapide (quickSort). Ils ont pas consquent

les mmes complexits. Certes on a remarqu lors de nos diffrents tests quil est plus

rapide que quicksort car il fait moins de comparaisons et de mouvements. Mais ce nest pas

une raison pour quils aient des complexits diffrentes.

3.2.3 Rsul tats des Tests Effectus-Voir annexe 6


3Mediane

0.000000

5000.000000

10000.000000

15000.000000

20000.000000

25000.000000

30000.000000

1 100 10000 1000000 1000000

00

N

t(

ms)





des cas)

3Mediane

0.00E+00

1.00E-05

2.00E-05

3.00E-05

4.00E-05

5.00E-05

6.00E-05

1 100 10000 1000000 10000000

0

N

K





K=Temps / N^2



39


40/54

3Mediane

0

1000000000

2000000000

3000000000

4000000000

5000000000

6000000000

1 100 10000 1000000 1E+08

N

NbreEchange-

comparaiso

nTableau non tri (moyen




des cas)

3Mediane

0.400000

0.600000

0.800000

1.000000

1.200000

1.400000

breEchange

mparaison/log

0.000000

0.200000

1 100 10000 1000000 1E+08

N

Nco


des cas)




des cas)

3.2.5 Observations et Conclusions sur l Algorithme du Tri 3-mediane

Les tests effectus sur le tri 3-mediane nous a prouv quil est deux fois plus

rapide que quicksort. En plus il amliore nettement la dgnrescence de

quicksort dans le pire des cas (avec un tableau presque tri ou tri dans

lordre inverse)

3.3 Tri par Tas (Heapsort)

Cest une structure de donnes simples, appele tas (heap en Anglais), qui permet de grer

efficacement les oprations de bases des files priorit.

Les enregistrements dun tas sont stocks dans un tableau dans lequel chaque cl estgarantie suprieure celle situes deux autres positions spcifiques. Ces dernires sont

40


41/54

leur tour chacune suprieure deux autres cls, etc. Ce rangement est visualisable sous

forme dun arbre binaire ayant des artes (liens) menant de chaque nud aux deux nuds

infrieurs.


Limplmentation de cet algorithme utilise comme mthodes:

-Le SiftDown:

La procdure de sifts est une procdure efficace qui peut tre utilise pour insrer des

lments dans un heap, ou pour enlever des lments. Il existe deux techniques de sifting:

le sift up et le sift down

Mais dans ce projet on utilise le sift down qui fonctionne de la manire suivante :

Etant donne un heap dans sa reprsentation implicite dans la forme dun tableau a avec N

lments, nous faisons un sift down de llment avec indice i comme suit :

Si le sommet i est une feuille (cest--dire quil na pas de fils) ou sil est plus grand que sesdeux fils on ne fait rien. Sinon on change le sommet i avec le plus grand de ses fils et on

recommence ce procd de faon rcursive

-Le BottomUpHeapCreate:

Elle permet de crer un heap(tas) partir du tableau de longueur N en utilisant la mthode

SifDown

-HeapSort

Comme on a un tas, on est sr que llment a[0] est le plus grand lment du tableau.

Ainsi chaque tape i>=1,nous remplaons la racine de larbre courant (i.e.,a[0])avec a[N-

1], et nous faisons un siftdown de llment a[0] dans larbre donn par les lments

a[0],.,a[N-i-1].

La mthode implique trois phases :

Un tableau a de longueur N peut tre considr comme un arbre binaire avec racine

de la faon suivante (reprsentation implicite) : les sommets de larbre

correspondent aux positions 0, 1,2,.N-1

La racine est la position 0, et pour tout sommet i, ses fils sont en positions 2i+1 et

2i+2, condition que ces valeurs soient plus petites que N.

- Construction du tas (heap) partir de larbre binaire

Ce tableau est un tas(heap) si :

a[i]>=a[2i+1] et a[i]>=a[2i+2 ] avec 2i , 2i+1


42/54

- Une fois quon a un tas, on peut appliquer maintenant la mthode qui consiste qui

consiste changer la racine avec le dernier lment du tas. Cette manire de faire

est dun grand intrt car on sait que llment maximal du tableau se trouve la

racine. Ds lors on a plus un tas, on le reconstruit de nouveau en siftant depuis la

racine jusquen lavant dernier lment quon vient de dplacer en bas de larbre.

(c'est--dire on descend llment de la racine tout en vrifiant chaque noeud, la

proprit dun heap. On reprend le mme principe jusqu ce quil reste un seul

lment dans larbre. Ce nest pas toujours facile de dfinir un mthode trsclairement, on voit mieux sur lexemple ci-dessous.

42


43/54

Voici une tape dapplication de heapsort (tri par tas) dcrit ci-dessus

Code en langage C de la mthode HeapSort

#include "SiftDown.cpp"

43


44/54

#include "TopDownHeapCreate.cpp"

void HeapSort(int *a, int N,long long *comparaisons,long long *echanges) {

TopDownHeapCreate(a,N,comparaisons,echanges);

for (int i = N-1 ;i>=1 ; i--){

swap(a,0,i,echanges);

SiftDown(a,0,i-1,comparaisons,echanges);

}

}

Code en langage C de la mthode BottomUpHeapCreate

void BottomUpHeapCreate(int*a,int N){

int i;

for (i =floor((N-1)/2);i


45/54

while (Swapped && i>=0 && ia[2*i+2]){

(*comparaisons)++;

j= 2*i+1;}

else

j= 2*i+2;

if(2*i+2 >= ind_max){

(*comparaisons)++;

j=2*i+1;

}

if(2*i+1 >= ind_max){

(*comparaisons)++;j=i;

}

if (a[i]


46/54


-Voir annexe 7


Heapsort

0

10000000

20000000

30000000

40000000

50000000

60000000

70000000

80000000

1 100 10000 1000000

N

NbreEchange-

Comparaison


des cas)




des cas)

Heapsort

0.0000001.0000002.0000003.0000004.0000005.0000006.0000007.0000008.0000009.000000

1 100 10000 1000000

N

NbreEchange-

Comparaison

/NlogN


des cas)




des cas)

46


47/54

0.01000

0.10000

1.00000

10.00000

100.00000

1000.00000

10000.00000

1 100 10000 1000000

Taille du tableau

temps(m

s)


des cas)




des cas)

0.000000

0.010000

0.020000

0.030000

0.040000

0.050000

0.060000

0.070000

0.080000

1 100 10000 1000000

N

t(ms)/Nlog-n


des cas)




des cas)

3.3.5 Observations et Conclusions sur lAlgorithme du Heapsort

Le tri par tas est une technique de tri qui est comparable au tri rapide (quicksort) pour le

temps moyen. Lutilisation dun tas permet de trier N lments en temps de lordre de

Nlog(N), indpendamment de la nature des donnes (ici des tableaux) O(NlogN), ceci

sans mmoire auxiliaire car on peut utiliser le tableau trier pour reprsenter le tas.

Les tests effectus sur le heapsort nous permet de conclure quil est devient mauvais sur des

tableaux presque tri, ce se justifie par son fonctionnement. On pourrait donc penser une

amlioration de cet algorithme en tenant compte si certains sommets sont bien placs.

47


48/54

3.4 Comparaisons des Tris Sophistiqus

NLog(N) Sorting

0.00000

200.00000

400.00000

600.00000

800.00000

1000.00000

1200.00000

1400.00000

0 5000

0

1000

00

1500

00

2000

00

2500

00

3000

00

3500

00

4000

00

4500

00

5000

00

5500

00

6000

00

N

Tmoy

QuickSort

3-Mediane

HeapSort

Tout ce qui suit se rsume sur la courbe de NlogNSorting ci-dessus.

Bien entendu, il sagit de savoir quand choisir le tri par tas, le tri rapide ou le tri 3-mdiane

pour telle ou telle application. Le choix entre heapsort et tri rapide (quicksort) revient

privilgier les performances dans le cas moyen ou dans le pire des cas. En gnral, rendre

heapsort plus rapide que quicksort nest pas gagn davance car la version amliorer dequicksort (3-mdiane) relve ce dfi.

Les rsultats des tests empiriques en annexe montrent que heapsort est plus lent que

quicksort dans le moyen des cas mais il est mieux de choisir heapsort pour les types de

tableaux tris dans lordre inverse o quicksort dgnre en O(N^2).

4. CONCLUSION GENERALE

Durant le projet, diffrents algorithmes de tri ont t tudis et compars. La question qui

se pose maintenant est de dterminer si lon peut esprer trouver une mthode de tri

meilleure que toutes les autres. Ce nest pas aussi simple. Il faut videmment prciser le(ou les) critre(s) selon le(s)quel(s) on compare les mthodes et pour quelles mthodes ce

critre est significatif.

Pour obtenir des rsultats intressants, on va se restreindre la classe Tc des algorithmes de

tri qui oprent uniquement par comparaisons deux deux des cls des lments trier. De

plus, on fait lhypothse que toutes les cls du tableau trier sont diffrentes.

Dans ces conditions, comme le confirme les diffrents tests exprimentaux,on en dduit

que :

La complexit, en nombre de comparaisons, aussi bien en moyenne quau pire, de tout

algorithme de la classe Tc est dordre de grandeur suprieur ou gal Nlog(N) .

On peut en dduire que les algorithmes de tri rapide(quicksort) et tri par tas(heapsort) sont

optimaux en moyenne; le tri par tas est de plus optimal dans le cas le pire(une entre detableaux tris dans lordre inverse). Mais ceci est vrai seulement partir dune certaine

48


49/54

valeur de la taille du tableau. Par consquent, il est important de savoir quon ne gagne pas

grande chose utiliser les tris compliqus (rapides) pour trier les tableaux qui ont moins

dune centaine dlments.

Pour analyser les algorithmes de tri, on sest bas sur deux oprations fondamentales: les

comparaisons et les mouvements. Le rsultat nonc ci-dessus porte seulement sur les

comparaisons. Le nombre de mouvements ne doit pas tre nglig pour autant : Si onconsidre par exemple le tri par Insertion, il est optimal dans le pire des cas en nombre de

comparaisons mais le nombre de transfert est en O(N^2). Pratiquement le temps total

dexcution de lalgorithme est proportionnel N^2.

Le tri par Shell requiert peu de code et se montre comptitif pour des tableaux de grandes

tailles en face des tris performants (quicksort, tri par tas) qui sont deux fois plus rapides,

except pour de grands N mais qui sont beaucoup plus complexes implmenter.

En rsum si vous avez besoin dune solution rapide pour un problme de tri et que vous

ne voulez pas vous occuper de linterfaage dun systme de tri, vous pouvez utiliser le tri

shell et reporter plus tard le travail supplmentaire pour une mthode plus sophistique.

Pour mieux voir le comportement des divers algorithmes tudis dans ce projet dans le pire

des cas, moyen des cas et meilleur des cas, on a procd une reprsentation sous forme

dhistogramme ci-dessous.

49


50/54

Tableau non tri pour N=100000

Tmoy Bubble; 25827.4

Tmoy Selection; 9662.3Tmoy Insertion; 8510.4

Tmoy Heapsort; 99.8

Tmoy QuickSort; 18.6

Tmoy 3Mediane; 7.9

0

5000

10000

15000

20000

25000

30000

100000

Temps

Tmoy Bubb

Tmoy Sele

Tmoy Inser

Tmoy Heap

Tmoy QuicTmoy 3Me

50


51/54

Tableau tr i en sens inverse pour N=100000

Tmax Bubble; 30946

Tmax Selection; 10632

Tmax Insertion; 17095

Tmax Heapsort; 91.2

Tmax QuickSort;

10448.9

Tmax 3Mediane; 16.80

5000

10000

15000

20000

25000

30000

35000

100000

Temps

Tmax Bubble

Tmax Selection

Tmax Insertion

Tmax Heapsort

Tmax QuickSort

Tmax 3Mediane

51


52/54

Tableau no n tr i (alatoire ) pour N=250

Tmoy Bubble; 1

Tmoy Selection; 0.3

Tmoy QuickSort; 0.1

Tmoy Insertion; 0.2Tmoy Heapsort; 0.2

Tmoy 3Mediane; 0.1

0

0.2

0.4

0.6

0.8

1

1.2

250

Temps

Tmoy Bubble

Tmoy Selection

Tmoy Insertion

Tmoy Heapsort

Tmoy QuickSort

Tmoy 3Mediane

Tableau non tri (alatoire) pour N=250

Tmoy Bubble; 1

Tmoy Selection; 0.3

Tmoy QuickSort; 0.1

Tmoy Insertion; 0.2Tmoy Heapsort; 0.2

Tmoy 3Mediane; 0.1

0

0.2

0.4

0.6

0.8

1

1.2

250

Temps Tmoy Bubb

Tmoy Sele

Tmoy Inser

Tmoy Hea

Tmoy Quic

Tmoy 3Me

52


53/54

5. ANNEXE DES RESULTATS DES TESTS

-

Annexe1 : Rsultats des tests de Tri Bulles(BubbleSort)

-

Annexe2 : Rsultats des tests de Tri par Slection(SelectionSort)- Annexe1 : Rsultats des tests de Tri par Insertion(InsertionSort)

- Annexe1 : Rsultats des tests de Tri par Shell (ShellSort)

- Annexe1 : Rsultats des tests de Tri rapide(quickSort)

- Annexe1 : Rsultats des tests de Tris trois-mdiane(three-median)

- Annexe1 : Rsultats des tests de Tri par tas(heapSort)

53


54/54

Documents

ramatouFinal