Epita:Algo:Cours:Info-Sup:Algorithmes de tri simples
Sommaire |
Les tris simples
Généralités et définitions
La donnée d'un tri est une liste $L$ de $N$ éléments. Une clé appartenant à un ensemble totalement ordonné est associée à chacun d'eux. C'est la condition sinequanone pour pouvoir trier les éléments entre eux. Trier la liste $L$ consiste à trouver une liste $L'$ dont les éléments sont une permutation de ceux de la liste $L$ d'origine.
Définitions
- Une liste est triée si les clés de ses éléments apparaissent en ordre croissant/décroissant lorsqu'on la parcourt.
- Deux listes $L$ et $L'$ sont des permutations l'une de l'autre si et seulement si le nombre d'occurrences de tout élément est égal dans les deux listes.
- Un tri est stable s'il conserve l'ordre d'origine des éléments dont les clés sont égales. Cette propriété (la stabilité) est intéressante lorsque l'on fait des tris successifs en décomposant les clés.
- Une clé est dite structurée quand elle est composée de plusieurs valeurs, comme par exemple: une clé classe + une clé nom + une clé prénom. On dit dans ce cas que classe est la clé primaire et que nom et prénom sont des sous-clés secondaires.
- On parle de tri interne lorsque les éléments et les clés sont séparés et organisés différemment pour permettre une gestion complète de la collection de données en mémoire. Avec ou sans recopie de la liste d'éléments, ce qui peut avoir son importance dans le choix de l'algorithme de tri.
Dans les autres cas, le tri sera externe.
Conventions
Dans tous les exemples qui suivront, nous utiliserons des tableaux d'entiers, les éléments étant réduits à leur clé. Nous utiliserons une représentation contiguë des listes. Si une représentation chaînée est souhaitable, nous le préciserons.
Les algorithmes de tris présentent des comparaisons entre clés et ds transferts (affectations) de ces même clés. Nous présenterons donc pour chaque algorithme, pour ces deux types d'opérations, la complexité en fonction de $N$ éléments.
