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é.