Algorithme de tri

Il est évident que suivant la relation d'ordre considérée, une même collection d’objet peut donner lieu à divers arrangements, pourtant il est possible de définir un algorithme de tri indépendamment de la fonction d’ordre utilisée. Celui-ci ne fera qu'utiliser une certaine fonction d’ordre correspondante à une relation d’ordre qui doit permettre de comparer tout couple d'éléments de la collection.

Sommaire

1 Classification

1.1 Complexité algorithmique
1.2 Caractère en place
1.3 Caractère stable

2 Exemples d'algorithmes de tri

3 Liens externes

Classification

La classification des algorithmes de tri est très importante, car elle permet de choisir le type d’algorithme le plus adapté au problème traité, tout en tenant compte des contraintes imposées par celui-ci.

Les principales caractéristiques qui permettent de différencier les algorithmes de tri sont : la complexité algorithmique, les ressources nécessaires et le caractère stable.

Complexité algorithmique

La complexité algorithmique temporelle dans le pire des cas permet de fixer une borne supérieure du nombre d'opérations qui seront nécessaire à trier un ensemble de n éléments. On utilise pour symboliser cette complexité la notation de Landau : O.
La complexité algorithmique temporelle en moyenne : c’est le nombre d'opérations élémentaires effectué en moyenne pour trier une collection d’éléments. Elle permet de comparer les algorithmes de tris et donne une bonne idée du temps d'exécution qui sera nécessaire à l’algorithme ; on arrive à l'estimer avec une précision assez importante.
La complexité algorithmique spatiale (en moyenne ou dans le pire des cas) représente, quant à elle, l’utilisation mémoire que va nécessiter l'algorithme. Celle-ci peut dépendre, comme le temps d'exécution, du nombre de quantités à trier.

Dans la plupart des tris, T(n) = O(n²) bien que pour certains algorithmes, T(n) = O(n·log(n)).

On peut montrer que la complexité temporelle en moyenne et dans le pire des cas d’un algorithme basé sur une fonction de comparaison ne peut pas être meilleur que n·log(n)).

Le problème du tri consiste, étant donné une suite u = (u1, u2, ..., un) d’éléments d’un ensemble totalement ordonné (par exemple $\mathbb{N}$ ), à déterminer une permutation σ de 1, ..., n telle que : y = (uσ(1), 'uσ(2), ..., uσ(n)) soit triée. L'algorithme doit donc être en mesure de fournir toute les possibilités de permutation des termes de la suite, car il est équivalent de fournir la permutation σ que la suite triée y. Si l’on considère que les comparaisons sont les seules opérations élémentaires, le nombre de permutation de n éléments étant n! (factorielle n) et sachant que l’algorithme différencie deux cas à chaque comparaison, il faut que le nombre d’opérations élémentaires h soit tel que : $2^h \geq n!$ ainsi $h \geq n \cdot \log_2(n)$

Les tris qui ne demandent que n·log(n) comparaisons en moyenne sont dits optimaux.

Pour certains types de données (entiers, chaînes de caractères de taille bornée), il existe cependant des algorithmes plus efficaces au niveau du temps d'exécution, comme le tri comptage ou le tri radix. Ces algorithmes n'utilisent pas la comparaison entre éléments (la borne n·log(n) ne s'applique donc pas pour eux) mais nécessitent des hypothèses sur les objets à trier. Par exemple, le tri comptage et le tri radix s'appliquent à des entiers que l'on sait appartenir à l'ensemble [1, m] avec comme hypothèse supplémentaire pour le tri radix que m soit de la forme 2^k.

Caractère en place

Un algorithme est dit en place s'il n'utilise qu'un nombre très limité de variables et qu’il modifie directement le tableau qu’il est en train de trier. Ceci nécessite l’utilisation d'une structure de donnée adaptée (un tableau par exemple). Ce caractère est très important si on ne dispose pas d'une grande quantité de mémoire utilisable.

Caractère stable

Un algorithme est dit stable s'il garde l'ordre relatif des quantités égales pour la relation d'ordre.

Exemple, si on considère la suite d’éléments suivante :

(4, 1)  (3, 1)  (3, 7)  (5, 6)

que l'on tri par rapport à leur première coordonnée (la clé), deux cas sont possibles, quand l’ordre relatif est respecté et quand il ne l'est pas :

(3, 1)  (3, 7)  (4, 1)  (5, 6)   (ordre relatif maintenu)
 (3, 7)  (3, 1)  (4, 1)  (5, 6)   (ordre relatif changé)

Lorsque deux éléments sont égaux pour la relation d'ordre (c’est-à-dire qu'il ont la même clé), l'algorithme de trie conserve l'ordre dans lequel ces deux éléments se trouvaient avant son exécution. Les algorithmes de tri instables peuvent être retravaillés spécifiquement afin de les rendre stable, cependant cela peut être au dépend de la rapidité et/ou peut nécessiter un espace mémoire supplémentaire.

Exemples d'algorithmes de tri

Tri à bulles : Algorithme quadratique, T(n) = O(n²), en moyenne et dans le pire des cas, stable et en place ;
Tri par sélection : Algorithme quadratique, T(n) = O(n²), en moyenne et dans le pire des cas, qui trie sur place ;
Tri par insertion : Algorithme quadratique, T(n) = O(n²), en moyenne et dans le pire des cas, stable et en place. C'est le plus rapide est le plus utilisé pour un petit nombre de valeurs à trier ;
Tri rapide (quick sort) ;
Tri fusion (merge sort);
Tri par tas (heap sort) ;
Tri comptage : dans certaines conditions c'est un algorithme linéaire, T(n) = O(n), stable mais nécessite l'utilisation d'une seconde liste de même longueur que la liste à trier ;
Tri par base : c'est aussi un tri linéaire dans certaines conditions (moins restrictives que pour le tri par comptage), T(n) = O(n), stable mais nécessite aussi l'utilisation d'une seconde liste de même longueur que la liste à trier.

Liens externes

Mémoire de synthèse sur les algorithmes de tri

Les algorithmes de tri

à bulle · par sélection · par insertion · par tas · par base · rapide · fusion · comptage