Les algorithmes de tri
Il faut trier les informations pour pouvoir ensuite y accéder de façon plus rapide et facile. Il existe de nombreux algorithmes de tri : le tri par sélection et le tri par fusion.
I- LE TRI PAR SELECTION
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, 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 et ainsi de suite.
Pour ne pas perdre de valeurs, 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.
EX :
42'63'32'14 devient 42 63'14 32 (nombre le plus petit des deux devant)
Les petits sous-tableaux triés sont fusionnés deux à deux, puis de nouveau fusionnés avec des tableaux à 4 valeurs, etc...
Cet algorithme est plus facile, 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() { // fonction ne prenant pas de paramètre, s'exécutant qu'une seule fois au début du programme et ne renvoie aucune valeur au reste du programme, les fonctions sont en bleu et les mots clés en vert sur Processing. Processing exécute automatiquement la fonction Setup. Ce n'est pas une instruction (elle n'a pas de ; )
int i, j, k, z; // instruction (;) qui déclare 4 variables entières nommées i j k z
int [] tab = new int [16]; // instruction de déclaration d'un tableau nommé «tab» d'entiers à 16 valeurs, numérotées de 0 à 15
for (i = 0; i <= 15; i = i + 1) { //boucle qui s'exécute 16 fois où i est le compteur de boucle, i variant de 0 à 15, i est incrémenté de 1 à chaque tour de boucle (on le voit avec i=i+1)
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. Le (int) : transforme un nombre décimal en nombre entier. Random : fonction revoyant à une variable aléatoire entre 0 et 1. Floor est une fonction renvoyant à la partie entière du nombre aléatoire de la fonction random. « Math » indique juste que c'est une fonction mathématique
}
for (i = 0; i <= 15; i = i + 1) {
print(tab[i] + " "); //écrit sur la console sur une même ligne le contenu de la case i tu tableau puis un espace
}
System.out.println(); // instruction 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]) { //une condition (« if »), avec un booléen qui est vrai si le contenu de la case j est plus petit ou égal au 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.
Le découpage d'un sketch en fonction facilite sa compréhension.
2) Tri par fusion récursif
Les fonctions récursives s'appellent elles-mêmes. L'algorithme est plus difficile à comprendre mais plus efficace et plus rapide.
void fusion (......
fusion(.....
3) Tri par fusion
if ( ( (x < b + s) && (y < b + 2 * s) && (tab[x] < tab[y]) ) || (y == b + 2 * s) ) {
"et" "et" "ou"
« if » utilise un booléen qui est vrai si les trois premières conditions sont vraies, ou si la quatrième est vraie.
while (s <= 15) {
« while » signifie tant que, c'est une boucle dont le nombre de tour n'est pas prédéfini, le risque possible est la boucle infinie...