TP #9 : Tris

Objectifs

Exercices sur les tris de tableaux

Tris vus en cours

Vous implémenterez deux tris vus en cours : le tri par sélection et le tri par insertion.

Tri-rapide

Cette méthode consiste à placer un élément (appelé pivot) de la suite à trier à sa place définitive en permutant tous les éléments de telle sorte que tous ceux qui lui sont inférieurs soient à sa gauche et que tous ceux qui lui sont supérieurs soient à sa droite. Cette opération s’appelle partitionnement. Pour chacune des sous-suites obtenues, on définit un nouveau pivot et on répète l’opération de partitionnement. Ce processus est répété récursivement, jusqu’à ce que la suite soit triée. En pratique, le pivot est soit le premier, soit le dernier élément de la suite à trier. Dans l’exemple suivant, le pivot est le dernier élément de la suite.

tri rapide	28	13	20	35	21	19	15	18	pivot = 18
partition	15	13	18	20	35	21	19	28	pivot placé
tri rapide	15	13							pivot = 13
partition	13	15							pivot placé
tri rapide				20	35	21	19	28	pivot = 28
partition				20	19	21	28	35	pivot placé
tri rapide				20	19	21			pivot = 21
partition				20	19	21			pivot placé
tri rapide				20	19				pivot = 19
partition				19	20				pivot placé
fin	13	15	18	19	20	21	28	35

L’objectif est donc d’écrire l’algorithme du tri-rapide

Comparaisons

Pour évaluer la performance de ces 3 algorithmes, vous testerez sur des exemples de tableaux d’entiers de taille variable avec des nombres aléatoires. Vous testerez également l’influence de trier un tableau partiellement / totalement trié.