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 sur la première case d'un autre tableau et on l'élimine du tableau de départ.
Puis on repère la valeur la plus petite restante.
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 puis le 42 prend la place du 11.
II]Tri par fusion
42 63
32 14
42 63
14 32
Les petits sous tableaux triés sont fusionnés 2 à 2 puis de nouveau fusionné avec des tableaux à 4 valeurs etc...
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'éxécution du programme.
III]Programmation de tri sous processing
1.Tri par selection
void setup() {//fonction qui ne s'execute qu'une fois n'influençant pas le reste du programme qui n'a aucune condition prend pas de paramère Les fonctions sont en bleu sur processing , mot clef en vert. Processing execute automatiquement la fonction setup.Ce n'est pas une instruction (pas de« ; »)
int i, j, k, z;//instruction declaration de 4 valeur entière i,j,k,z
int [] tab = new int [16]; //instruction déclaration d'un tableau nommé tab ayant 16 cases
for (i = 0; i <= 15; i = i + 1) {//fonction boucle for s'excute 16 fois où i est le compteur de boucle ayant pour parametre i allant de 0 à 15,i est incrémenté de 1 à chaque tour de boucle.
tab[i] = (int)Math.floor(Math.random() * 1000);// tableau avec la variable aléatoire i dont on intégrera une entier aléatoire entre 0 et 999. (int) transforme un décimal en nombre entier. Random() fonction renvoyant une valeur aléatoire entre 0 et 1. Floor() fonction partie entière du nombre aléatoire de la fonction random. Math fonction mathématique.
}// fin de la fonction for
for (i = 0; i <= 15; i = i + 1) {
print(tab[i] + " ");//écrit sur une meme ligne le contenu du tableau avec un espace.
}
System.out.println();// fonction 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]) {//Fonction boucle if de condition si un bouléen est vrai tableau de j est inférieur ou égual au tableau de 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();
}
Les variables au debut du programme sont globales
Le découpage d'un sketch en fonction facilite sa compréhension.
FONCTION RECURSIVE
Les Fonctions récursives s'appellent elles même , l'algorithme est plus difficile à comprendre mais plus efficace , plus rapide.
Void fusion{…
fusion(...)
}
TRI PAR FUSION
Cet algorithme divise le tableau principal en tableau plus petit, qui sont triés puis fusionnés.
if(((x < b + s) && (y < b + 2 * s) && (tab[x] < tab[y])) || (y == b + 2 * s)) {
Le if utilise un bouléen qui est vrai si les 3premieres conditions sont vrai ou la 4em.
while(s <= 15) {
Le while est une boucle dont le nombre de tour n'est pas prédefini.