Mini-Projet 2 - Les Algorithmes de Tri
Mini-Projet 2 - Les Algorithmes de Tri
Mini-Projet 2 - Les Algorithmes de Tri
Master I
Systèmes Informatiques Intelligents
Complexité des Algorithmes
Mini Projet II
BIDA Ikram
BOUKERBOUB Abderrahim
Groupe 2
Environnement du travail
Matériel :
L'implémentation des algorithmes a été réalisée sur un micro-ordinateur ayant la configuration matérielle
suivante :
- Un micro processor Intel(R) Core(TM) i3-2328M 2.20GHz.
- Une mémoire de 4.00 GB de RAM.
- Une résolution de 1366x768.
- Windows 7 édition intégrale 64 bit.
Logiciel :
Afin d'implémenter nos algorithmes, nous avons opté pour :
Le langage C++ comme langage de programmation (Code :: Blocks 10.05) .
Introduction :
La théorie de la complexité algorithmique s'intéresse à l'estimation de l'efficacité des algorithmes.
Elle s'attache à la question :
entre différents algorithmes réalisant une même tâche, quel est le plus rapide et dans quelles conditions ?
Trier des objets est à la fois un problème fondamental de l’algorithmique, comme étape de prétraitement
d’algorithmes plus complexes ou pour ordonner des structures de données.., et une bonne illustration de
différent paradigmes de programmation.
Analyse et complexité :
Le traitement nécessite deux boucles for imbriquées dont l'ordre de grandeur du nombre
d'itérations est n.
On peut donc dire que la complexité dans le pire des cas du tri par sélection est d’ordre O (n2).
Tri par insertion
Algorithme :
Var i, k, c, p : entiers ;
Debut
Pour i:=1 à n faire
C :=T[i];
P :=0;
Tantque (T[p]<c) faire
P :=p+1 ;
Fintq
Pour k=i-1 à p pas k:=k-1 faire
//on décale les nombres
T[k+1]=T[k];
Fait;
T[p] :=c; //on écrit l'élément
Fait ;
Fin
Analyse et complexité :
Comme précédemment (Tri sélection), la complexité est en O(n²). ( deux boucles imbriqués )
Tri par bulle
Algorithme :
Debut
flag :=1;
Tantque (flag) faire
flag : =0;
i : =0;
Tantque (i<n-1) faire (n fois)
//si élément est supérieur au suivant
Si (T[i]>T[i+1]) alors
c=T[i]; //on échange
T[i]=T[i+1]; //les deux
T[i+1]=c; //nombres
flag=1;
Finsi ;
i :=i+1 ;
Fintq
Fintq ;
Fin
Analyse et complexité :
Le pire cas (n itérations) est atteint lorsque le plus petit élément est à la fin du tableau. Donc Le
nombre total de comparaisons est majoré par n*(n+1)/2.
On peut donc dire que la complexité dans le pire des cas du tri par insertion est d’ordre O (n2).
Tri rapide
jjd un élément du tableau appelé pivot.
Choisir
Ordonner les éléments du tableau par rapport au pivot c.-à-d. mettre les éléments plus petit
que le seuil à gauche du seuil et les éléments plus grands à droite.
Appeler récursivement le tri sur les parties du tableau à gauche et à droite du pivot.
Algorithme
Analyse et complexité :
La complexité moyenne en O(n.log(n)) n'est atteinte que lorsque les pivots successifs divisent la liste
en deux sous-listes de taille à peu près équivalente.
Dans le pire des cas (par exemple le pivot choisi est systématiquement à chaque fois la plus grande
valeur) on montre que la complexité est en O(n²).
Choix du pivot
La partie sensible qui influe sur la complexité de l’algorithme du tri rapide est la méthode du choix du
pivot.
En effet, il existe plusieurs méthodes pour ce choix dans notre projet nous avons évalué les 3
méthodes suivantes :
Pivot arbitraire : on prend toujours le premier élément du sous-tableau courant (on peut aussi
choisir le dernier élément ou l’élément central) comme pivot.
Pivot médiane : on choisit la valeur médiane entre le premier élément, l’élément central et le
dernier élément du sous-tableau courant.
Comparaison entre les 3 méthodes : (Moyenne du temps en secondes de 5 exécutions pour chaque
longeur)
Remarque : Le tri rapide s’exécute dans un temps très petit, nous avons donc choisi ces longueurs
pour pouvoir voir la différence entre ces 3 méthodes.
Comparaison entre les méthodes du choix du pivot
0,3
0,25
Temps d'exécution en secondes
0,2
0,15
0,1
0,05
0
500000 600000 700000 800000 900000 1000000
Longeur du tableau
Arbitraire Aléatoire Médiane
Conclusion
D’après ces résultats on peut conclure que la méthode la plus rapide est le choix du pivot de façon
arbitraire. Nous avons donc exécuté nos tests sur le tri rapide avec cette méthode.
Tri par fusion
On divise le tableau T à trier en deux tableaux qui ont à peu près le même nombre
d'éléments : T1 et T2 ;
On règne : on trie récursivement les deux tableaux T1 et T2 à l'aide du tri fusion.
On combine : on fusionne les deux séquences triées pour produire le tableau trié.
Algorithme
Analyse et complexité :
La taille des données est évidement le cardinal n du tableau à trier , il n’y a pas lieu de distinguer de
meilleur ou de pire cas , le processus récursif ne dépend pas de l’instance mais uniquement de sa
taille n .
Si n=1 => l’algorithme est on O(1) ;
Sinon Si n>1
Calcul de milieu O(1) ;
2 appels récursifs 2* T (n/2) ;
Fusion en O(n) ;
Var i : entier
Début
organiser(T, n); i=n-1
Tantque (i>0) faire
echanger(T, 0, i); //la dernière valeur va être remplacé par la
//racine la plus grande valeur qui se trouve au début du tableau
redescendre(T, i, 0) ; i :=i-1 ;
Fintq
Fin
Analyse et complexité :
Le tri par tas consiste à :
• transformer le tableau de n éléments en un tas : de complexité O(n)
• puis extraire les éléments un à un. O(n log n).
2- Les Fonctions de tri en C++
Tri par sélection
Pire cas :
les Tris (sélection, insertion et bulle) , les valeurs seront triées d’une façon inversée Comme suit :
Moyen cas :
Les tris (rapide, fusion , tas ) ,Les valeurs seront mélanger ( générer par un random ) comme suit :
Enfin en sortie -pour chaque taille de tableau dans l’intervalle I-, on obtient des fichiers
contenants la moyenne de temps d’exécution -de 5 tests sur un même algorithme - dans
sortie_[taille de tableau] pour le pire cas et dans sortie_MOYEN_[taille de tableau]
Pire cas :
Moyen cas
Nombre d’éléments Tri par sélection Tri par insertion Tri par bulle
10000 0.396000 0.193200 0.568600
11000 0.477600 0.234400 0.693000
12000 0.569400 0.285000 0.823000
13000 0.672400 0.329000 1.019000
14000 0.850800 0.410400 1.201800
15000 1.046200 0.478000 1.427200
16000 1.091600 0.526800 1.529400
17000 1.198200 0.583800 1.716200
18000 1.359400 0.655400 1.943200
19000 1.528600 0.774800 2.210000
20000 1.709800 0.805800 2.385600
21000 1.853200 0.892800 2.632600
22000 2.015200 0.978000 2.873200
23000 2.197400 1.075800 3.189000
24000 2.385800 1.172000 3.463600
25000 2.608000 1.282600 3.744200
26000 2.789000 1.367000 4.055200
27000 3.068800 1.469000 4.438600
28000 3.258200 1.577400 4.665600
29000 3.501000 1.727400 5.041600
30000 3.708400 1.828600 5.352400
31000 3.959800 1.933600 5.768400
32000 4.264600 2.081000 6.147800
33000 4.526800 2.213400 6.541600
34000 4.858400 2.336400 7.662400
35000 6.032600 2.691800 7.271600
36000 5.418800 2.611800 7.739800
37000 5.692200 2.759600 8.144201
38000 5.992400 2.888200 8.536800
39000 6.286000 3.089600 9.088400
40000 6.664200 3.204400 9.508600
41000 7.075800 3.395000 10.013000
42000 7.332800 3.582600 10.675200
43000 8.736800 4.127000 11.123200
44000 8.041199 3.872400 11.506200
45000 8.288600 4.086600 12.035200
46000 8.659200 4.255600 12.543201
47000 9.064799 4.500400 13.263800
48000 9.629600 4.698200 13.925600
49000 10.636200 5.660800 14.278799
50000 10.306200 5.021200 14.759201
51000 10.729800 5.199800 15.359599
52000 11.398399 5.885200 19.305800
53000 13.907201 6.620200 18.170798
54000 11.989400 5.835200 18.112999
55000 14.693800 6.946400 17.852199
56000 12.951201 6.305800 18.534200
57000 13.341800 7.421000 23.350800
58000 16.898599 8.159000 23.843199
59000 17.436200 8.291599 24.297200
60000 17.508600 8.488200 22.623801
61000 17.886600 8.798600 25.888000
62000 18.654201 8.104400 22.699400
63000 18.014801 9.348200 27.552600
64000 16.847400 8.195000 24.171599
65000 21.275400 9.949599 29.009799
66000 17.873598 8.713000 25.716602
67000 20.914000 10.602600 31.306000
68000 20.019600 10.387800 32.432599
69000 23.059799 10.860400 28.116602
70000 22.169600 11.562400 34.719998
71000 24.355400 11.888400 30.192999
72000 24.165601 12.223000 32.828799
73000 24.460201 12.566799 34.507599
74000 24.968399 12.917400 34.640601
75000 25.669400 13.252600 35.112399
76000 26.917599 13.635399 36.038199
77000 26.525400 13.990800 38.363199
78000 28.357999 14.361600 38.159198
79000 29.176999 14.746600 37.890002
80000 30.023798 15.295000 45.029999
81000 30.469800 15.480200 41.134598
82000 30.531400 15.889200 46.776602
83000 29.367001 15.801599 45.720599
84000 34.033801 16.649800 45.581799
85000 32.447598 17.058200 50.100201
86000 30.336398 17.818401 46.702805
87000 39.301999 17.863800 49.252399
88000 37.359201 18.268001 51.260400
89000 38.289398 18.708401 50.277600
90000 37.419000 19.356400 53.851398
91000 38.425998 18.981201 48.940799
92000 39.777200 19.051199 50.050998
93000 40.708600 19.608801 51.115601
94000 42.247601 20.454401 52.222205
95000 42.294400 21.599001 60.445398
96000 43.532199 18.685799 59.029004
97000 43.384402 18.866199 58.226404
98000 46.365198 19.597400 56.772998
99000 47.176202 20.212601 62.929999
100000 48.756598 23.932600 65.259399
101000 50.386801 24.364999 65.871997
102000 48.511798 21.762999 66.565601
103000 43.479001 21.248199 62.652399
104000 53.124194 22.866400 66.591998
105000 51.205200 24.307999 70.899603
106000 51.483398 22.525800 71.442999
107000 52.443396 22.962599 67.714001
108000 55.139203 23.369200 71.275000
109000 52.102002 24.008801 90.606409
80
70
60
50
40
30
20
10
0 100000
103000
106000
109000
25000
28000
31000
34000
37000
40000
10000
13000
16000
19000
22000
43000
46000
49000
52000
55000
58000
61000
64000
67000
70000
73000
76000
79000
82000
85000
88000
91000
94000
97000
Taille du tableau
0,08
Temps d'exécution en secondes
0,07
0,06
0,05
0,04
0,03
0,02
0,01
0 100000
103000
106000
109000
28000
52000
76000
10000
13000
16000
19000
22000
25000
31000
34000
37000
40000
43000
46000
49000
55000
58000
61000
64000
67000
70000
73000
79000
82000
85000
88000
91000
94000
97000
Taille du tableau
Nombre d’éléments Tri par sélection Tri par insertion Tri par bulle
10000 0.506600 0.192800 0.628000
11000 0.575000 0.232000 0.762000
12000 0.693000 0.274600 0.904400
13000 0.813000 0.322000 1.068200
14000 0.946000 0.373000 1.255000
15000 1.099600 0.428600 1.437200
16000 1.227000 0.487400 1.651200
17000 1.399000 0.549400 1.866600
18000 1.569200 0.616600 2.093600
19000 1.742400 0.688600 2.326000
20000 1.930800 0.762000 2.709000
21000 2.242800 0.882400 3.018800
22000 2.448000 0.967800 3.332600
23000 2.675400 1.059800 3.624800
24000 2.979800 1.159000 3.971000
25000 3.157000 1.249800 4.288400
26000 3.388600 1.352000 4.652000
27000 3.675000 1.458600 5.009200
28000 3.952000 1.574000 5.576800
29000 4.287200 1.689000 6.323200
30000 5.367200 2.132400 7.435800
31000 5.754200 2.057200 6.659800
32000 5.149800 2.042200 7.129200
33000 6.736800 2.579200 8.924001
34000 6.894800 2.745800 9.608800
35000 7.286200 2.913200 9.207400
36000 6.405200 2.585200 9.216000
37000 8.092999 3.246600 10.856200
38000 7.122000 2.905200 10.410400
39000 8.784200 3.619800 12.798600
40000 9.865001 3.887200 13.249800
41000 9.843000 4.009800 14.145000
42000 10.609801 4.258800 14.983400
43000 11.030000 4.443400 15.239600
44000 11.116199 4.149600 13.465800
45000 10.147400 4.774000 16.497601
46000 10.986401 4.298200 14.626801
47000 11.037600 5.194600 17.923801
48000 11.464999 4.594400 15.960199
49000 11.509801 5.361600 19.554800
50000 13.571400 5.005000 17.275000
51000 12.382401 5.221200 18.189999
52000 15.187801 6.351600 21.044400
53000 13.384200 5.610000 21.464001
54000 16.479599 6.958400 24.088000
55000 15.194800 6.046800 20.924400
56000 14.772400 7.764999 23.724399
57000 15.927800 7.770000 27.254199
58000 18.648001 7.517599 23.313400
59000 17.793600 7.487400 24.141400
60000 16.641399 7.179199 28.196399
61000 20.537001 8.874600 27.457401
62000 17.711000 7.668600 26.744598
63000 19.746001 9.322600 27.750201
64000 19.566200 9.616200 28.884000
65000 19.153000 8.422000 29.325998
66000 19.778400 8.686600 30.208600
67000 21.159000 10.650600 31.887601
68000 20.799400 9.226400 32.409000
69000 22.756400 9.967001 36.103000
70000 23.128598 10.934799 37.670001
71000 24.157600 10.082000 42.626801
72000 25.776001 11.586600 38.746002
73000 27.294400 12.996600 48.607401
74000 31.155200 13.805800 50.321600
75000 32.604599 14.248199 51.525604
76000 32.977399 14.655800 53.196997
77000 33.895801 14.957800 54.058002
78000 34.122400 15.267200 64.195398
79000 34.719403 15.684399 56.733398
80000 35.563599 16.072000 69.051404
81000 46.922998 16.557599 58.087000
82000 47.764401 16.963802 71.554596
83000 37.934601 27.957999 75.053796
84000 38.732999 28.147202 76.344604
85000 40.011798 18.037799 74.076801
86000 37.406799 17.705800 61.212799
87000 37.839999 17.875999 58.479199
88000 39.887799 16.021399 61.165204
89000 37.311200 15.966200 60.838202
90000 38.141602 16.422998 61.040601
91000 40.784799 19.799400 66.026801
92000 40.585999 17.424200 68.685400
93000 43.245599 20.605402 64.343604
94000 42.265201 17.777400 70.994202
95000 37.358798 22.121599 71.657800
96000 43.633798 18.683400 74.107794
97000 47.114200 22.484399 72.707800
98000 46.520001 23.876199 86.775201
99000 50.863400 24.304599 87.997595
100000 51.596802 24.809802 87.713403
101000 52.045599 25.167599 99.937000
102000 53.456799 25.755399 92.874603
103000 62.087402 26.005798 93.113000
104000 52.091797 25.836200 89.896600
105000 52.493799 22.120000 92.200000
106000 54.308398 23.794800 78.455798
107000 50.378201 22.858800 80.101196
108000 53.736200 23.310199 84.443396
109000 53.620197 28.676001 94.969598
Comparaison entre les 6 algorithme de tri -Moyen cas-
109000
106000
103000
100000
97000
94000
91000
88000
85000
82000
79000
Temps d'execution en seconde
76000
73000
70000
67000
64000
61000
58000
55000
52000
49000
46000
43000
40000
37000
34000
31000
28000
25000
22000
19000
16000
13000
10000
0 10 20 30 40 50 60 70 80 90 100
Taille de tableau
Pire cas :
Pour les tris rapide , tas et fusion on a pris les même temps que le moyen cas , en gros ces 3 tris n’ont pas
de pire cas .
Comparaison entre les 6 algorithme de Tri
109000
106000
103000
100000
97000
94000
91000
88000
85000
82000
79000
Temps d'execution en seconde
76000
73000
70000
67000
64000
61000
58000
55000
52000
49000
46000
43000
40000
37000
34000
31000
28000
25000
22000
19000
16000
13000
10000
0 10 20 30 40 50 60 70 80 90 100
Taille du tableau
tri par tas tri fusion tri rapide tri bulle tri insertion tri selection
Conclusion
L'algorithme le plus efficace est le tri rapide, puis viennent le tri par tas et le tri fusion. Pour
les trois plus lents, on remarque que le «pire» d'entre eux est, en moyenne, le tri à bulles, puis
viennent le tri par sélection et le tri par insertion (avec des écarts de performance toutefois très
nets entre eux trois).
Ces temps expérimentaux confirment les résultats théoriques : les méthodes fusion, tas ou
Rapide ont une complexité en O(n log2(n) ).
Remarque : Chaque valeur mise dans les tableaux précèdent est la moyenne de cinq tests
effectués pour chaque tri. (Voir l’algorithme tri_c_plus dans le répertoire Algorithme_Tri)
Exemple d’une exécution
Taille de tableau = 101000 dans le moyen cas