Algorithmes de tri

Introduction

Les algorithmes de tri représentent une famille d'algorithmes d'une grande importance. Il s'agit de réorganiser les éléments d'une séquence de telle manière à ce que l'ordre entre les élément imposé par la séquence corresponde à l'ordre entre les éléments déterminé par le domaine de ces éléments.

Le domaine des éléments de la séquence doit donc être ordonné. Ici, nous traitons uniquement des domaines totalement ordonnés ce qui signifie que pour chaque paire d'éléments du domaine x et y, soit x = y, soit x < y, soit x > y.

Types de séquences

Différents algorithmes de tri marchent pour différents types de séquences. Ici, nous allons considérer des algorithmes de tri sur les tableaux et des algorithmes de tri sur les listes.

Opérations sur les éléments

Une autre distinction sur les algorithmes de tri concernes les opérations permise sur les éléments du domaine. La plus grande famille d'algorithmes permet uniquement la comparaison entre deux éléments comme c'est indiqué ci-dessus. Cette famille d'algorithmes s'appelle tri par comparaison. D'autres algorithmes permettent des opérations plus fines, comme de faire correspondre les éléments du domaine à des petits entiers. Ce dernier type d'algorithmes de tri s'appelle tri par casiers

En place

On dit qu'un algorithme de tri est en place s'il n'utilise que très peu (O(1)) de mémoire auxiliaire.

Stabilité

On dit qu'un algorithme de tri est stable s'il préserve l'ordre entre éléments égaux.