Les algorithmes de tri

Si les données sont triées, l'accès aux informations sera plus rapide dans la plupart des cas. Toutes les informations peuvent être représenté par des nombres que l'on triera par ordre croissant ou décroissant. On peut trier par sélection ou par fusion.

Tri par sélection: C'est la méthode que l'on utilise spontanément pour trier un tableau sans ordinateur. On cherche la valeur la plus petite, on la place dans la première case d'un nouveau tableau et on la supprime du tableau à trier. Puis de même avec les suivantes. Un nouveau tableau n'est pas vraiment nécessaire, il suffit de déplacer les valeurs les plus petites au début du tableau. Ainsi, plus de case vide.

Cette méthode demande un temps d'exécution plus important que le tri par fusion.

Tri par fusion:

Cet algorithme découpe la table en groupe de 2 cases, les nombres sont triés par ordre croissant dans chaque groupe. Puis, on groupe 2 ensembles de 2 cases que l'on trie. Puis, 2 ensembles de 4 puis de 8, ect...

Si nécessaire, on rajoute de grandes valeurs à la fin du tableau pour permettre le tri. Cette méthode est plus rapide surtout si elle est codée avec un algorithme récursif, utilisant des fonctions qui s'appellent elles-mêmes. Le code est plus court et plus rapide d'exécution mais plus compliqué à comprendre.

Pour programmer un tri, il faut:

1ère étape : créer un tableau de valeurs aléatoires

2ème étape : afficher le tableau non trié

3ème étape : appel de la fonction de tri et affichage du tableau trié