COURS/TP 8 : algorithmes de tri

Introduction

De nombreux problèmes portant sur les listes peuvent être traités par des algorithmes plus efficaces lorsque les listes sont triées. Il peut donc être intéressant de disposer d'algorithmes permettant de trier une liste.

Algorithmes de tri

Il existe de nombreux algorithmes de tri. On présente trois algorithmes dits "naïfs" : le tri par sélection, le tri par insertion, et le tri à bulles.

Tri par sélection

Le tri par sélection consiste à répéter l'instruction suivante :

trouver le k-ième élément le plus petit, puis à l'échanger avec le k-ième élément.

Exemple : on veut trier la liste L=[6,4,2,6,3,1].

La liste obtenue est alors triée.

Tri par insertion

On commence par initialiser une liste M = []. On répète l'instruction suivante :

on choisit le k-ième élément de L, et on l'insère à sa place dans M.

Exemple : on veut trier la liste L = [6,3,1,7,5,2,3]. On initialise M=[].

Ainsi, lorsque l'on trie L, on trouve la liste M.

La liste obtenue est alors triée.

Tri par comptage

Pour le tri par comptage, on suppose que les éléments de la liste $L$ appartiennent tous à un même ensemble $E$ (par exemple $E=\{0,1,..., n\}$). Pour trier $L$, on commence par compter le nombre de fois que chaque élément de $E$ apparaît dans $L$. Pour trier $L$, il n'y a plus qu'à parcourir les éléments de $E$ dans l'ordre et les placer le bon nombre fois dans une liste $M$. À l'issue de l'algorithme, $M$ est la liste obtenue en triant la liste $L$.

Exemple : on veut trier $L = [3,1,1,5,9,9,1,3,4,3,7,6]$. On sait que les éléments sont compris entre $0$ et $9$. On commence par la liste des occurrences : $Oc = [0,3,0,3,1,1,1,1,0,2]$. Ainsi, en triant on obtient $M=[1,1,1,3,3,3,4,5,6,7,9,9]$.

Exercices

Exercice 1

On donne le pseudo-code de l'algorithme du tri par sélection :

Écrire une fonction tri_select(L) prenant en argument une liste entiers L et qui renvoie la liste obtenue en triant L dans l'ordre croissant.

Exercice 2

Exercice 3

Exercice 4

Lorsqu'une liste est triée, il est possible d'effectuer une recherche d'un élément dans une liste de manière plus efficace à l'aide de la dichotomie. On donne le pseudo-code suivant :

Exercice 5

Exercice 6

Écrire une fonction plus_grand_anagramme(mot) prenant en argument une chaîne de caractères mot et qui renvoie le plus grand anagramme de mot pour l'ordre lexicographique.