Les algorithmes de tri
Il faut trier les informations pour pouvoir ensuite y accéder plus facilement. Il existe de nombreux algorithmes de tri.
I- Le tri par sélection
Le tri par sélection est la méthode la plus intuitive de tri sans ordinateur. On cherche la valeur la plus petite du tableau. On la recopie dans la première case de notre tableau et on l'élimine du tableau de départ. Puis, on repère la valeur la plus petite restante et, etc,... Pour n'avoir à utiliser qu'un seul tableau, on peut placer la valeur la plus petite dans la première case et décaler les autres valeurs.
Pour ne pas perdre de valeur, il faut utiliser une variable de stockage intermédiaire dans laquelle on placera le 11 avant qu'il ne remplace le 42.
II- Tri par fusion
Cet algorithme divise le tableau principal en tableaux plus petits qui sont triés puis fusionnés.
42 63 32 14
42 63 14 32
Les petits sous - tableaux triés sont fusionnés 2 à 2 puis, de nouveau, fusionnés avec des tableaux à 4 valeurs et ,etc,... Cet algorithme est plus rapide, surtout s'il est programmé de manière récursive.
Une fonction récursive s'appelle elle-même pendant l'exécution du programme.
III- Programmation de tri sous Processing
1) Tri par sélection
void setup() {
// c'est une fonction qui ne prend pas de paramètres, qui ne renvoie rien au reste du programme et qui ne s'exécute qu'une fois. Les fonctions sont en bleu sur Processing / mots - clés en vert. Processing exécute automatiquement la fonction setup. Cette première ligne n'est pas une instruction (pas de point virgule).
int i, j, k, z;
// instruction de déclaration de 4 variables entières i, j, k et z.
int [] tab = new int [16];
// instruction de déclaration d'un tableau nommé tab à 16 valeurs (variables entières)
for (i = 0; i <= 15; i = i + 1) {
// numéroté de 0 à 15 ; boucle for qui s'exécute 16 fois où i est le compteur de boucles variant de 0 à 15. i est incrémenté de 1 à chaque tour de boucle.
tab[i] = (int)Math.floor(Math.random() * 1000);
// affectation d'un entier aléatoire compris entre 0 et 999 dans la case i du tableau. (int) = cast : transforme un décimal en nombre entier. random() est une fonction renvoyant un nombre aléatoire entre 0 et 1. floor() est une fonction qui renvoie la partie entière du nombre aléatoire de la fonction random.
}
for (i = 0; i <= 15; i = i + 1) {
print(tab[i] + " ");
}
// print(tab [i] + " ") écrit de la case [i) du tableau plus un espace.
System.out.println();
// instruction de retour à la ligne.
for (i = 0; i <= 14; i = i + 1) {
k = i;
for (j = i + 1; j <= 15; j = j + 1) {
if (tab[j] <= tab[k]) {
// il s'agit d'une condition (booléen) qui est vraie si le contenu de la case [j] est plus petit que le contenu de la case [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();
}
Ce programme n'a pas de fonction Draw car l'algorithme ne doit s'exécuter qu'une fois, la fonction Setup suffit.
Les variable au début du programme sont globales. Le découpage d'un sketch en fonction facilite sa compréhension.
2) Le tri récursif
Les fonctions récursives s'appellent elles-mêmes. L'algorithme est plus difficile à comprendre mais plus efficace, plus rapide.
void fusion ( ... ) On appelle la fonction fusion dans la fonction fusion.
3) Le tri par fusion
if(((x < b + s) && (y < b + 2 * s) && (tab[x] < tab[y])) '' (y == b + 2 * s)) {
Le if utilise un booléen qui est vrai si les 3 premières conditions sont vraies ou la quatrième.
&& = et.
'' = ou.
Le while est une boucle dont le nombre de tours n'est pas prédéfini. Risque : boucle infinie.