Algorithmique/Les tris
Introduction
modifierLes algorithmes de tri sont utilisés dans pleins de domaines différents. Ils peuvent être utilisés pour trier des notes, des tailles, et bien d'autres encore. Si vous avez déjà joué aux cartes, vous avez sûrement déjà trié un paquet de carte pour voir si il était complet. L'ordre du paquet, ainsi que la façon dont vous avez déplacé chaque carte dans le paquet peut constituer un algorithme de tri.
La plupart du temps, on va considérer une structure de données, tel un tableau, et c'est sur cette structure que l'on va faire nos tris.
Au cours de ce chapitre, nous allons étudier quelques algorithmes, qui ont des utilités différentes. En effet, en fonction des données que nous aurons à traiter, nous n'utiliserons pas le même algorithme.
Coût d'un tri
modifierLa première chose à prendre en compte quand on va faire des tri, c'est simplement quel sorte de données allons-nous trier ? Est-ce que les données sont très mélangés ? Avons-nous beaucoup ou peu de données à trier ? Ces questions ne sont pas anecdotiques, car même si les tris sont assez abstraits quand ils sont écrits sous la forme d'algorithme sur une page web, elles prennent toute leur importance quand il faut, par exemple, trier les habitants de l'Europe en fonction de leur âge. Étant données les plusieurs millions de données à trier, et que nous sommes limités par la puissance de calcul de nos ordinateurs, il vaut mieux utiliser un algorithme efficace.
Pour cela, il existe la notation de Landau qui nous permet d'étudier la complexité en temps et en espace ( c'est-à-dire combien de temps et de place est nécessaire ) des algorithmes de tri.
On peut considérer trois axes d'études :
- Conception : Existe-t-il des techniques générales ?
- Preuve de correction : Est-ce que, pour chaque entrée, l'algorithme termine en produisant la bonne sortie ?
- Efficacité : Avec les ressources disponibles en temps et en espace, est-ce optimal ? Peut-on faire mieux ?
Comme dit précédemment, il existe plusieurs algorithmes pour un même problème, et pour les étudier, il faut comparer leur complexité.
NB : Cette étude de complexité s'applique aux algorithmes de manière générale.
La complexité en espace
modifierC'est la mémoire nécessaire pour effectuer un calcul. Il existe deux types de mémoires :
- La mémoire incompressible, nécessaire pour stocker le résultat et les données,
- La mémoire auxiliaire, pour les calcules intermédiaires
Pour comparer deux algorithmes entre eux, on peut comparer leur utilisation de la mémoire auxiliaire. En effet, on traite les mêmes données, et on aura à priori le même résultat.
La complexité en temps
modifierC'est le temps nécessaire pour mener le calcul à son terme. Il est difficile à quantifier car cela va surtout dépendre de la machine que l'on utilise. Par convention, on estime ce temps par le nombre d'opérations élémentaires effectuées. Sur une machine donnée, le temps d'exécution sera plus ou moins proportionnel à ce nombre. Une opération élémentaire étant une opération dont le temps d'exécution est constant, comme par exemple l'affectation, la comparaison, opération arithmétique...
À titre d'exemple, un ordinateur à 3.2Ghz effectue 1017 cycles en 1 an.
| n | 10 | 100 | 103 | 106 | 109 | 10¹² |
|---|---|---|---|---|---|---|
| log2n | ||||||
| 10n | ||||||
| nlog2n | ||||||
| n2 | ||||||
| n3 | ||||||
| 2n |
Notation utilisées
modifierArticle en construction...
Les tri internes
modifierArticle en construction...
Les tri externes
modifierArticle en construction...
Exemples
modifierArticle en construction...[1]
Références
modifier
