Les algorithmes de tri
Il faut trier les informations pour pouvoir ensuite y accéder plus rapidement, 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 ...
Pour n'avoir a utiliser qu'un seul tableau, on peut placer la valeur la plus petite dans la première case puis décaler les autres valeurs. Et ainsi de suite.
Pour ne pas perdre de valeur, il faut utiliser une variable de stockage intermédiaire dans laquelle on placera le 11 avant qu'il remplace le 42.
II) Tri par fusion :
Cet algorithme divise le tableau principal en tableau plus petit qui sont triés puis fusionnés.
42/63
Les petits sous tableaux triés sont fusionnés, puis de nouveau fusionnés avec des tableaux à 4 valeurs...
Cet algorithme est plus rapide surtout si 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 qui ne prend pas de paramètres, qui ne renvoi rien au reste du prog et s'exécute qu une fois.
int i, j, k, z; // instruction (;) de déclaration de 4 variables entières.
int [] tab = new int [16]; // déclaration d'un tableau d'entier à 16 valeurs numéroté de 0à15.
for (i = 0; i <= 15; i = i + 1) { // boucle qui s'exécute 16 fois, i variant de 0à15 (i=compteur). I est incrémenté de 1 à chaque tour
tab[i] = (int)Math.floor(Math.random() * 1000); // affectation d'un entier aléatoire compris entre 0et999 dans la case i du tableau. (int) transforme un décimal en entier. Random= fonction renvoyant une valeur entre 0et1. Floor renvoie la partie entière d'un nombre aléatoire.
}
for (i = 0; i <= 15; i = i + 1) { // boucle pour i allant de 0à15 avec un pas de 1
print(tab[i] + " "); // écrit sur une même ligne (sur la console) le contenu de la case i du tableau et un espace
}
System.out.println(); // retour à la ligne
for (i = 0; i <= 14; i = i + 1) { //boucle pour i allant de 0à14
k = i; // k prend la valeur i
for (j = i + 1; j <= 15; j = j + 1) { // boucle pour j allant de i+1à15
if (tab[j] <= tab[k]) { // condition booléen vrai si val tab j inférieur ou égal a val tab k
k = j; // j prend la valeur k
}
}
z = tab[i]; // z = tte les valeurs
tab[i] = tab[k]; // les valeurs du tableau = celle du tableau de k
tab[k] = z; // z prend les valeurs de tab k
}
for (i = 0; i <= 15; i = i + 1) {
print(tab[i] + " ");
}
System.out.println();
}
Les fonctions sont en bleu sur processing
Les mots clé sont en vert
Procession exécute automatiquement la fonction setup
Ce programme n'a pas de fonction Draw car l'algorithme ne doit s'exécuter qu'une fois, la fonction Setup suffit.
Les variables globales sont utilisables par toutes les fonctions du programme
Le découpage d'un sketch en fonction facilite sa compréhension
2) Les fonctions récursives
Elles s'appellent elles même. L'algorithme est plus difficile a comprendre mais plus efficace et plus rapide.
void fusion (...
fusion(...
* tri par fusion :
Le if= un booléen qui est vrai si les 3premieres conditions sont vraies ou la 4ème.
While est une boucle dont le nombre de tours n'est pas prédéfini :
risque= boucle infini.