Newer
Older
[Grille d'évaluation P4z](https://docs.google.com/spreadsheets/d/1VXeO91rhy04xa0p8KUhWliFl228utHaDir8MstO5Z-M/edit?usp=sharing
Le tri rapide pose un problème de rapidité dès lors que le tableau n'est pas aléatoire.
Comment pouvons nous observer l'impact des valeurs d'un tableau sur ce tri rapide ?
Les programmes sont séparés en 4 tris :
- [le tri rapide](scripts/maintrirapide.c)
- [le tri fusion](scripts/maintrifusion.c)
- [le tri insertion](script/maintriinsertion.c)
- [le tri à bulle](scripts/maintribubble.c)
Usage : <type> <TailleTableau>
./rapide Aleatoire 5000
./bulle Trie 5000
./insertion Reverse 5000
./fusion Aleatoire 5000
```
### Environnement de test
Description de la plateforme de test
```
Script permettant de produire les données temps & mémoire :
[temps.sh](scripts/temps.sh)
Script permettant de produire les données d'écritures :
[stats.sh](scripts/stats.sh)
Afin de lancer les scripts analysant les temps & consommation mémoire :
```
Dans le dossier scripts:
./temps.sh > temps.dat
./stats.sh > stats.dat
./rapide Aleatoire 5000
./bulle Trie 5000
./insertion Reverse 5000
./fusion Aleatoire 5000
Afin de lancer un tri seul :
```
Dans le dossier scripts:
./rapide Aleatoire 5000
./bulle Trie 5000
./insertion Reverse 5000
./fusion Aleatoire 5000
Tableau Trié :
Tableau Tri Inversé :
Tableau Aléatoire :
Tableau Trié :
Tableau Tri Inversé :
Tableau Aléatoire :
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#### Analyse des performances de temps et de mémoire.
##### Analyse des performances du temps d'éxécution.
###### Tableaux aléatoires :
###### Remarques
Les tris fusions et rapides de plus près :
On constate que la courbe du tri par **insertion** marque un plus grande évolution que les deux autres. On remarque cependant que le tri **rapide** prend progressivement de plus en plus de temps alors que le tri **fusion** reste à une vitesse constante quel que soit la taille du tableau. De précédents tests on été effectués avec des tableaux de taille 300 000 mais cela ne valait pas le coup car les temps d'executions dépassaient la minute pour le tri par **insertion** .
###### Conclusion
D'après la courbe on remarque que le tri **rapide** est plus rapide que le tri **fusion**
Le tri **insertion** devient de plus en plus long en fonction de la taille du tableau
##### Tableaux triés :
###### Remarques
Les tris insertions et insertion de plus près :
On constate que la courbe du tri par **rapide** marque une plus grande évolution que les deux autres tris. On remarque cependant que le tri **insertion** est maintenant beaucoup plus optimal en termes de temps, comme l'était le tri **fusion** qu'aux tests avec des tableaux aléatoires. Le tri **fusion** reste quasiment aussi constat.
###### Conslusion
D'après la courbe on remarque que le tri **insertion** est plus rapide que le tri **fusion**
Le tri **rapide** devient de plus en plus long en fonction de la taille du tableau
##### Tableaux inversés :
###### Remarques
On constate que les courbes des tris **rapide** et **insertions** s'envolent plus la taille du tableau est conséquente. Le tri **fusion** reste constant comme dans les deux autres types de tableaux.
###### Conslusion
Le tri **fusion** est le seul tri optimal en termes de temps d'éxécution avec un tableau inversé.
***
#### Analyse de la mémoire occupée
##### Tableaux aléatoires :
###### Remarques
Cette fois ci, on remarque que c'est le tri **fusion** qui consomme le plus de ressources alors que les tris **insertion** et **rapide** possèdent une consommation assez similaire.
L'allure de la courbe de tri **fusion** peut être expliquée par les allocations mémoires nombreuses dans l'algorithme.
Chaque appel de la fonction **fusion** alloue 2 emplacements, et la fonction est appelée plusieurs fois. Cela peut donc aussi expliquer l'allure linéaire et constante de la courbe.
###### Conclusion
D'après la courbe on remarque que le tri **fusion** n'est pas efficient en terme de mémoire.
préalables et ce qu'ils ne permettent pas de vérifier.
## Etude approfondie
### Hypothèse
### Protocole expérimental de vérification de l'hypothèse
Nous allons observer l'évolution des perfomances du tri rapide en fonction du type de tableau qui lui est donné.
Nous allons prendre un tableau presque trié pour l'expérience.
Sur ce graphique nous observons que le tri **rapide** sur un tableau semi trié est aussi lent que sur un tableau trié entièrement. Les deux opérations de tris utilisent donc quasiment le même temps CPU.
### Discussion des résultats expériment
On remarque qu'avec tableau trié dont le pivot est la dernière valeur, donc le plus grand nombre, l'algorithme de tri rapide va effectuer chaque permutation avec lui même. Ce qui impacte sur le nombre d'écritures et le temps d'éxécution.
Le problème réside dans l'algorithme du tri rapide. Un moyen d'optimiser l'algorithme serait peut être d'empècher de permuter les valeurs entre elles.
On peut aussi effectuer des recherches et tenter une modification du tri rapide, en modifiant son pivot afin d'observer toute évolution.