Les tableaux : résultats des tris

Pour finir l’exemple d’utilisation des tableaux, voici les résultats des trois méthodes de tri présentées :

Pour un tableau de taille 5 :

4 2 0 5 3
0 2 3 4 5
durée du tri à bulle : 4819 nanosecondes
durée du tri par sélection : 4539 nanosecondes
durée du tri par insertion : 4889 nanosecondes

Pour un tableau de taille 10 :

8 5 9 0 2 5 7 2 1 3
0 1 2 2 3 5 5 7 8 9
durée du tri à bulle : 8032 nanosecondes
durée du tri par sélection : 5936 nanosecondes
durée du tri par insertion : 6216 nanosecondes

Pour un tableau de taille 50 :

3 3 5 6 8 1 7 4 6 8 1 2 4 2 0 3 4 4 1 9 5 3 4 3 4 7 9 8 4 7 6 4 6 2 1 4 8 1 1 8 3 3 0 4 2 3 4 9 0 9
0 0 0 1 1 1 1 1 1 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 5 5 6 6 6 6 7 7 7 8 8 8 8 8 9 9 9 9
durée du tri à bulle : 112794 nanosecondes
durée du tri par sélection : 40019 nanosecondes
durée du tri par insertion : 35410 nanosecondes

Les tableaux : comparaison des tris

Pour effectuer les tests d’efficacité sur les tris, nous prendrons des tableaux d’entier compris entre 0 et 9.

L’initialisation des Tableaux se fera à l’aide d’une méthode qui va créer un tableau de taille n et le remplir avec des nombres aléatoirement choisit entre 0 et 9 grâce à la méthode ” Random “.

Le code utilisé est le suivant :

Avant d’exécuter les méthodes de tri sur le tableau ainsi obtenu, il en faut en crée deux autres instances afin de disposer d’un tableau identique pour les autres méthodes de Tri. La création des deux autres tableaux se fait de la manière suivante :

On exécute ensuite chacune des méthode de tri sur l’un des tableaux, en prenant les temps processeur avant et après le tri, de manière à connaitre la durée d’exécution de chaque tri sur le tableau. Ceci se fait grâce au code suivant :

afficher(tab1);
long time1 = System.nanoTime();
triBulle(tab1);
long time2 = System.nanoTime();
afficher(tab1);
System.out.println(“durée du tri à bulle : “+ (time2 – time1) +” nanosecondes”+“\n”);

afficher(tab2);
long time3 = System.nanoTime();
triSelection(tab2);
long time4 = System.nanoTime();
afficher(tab2);
System.out.println(“durée du tri par selection : “+ (time4 – time3) +” nanosecondes”+“\n”);

afficher(tab3);
long time5 = System.nanoTime();
triInsertion(tab3);
long time6 = System.nanoTime();
afficher(tab3);
System.out.println(“durée du tri par insertion : “+ (time6 – time5) +” nanosecondes”+“\n”);

Les résultats pour différentes tailles de tableaux seront présentés dans l’article suivant.

Les tableaux : les tris

Pour trier des tableaux, il existe trois méthodes de tris principales : Le tri à bulles, le tri par sélection, et le tri par insertion. Nous allons voir dans la suite la particularité de chaque tri, ainsi qu’un exemple de codage dans la langage JAVA.

Pour commencer, nous allons introduire la fonction « inverser » qui inverse les éléments aux adresses i et i+1 du tableau

Le tri à bulles :

Son principe de fonctionnement est le suivant : on parcours le tableaux case après case et on compare les valeurs des cases i et i+1 . Si Montableau[i]>Montableau[i+1], alors on inverse les valeurs des cases i et i+1. On continue ensuite à parcourir le tableau en boucle jusqu’à ce que plus aucune inversion ne soit réalisée. On obtient alors un tableau trié par ordre croissant. (modifiable pour classer en ordre décroissant).

Exemple :

Code Java :

Le tri par sélection :

Le tri par sélection consiste à parcourir le tableau, et, à chaque passage, relève la valeur la plus haute, et réalise une inversion entre la dernière case du tableau et la case contenant la valeur maximale du tableau. Au passage suivant, on relève la valeur de la case contenant la plus grande valeur parmi les n-1 premières cases du tableau pour un tableau de taille n. L’opération se répète jusqu’à ce que n prenne la valeur 1.

Exemple :

Code JAVA :

Le tri par insertion :

Ce tri à la particularité d’utiliser un deuxième tableau, de taille identique à celui à trier, mais initialement vide. On lit les valeurs du tableau à trier une par une, et on les insère directement à la bonne place dans le tableau vide, on décale alors les autres valeurs du second tableau pour insérer la valeur en question au bon endroit, sans modifier les informations ni les perdre.

Exemple :

Code JAVA :

Les tableaux : introduction

Pour commencer ce blog, nous allons étudier une structure de données inévitable et certainement la plus simple à utiliser. Il s’agit des tableaux (arrays en anglais).
Un tableau est un ensemble, de taille fixe, regroupant des éléments d’un même type (entier par exemple). Grâce à l’indexation de ces éléments, il est possible d’atteindre immédiatement n’importe quel élément du tableau. La figure 1 illustre ces propos :

Exemple d’implémentation de ce tableau d’entiers en JAVA :

public static void main(String[] args) {

      int [] monTableau = {15, 53, 1, 29, 5, 8};

      System.out.println(monTableau[0]); // affiche 15

      System.out.println(monTableau[3]); // affiche 29
}

Dans ce programme, nous avons crée un tableau nommé monTableau représenté par la figure 1. Il contient six éléments. L’accès à l’un d’eux se fait à l’aider de la syntaxe suivante : monTableau[i] où i représente l’index (ou l’indice) de l’élément recherché.
Vous remarquerez que le premier élément du tableau est indexé par 0 et non par 1. (On parle de “zero-based indexing”). L’index du dernier élément est donc 5.

En mémoire, ce tableau occupe six cases mémoires consécutives. MonTableau est simplement une référence (ou un pointeur) vers la première case mémoire contenant la première valeur du tableau. monTableau[i] signifie simplement un déplacement de i cases mémoires depuis la première case mémoire référencée par monTableau. Ceci permet d’obtenir un temps d’accès constant à n’importe quel élément du tableau. La figure 2 illustre ces propos :

Dans l’exemple précédent le tableau contient des entiers. Il est également possible de créer des tableaux contenant des tableaux. On parle alors de tableaux à N-dimensions.

Les tableaux sont très faciles à utiliser malheureusement ils ne sont pas du tout performants pour les recherches. En effet, pour rechercher un élément dans un tableau il faut le parcourir dans sa totalité dans le pire des cas. On dit alors que la complexité algorithmique est de O(n). Les performances des recherches sur les tableaux peuvent être améliorées en les complétant d’une relation d’ordre. On peut alors soit trier le tableau, soit insérer les éléments au bon endroit lors de la création du tableau.

Le prochain article présentera différents algorithmes de tris des tableaux.