Les algorithmes simples de tri

Le problème

Le but du TD est simple, il s'agit de passer en revue les méthodes de tri les plus simples. Vous avez probablement déjà programmé certains tris, en ce cas, votre tâche n'en sera que plus aisée. Chacun de vos tris sera programmé comme une procédure ou une fonction et le programme principal donnera le choix entre les différentes méthodes.

Il existe de nombreux algorithmes visant à trier un ensemble de données selon un certain prédicat. Nous programmerons deux de ces algorithmes dans ce TD. Pour des raisons de commodité, nous ne traiterons que des listes de n entiers et les rangerons dans un ordre croissant mais le principe reste le même pour n'importe quel type de données et n'importe quel prédicat de comparaison.

Les méthodes de tri les plus connues sont, pratiquement dans l'ordre d'efficacité croissante, les suivantes

• permutation ou tri bulle,
• extraction simple et dichotomique,
• insertion simple et dichotomique,
• tri rapide ou quick sort.

Programmation

Nous ne programmerons dans ce TD que les tris par permutation et insertion simple et dichotomique, le tri rapide sera traité dans un TD ultérieur.

Tri par permutation

C'est probablement la méthode la plus simple. Cette méthode consiste à ramener, par le biais de permutations, l'élément le plus petit en début de liste (comme une bulle). Puis, ceci fait, il suffit de réitérer le processus en ne considérant plus que les n-1 éléments restant dans la liste.

Cet algorithme modifie la liste initiale et se programme à l'aide de deux boucles imbriquées. L'une parcoure la liste en partant de la tête et contient une seconde boucle partant de la fin, comparant deux éléments consécutifs et les permutant si besoin est.

Ex:

[3, 1, 5, 7, -3, 2] liste initiale

[-3, 3, 1, 5, 7, 2] -3 est mis en tête de liste

[-3, 1, 3, 5, 7, 2] 1 est mis en tête de la liste restante

[-3, 1, 2, 3, 5, 7] 2 est mis en tête de la liste restante

[-3, 1, 2, 3. 5. 71

Tri par insertion

Cette méthode consiste, quant à elle, à construire, élément après élément, une liste triée. Il suffit de partir d'une liste vide et d'y insérer successivement tous les éléments de la liste initiale. Le problème se résume donc à écrire une procédure d'insertion d'un élément dans une liste triée puis de rappeler cette procédure n fois pour obtenir ce que l'on désire.

Reprenons l'exemple précédant

[]

[3]

[1, 3]

[1, 3, 5]

[1, 3, 5, 7]

[-3, 1, 3, 5, 7]

[-3, 1, 2, 3, 5, 7]

Les algorithmes de tri par insertion simple et insertion dichotomique présentent rigoureusement la même structure si ce n'est que :

• insertion simple : la recherche de l'endroit d'insertion se fait en parcourant la liste depuis le début et en comparant l'élément à insérer à l'élément courant,
• insertion dichotomique : la recherche de l'endroit d'insertion se fait par dichotomie (séparation de l'intervalle en deux... ).

Procédures complémentaires et structures de données

Pour pouvoir tester nos algorithmes, il est indispensable de disposer d'une procédure d'entrée des éléments d'une liste et d'une procédure d'affichage de listes (probablement déjà écrites lors d'un précédant TD).

De plus, tous les algorithmes de tri nécessitent d'avoir accès à la taille de la liste. Pour ce faire, il y a généralement deux stratégies :

• calculer, lors de l'entrée, le nombre d'éléments et passer celui-ci en argument de toutes les procédures ou fonctions,
• manipuler une structure contenant la taille de la liste et la liste elle même en lieu et place d'une simple liste.