Ressources

Algorithmes de tris

Introduction

Les tris sont une des opérations les plus souvent effectuées par les ordinateurs, que ce soit dans les applications professionnelles (gestion des bases de données, des opérations bancaires...), la compression des données ou les jeux vidéo. On estime qu’un quart des cycles d’horloge des ordinateurs sont consacrés à des opérations de tri. Le coût énergétique de ces opérations de tris représente près de 2% de la consommation totale d’électricité en Europe. Sur des effectifs de plusieurs millions de données, les temps d’exécution des différents algorithmes de tris varient entre une dizaine de secondes et une dizaine de jours. D’où l’importance d’optimiser l’efficacité de ces algorithmes.

Bien que la plupart des algorithmes de tri soient connus depuis longtemps, la recherche sur leur optimisation est encore très active. La dernière amélioration de l’algorithme de tri "Quicksort" par Bentley & Sedgewick, considéré comme indépassable au niveau des tris par comparaison, date seulement de 2002.

Les algorithmes de tris se divisent en deux grandes catégories de complexité :

  • les tris rapides avec des temps d’exécution en  \(   n \times \lg \left(n\right) \)
  • et les tris lents avec des temps d’exécution quadratiques \(   n^{2} \)

À titre d’illustration, voici une comparaison des temps d’exécution pour ces deux catégories de complexité (sur la base arbitraire d'une milliseconde par opération élémentaire) :

\(  \large n \)\(  \large n \times \lg \left(n\right) \)\( \large  n^{2} \)
10 ms33 ms100 ms
100 ms664 ms10 s
1s10 s16 mn 40 s
10 s2 mn 13s1 jour 3h 46 mn
1 mn 40s27 mn 41s115 jours 17h
16 mn 40s5h 32 mn31 ans 259 jours

On voit donc bien que même sur un ordinateur très puissant, la complexité de l'algorithme reste primordiale dans la détermination du temps d'exécution.

Dans les tris lents on trouve : tri par insertion, le tri par sélection, le tri par bulles...
Dans les tris rapides, on dénombre : le tri fusion, le  tri rapide (Quick Sort)...

Les vidéos suivantes, présentent sous forme de chorégraphies, ces principaux algorithmes de tris :

Tri par insertion

Tri par sélection

Tri par bulles

Tri Shell

Tri fusion

Tri rapide

À voir : "A visualization of the most famous sorting algorithms"