Le Tri
Quel intérêt du tri ?
Si les données sont triées, l'accès aux information sera plus rapide dans la plupart des cas.
Toutes les informations peuvent être représentées par des nombres que l'on triera par ordre croissant ou décroissant.
1.Le tri à bulles
Le tri à bulle est utilisé par les ordinateurs pour classer des données dans un ordre spécifique.
La bulle de comparaison se déplace dans le tableau à trier on compare deux éléments consécutifs et on les échange si nécessaire.
Si le déplacement entre deux chiffres est nécessaire, on déplace le 1er chiffre dans la case auxiliaire puis le 2nd chiffre va ainsi dans la case libérée. Enfin le chiffre qui se situe dans la case auxiliaire prend la place de la case restée vide.
Après cette étape la bulle se déplace le long du tableau et poursuit le tri.
2.Le tri par sélection ou par insertion
Si l'on dispose d'un tableau de 7 cartes (A,B,C,D,E,F et G), déjà trié et qu'on veut en insérer une de plus. On la compare à celle du milieu D. Si elle est inférieure à D on la compare à B. Si elle est inférieur à B on la compare à A. Au final, 3 questions suffisent pour insérer une carte dans un tableau en contenant déjà 7 (dichotomie).
Le tri par insertion consiste à trier le début du tableau puis à y insérer à la bonne place, les autres cartes à 1 à 1.
Autre explications :
I) Tri par sélection
C'est la méthode que l'on va utiliser 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.
Amélioration de l'algorithme :
Un nouveau tableau n'est pas 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 pour le tri par fusion.
II) Tri par fusion
Cet algorithme découpe la table en groupes de deux cases. Les nombres sont triés par ordre croissant dans chaque groupe. Puis on groupe deux ensembles de deux cases que l'on trie. Puis deux ensembles de quatre, de huit, etc....
Si nécessaire, on rajoute à la fin du tableau de grandes valeurs pour permettre le tri (avoir un nombre pair).
Cette méthode est plus rapide et plus efficace surtout si elle est codée avec un algorithme récursif.
L'algorithme récursif utilise des fonctions qui s'appellent elles-mêmes. Le code est moins long et plus rapide d'exécution.
3.Programmation d'un tri
Etape 1 : créer un tableau de valeurs aléatoires
Etape 2 : afficher le tableau non-trié
Etape 3 : appel de la fonction de tri et affichage du tableau tri
Exemple de programme exécutant un tri par sélection :
void setup() {
int i, j, k, z;
int [] tab = new int [16];
for (i = 0; i <= 15; i = i + 1) {
tab[i] = (int)Math.floor(Math.random() * 1000);
}
for (i = 0; i <= 15; i = i + 1) {
print(tab[i] + " ");
}
System.out.println();
for (i = 0; i <= 14; i = i + 1) {
k = i;
for (j = i + 1; j <= 15; j = j + 1) {
if (tab[j] <= tab[k]) {
k = j;
}
}
z = tab[i] ;
tab[i] = tab[k];
tab[k] = z;
}
for (i = 0; i <= 15; i = i + 1) {
print(tab[i] + " ");
}
System.out.println();
}