Programmes de tri

Dans cette partie, nous allons montrer comment créer des programmes de tri sur des tableaux. Ces programmes sont basés sur des algorithmes de tri classiques enseignés dans toutes les filières de formation à la programmation.

Tri par sélection

Le tri par sélection consiste à parcourir un tableau de valeurs pour sélectionner la plus petite valeur et la placer en première position. Ensuite, il suffit de parcourir à nouveau le tableau pour placer la deuxième plus petite valeur et ainsi de suite.

Tri par insertion

Le tri par insertion repose sur le principe suivant : si les n premières valeurs du tableau sont déjà triées, placer la valeur suivante consiste à l’insérer parmi ces valeurs.

Tri par séparation

Le tri par séparation est le tri le plus rapide. Ce tri ne peut être réalisé directement avec AlgoTouch puisqu’il nécessite la prise en charge de la récursivité. C’est une notion extrêmement puissante mais non abordée dans le cadre que nous avons choisi : l’apprentissage de la programmation à des débutants. Cependant, nous pouvons programmer un algorithme de séparation de valeurs d’un tableau. Cet algorithme consiste d’abord à choisir une valeur, appelée pivot. Puis à placer toutes les valeurs du tableau inférieures ou égales à gauche du pivot et les valeurs supérieures ou égales à droite du pivot. Ainsi pour trier le tableau, il suffira de trier successivement les valeurs à gauche du pivot puis les valeurs à droite du pivot.
Défiler vers le haut