Les algorithmes de tri
Si les données sont triées, l'accès aux informations 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.
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 il n'y a plus de cases vides.
Cette méthode demande un temps d’exécution plus important que le tri par fusion.
II/ Tri par fusion
Cette algorithme découpe la table en groupe 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…
Si nécessaire on rajoute à la fin du tableau de grandes valeurs pour permettre le tri.
Cette méthode est plus rapide 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 loin et plus rapide d’exécution.
II/ Programmation d'un tri
Créer un tableau de valeurs aléatoires
Afficher le tableau non trié
Appel de la fonction de tri
Affichage du tableau trié
void setup() {
la fonction setup ne renvoie à rien, s'exécute qu'une fois et ne prend aucuns paramètres/arguments et n’a pas besoin d'être appelée, elle s'exécute en première automatiquement dès le début
pas de « ; » donc ce n’est pas une instruction !!!!
int i, j, k, z;
c'est une instruction car « ; » déclaration de 4 variables entières, on n'y met pas de valeurs (on initialise pas)
int [] tab = new int [16];
déclaration d'un nouveau tableau pouvant contenir 16 valeurs entières
!!!!!void et new sont en vert : ce sont des mots clés qui ont un sens pour processing
!!!!! en orange : type de variables
!!!!! en bleu : les fonctions (pour nous fonctions et méthodes sont les mêmes choses)
!!!!!parenthèses pour les paramètres
for (i = 0; i <= 15; i = i + 1) {
boucle for : i est la variable compteur de boucle de 0 a 15 qui prend 16 valeurs
tab[i] = (int)Math.floor(Math.random() * 1000);
!!! = affectation d'une valeur
affectation dans la case i du tableau d’une valeur entière
!!! int entre parenthèse est un caste car c’est la transformation d'une valeur numérique en valeur entière
fonction random par défaut génère un nombre aléatoire compris entre 0 et 1
fonction floor prend la partie entière de l'argument
première boucle for affecte a chaque case du tableau 16 valeurs entière aléatoires
}
for (i = 0; i <= 15; i = i + 1) {
print(tab[i] + " ");
la boucle suivante permet d'afficher sur la console toutes les valeurs du tableau séparées par un espace
}
System.out.println();
printline retour a la ligne juste println aurait suffit (syntaxe java)
!!!!! en JAVA la première fonction qui s'exécute est le « main » (équivalent au setup du processing)
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;
() dans le if : condition qui se traduit par un booléen (vrai ou faux)
si c'est vrai …
ici il n'y a pas de sinon (else)
}
}
z = tab[i];
tab[i] = tab[k];
tab[k] = z;
}
for (i = 0; i <= 15; i = i + 1) {
print(tab[i] + " ");
}
System.out.println();
}
Réorganisation en fonction
int i, j, k, z;
int [] tab = new int [16];
variables globales utilisables dans tout le programme sont déclarées au tout début du sketch
void setup() {
remplir();
afficher() ;
trier();
afficher() ;
}
void remplir(){
for (i = 0; i <= 15; i = i + 1) {
tab[i] = (int)Math.floor(Math.random() * 1000);
}
}
void afficher (){
for (i = 0; i <= 15; i = i + 1) {
print(tab[i] + " ");
}
System.out.println();
}
void trier(){
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;
}
System.out.println();
}
Utiliser des fonctions permet de clarifier le programme
Un algorithme récursif utilise des fonctions qui s'appellent elles mêmes
void fusion (...){
fusion
}
fusion appelle fusion
if ((une condition) &&(une autre condition) && (une autre condition) || (une autre condition)
combinaison de conditions
while (tant que) est un outil dangereux pour gérer les boucles car le nombres de tours n'est pas prédéfinit, risque de tours sans fin.