البـــــوابـــة
Chapitre 1 Tableaux
Les tableaux sont une des structures de base de l'informatique. Un tableau représente selon ses dimensions, un vecteur ou une matrice d'éléments d'un même type. Un tableau permet l'accès direct à un élément, et nous allons nous servir grandement de cette propriété dans les algorithmes de tri et de recherche en table que nous allons considérer.
1.1 Le tri
Qu'est-ce qu'un tri? On suppose qu'on se donne une suite de N nombres entiers á ai ñ, et on veut les ranger en ordre croissant au sens large. Ainsi, pour N = 10, la suite
devra devenir
Ce problème est un classique de l'informatique. Il a été étudié en détail, cf. la moitié du livre de Knuth [30]. En tant qu'algorithme pratique, on le rencontre souvent. Par exemple, il faut établir le classement de certains élèves, mettre en ordre un dictionnaire, trier l'index d'un livre, faire une sortie lisible d'un correcteur d'orthographe, ... Il faudra bien faire la distinction entre le tri d'un grand nombre d'éléments (plusieurs centaines), et le tri de quelques éléments (un paquet de cartes). Dans ce dernier cas, la méthode importe peu. Un algorithme amusant, bogo-tri, consiste à regarder si le paquet de cartes est déjà ordonné. Sinon, on le jette par terre. Et on recommence. Au bout d'un certain temps, on risque d'avoir les cartes ordonnées. Bien sûr, le bogo-tri peut ne pas se terminer. Une autre technique fréquemment utilisée avec un jeu de cartes consiste à regarder s'il n'y a pas une transposition à effectuer. Dès qu'on en voit une à faire, on la fait et on recommence. Cette méthode marche très bien sur une bonne distribution de cartes.
Plus sérieusement, il faudra toujours avoir à l'esprit que le nombre d'objets à trier est important. Ce n'est pas la peine de trouver une méthode sophistiquée pour trier 10 éléments. Pourtant, les exemples traités dans un cours sont toujours de taille limitée, pour des raisons pédagogiques il n'est pas possible de représenter un tri sur plusieurs milliers d'éléments. Le tri, par ses multiples facettes, est un très bon exemple d'école. En général, on exigera que le tri se fasse in situ, c'est-à-dire que le résultat soit au même endroit que la suite initiale. On peut bien sûr trier autre chose que des entiers. Il suffit de disposer d'un domaine de valeurs muni d'une relation d'ordre total. On peut donc trier des caractères, des mots en ordre alphabétique, des enregistrements selon un certain champ. On supposera, pour simplifier, qu'il existe une opération d'échange ou plus simplement d'affectation sur les éléments de la suite à trier. C'est pourquoi nous prendrons le cas de valeurs entières.
1.1.1 Méthodes de tri élémentaires
Dans tout ce qui suit, on suppose que l'on trie des nombres entiers et que ceux-ci se trouvent dans un tableau a. L'algorithme de tri le plus simple est le tri par sélection. Il consiste à trouver l'emplacement de l'élément le plus petit du tableau, c'est-à-dire l'entier m tel que ai ³ am pour tout i. Une fois cet emplacement m trouvé, on échange les éléments a1 et am. Puis on recommence ces opérations sur la suite á a2, a3, ..., aN ñ, ainsi on recherche le plus petit élément de cette nouvelle suite et on l'échange avec a2. Et ainsi de suite ... jusqu'au moment où on n'a plus qu'une suite composée d'un seul élément á aN ñ.
La recherche du plus petit élément d'un tableau est un des premiers exercices de programmation. La détermination de la position de cet élément est très similaire, elle s'effectue à l'aide de la suite d'instructions: m = 0;
for (int j = 1; j < N; ++j)
if (a[j] < a[m])
m = i;
Il faut refaire cette suite d'opérations en remplacant 1 par 2, puis par 3 et ainsi de suite jusqu'à N. Ceci se fait par l'introduction d'une nouvelle variable i qui prend toutes les valeurs entre 1 et N. Ces considérations donnent lieu au programme présenté en détail ci-dessous. Pour une fois, nous l' écrivons pour une fois en totalité; les procédures d'acquisition des données et de restitution des résultats sont aussi fournies. Pour les autres algorithmes, nous nous limiterons à la description de la procédure effective de tri.
class TriSelection {
final static int N = 10;
static int[] a = new int[N]; // Le tableau à trier
static void initialisation() { // On tire au sort des nombres
// entre 0 et 127, en initialisant
// le tirage au sort sur l'heure
for (int i = 0; i < N; ++i)
a = (int) (Math.random() * 128);
}
static void impression() {
for (int i = 0; i < N; ++i)
System.out.print (a[i] + " ");
System.out.println ("");
}
static void triSelection() {
int min, t;
for (int i = 0; i < N - 1; ++i) {
min = i;
for (int j = i+1; j < N; ++j)
if (a[j] < a[min])
min = j;
t = a[min]; a[min] = a[i]; a[i] = t;
}
}
public static void main (String args[]) {
initialisation(); // On lit le tableau
impression(); // et on l'imprime
triSelection(); // On trie
impression(); // On imprime le résultat
}
}
Les tableaux sont une des structures de base de l'informatique. Un tableau représente selon ses dimensions, un vecteur ou une matrice d'éléments d'un même type. Un tableau permet l'accès direct à un élément, et nous allons nous servir grandement de cette propriété dans les algorithmes de tri et de recherche en table que nous allons considérer.
1.1 Le tri
Qu'est-ce qu'un tri? On suppose qu'on se donne une suite de N nombres entiers á ai ñ, et on veut les ranger en ordre croissant au sens large. Ainsi, pour N = 10, la suite
á 18, 3, 10, 25, 9, 3, 11, 13, 23, 8 ñ
devra devenir
á 3, 3, 8, 9, 10, 11, 13, 18, 23, 25 ñ
Ce problème est un classique de l'informatique. Il a été étudié en détail, cf. la moitié du livre de Knuth [30]. En tant qu'algorithme pratique, on le rencontre souvent. Par exemple, il faut établir le classement de certains élèves, mettre en ordre un dictionnaire, trier l'index d'un livre, faire une sortie lisible d'un correcteur d'orthographe, ... Il faudra bien faire la distinction entre le tri d'un grand nombre d'éléments (plusieurs centaines), et le tri de quelques éléments (un paquet de cartes). Dans ce dernier cas, la méthode importe peu. Un algorithme amusant, bogo-tri, consiste à regarder si le paquet de cartes est déjà ordonné. Sinon, on le jette par terre. Et on recommence. Au bout d'un certain temps, on risque d'avoir les cartes ordonnées. Bien sûr, le bogo-tri peut ne pas se terminer. Une autre technique fréquemment utilisée avec un jeu de cartes consiste à regarder s'il n'y a pas une transposition à effectuer. Dès qu'on en voit une à faire, on la fait et on recommence. Cette méthode marche très bien sur une bonne distribution de cartes.
Plus sérieusement, il faudra toujours avoir à l'esprit que le nombre d'objets à trier est important. Ce n'est pas la peine de trouver une méthode sophistiquée pour trier 10 éléments. Pourtant, les exemples traités dans un cours sont toujours de taille limitée, pour des raisons pédagogiques il n'est pas possible de représenter un tri sur plusieurs milliers d'éléments. Le tri, par ses multiples facettes, est un très bon exemple d'école. En général, on exigera que le tri se fasse in situ, c'est-à-dire que le résultat soit au même endroit que la suite initiale. On peut bien sûr trier autre chose que des entiers. Il suffit de disposer d'un domaine de valeurs muni d'une relation d'ordre total. On peut donc trier des caractères, des mots en ordre alphabétique, des enregistrements selon un certain champ. On supposera, pour simplifier, qu'il existe une opération d'échange ou plus simplement d'affectation sur les éléments de la suite à trier. C'est pourquoi nous prendrons le cas de valeurs entières.
1.1.1 Méthodes de tri élémentaires
Dans tout ce qui suit, on suppose que l'on trie des nombres entiers et que ceux-ci se trouvent dans un tableau a. L'algorithme de tri le plus simple est le tri par sélection. Il consiste à trouver l'emplacement de l'élément le plus petit du tableau, c'est-à-dire l'entier m tel que ai ³ am pour tout i. Une fois cet emplacement m trouvé, on échange les éléments a1 et am. Puis on recommence ces opérations sur la suite á a2, a3, ..., aN ñ, ainsi on recherche le plus petit élément de cette nouvelle suite et on l'échange avec a2. Et ainsi de suite ... jusqu'au moment où on n'a plus qu'une suite composée d'un seul élément á aN ñ.
La recherche du plus petit élément d'un tableau est un des premiers exercices de programmation. La détermination de la position de cet élément est très similaire, elle s'effectue à l'aide de la suite d'instructions: m = 0;
for (int j = 1; j < N; ++j)
if (a[j] < a[m])
m = i;
L'échange de deux éléments nécessite une variable temporaire t et s'effectue par: t = a[m]; a[m] = a[1]; a[1] = t;
Figure 1.1 : Exemple de tri par sélection
Il faut refaire cette suite d'opérations en remplacant 1 par 2, puis par 3 et ainsi de suite jusqu'à N. Ceci se fait par l'introduction d'une nouvelle variable i qui prend toutes les valeurs entre 1 et N. Ces considérations donnent lieu au programme présenté en détail ci-dessous. Pour une fois, nous l' écrivons pour une fois en totalité; les procédures d'acquisition des données et de restitution des résultats sont aussi fournies. Pour les autres algorithmes, nous nous limiterons à la description de la procédure effective de tri.
class TriSelection {
final static int N = 10;
static int[] a = new int[N]; // Le tableau à trier
static void initialisation() { // On tire au sort des nombres
// entre 0 et 127, en initialisant
// le tirage au sort sur l'heure
for (int i = 0; i < N; ++i)
a = (int) (Math.random() * 128);
}
static void impression() {
for (int i = 0; i < N; ++i)
System.out.print (a[i] + " ");
System.out.println ("");
}
static void triSelection() {
int min, t;
for (int i = 0; i < N - 1; ++i) {
min = i;
for (int j = i+1; j < N; ++j)
if (a[j] < a[min])
min = j;
t = a[min]; a[min] = a[i]; a[i] = t;
}
}
public static void main (String args[]) {
initialisation(); // On lit le tableau
impression(); // et on l'imprime
triSelection(); // On trie
impression(); // On imprime le résultat
}
}
Figure 1.2 : Exemple de tri bulle
Il est facile de compter le nombre d'opérations nécessaires. A chaque itération, on démarre à l'élément [i]ai et on le compare successivement à ai+1, ai+2, ..., aN. On fait donc N - i comparaisons. On commence avec i = 1 et on finit avec i = N-1. Donc on fait (N-1) + (N-2) + ··· + 2 + 1 = N(N-1)/2 comparaisons, et N-1 échanges. Le tri par sélection fait donc de l'ordre de N2 comparaisons. Si N = 100, il y a 5000 comparaisons, soit 5 ms si on arrive à faire une comparaison et l'itération de la boucle for en 1µs, ce qui est tout à fait possible sur une machine plutôt rapide actuellement. On écrira que le tri par sélection est en O(N2). Son temps est quadratique par rapport aux nombres d'éléments du tableau.
Une variante du tri par sélection est le tri bulle. Son principe est de parcourir la suite á a1, a2, ..., aN ñ en intervertissant toute paire d'éléments consécutifs (aj-1, aj) non ordonnés. Ainsi après un parcours, l'élément maximum se retrouve en aN. On recommence avec le préfixe á a1, a1, ..., aN-1 ñ, ... Le nom de tri bulle vient donc de ce que les plus grands nombres se déplacent vers la droite en poussant des bulles successives de la gauche vers la droite. L'exemple numérique précédent est donné avec le tri bulle dans la figure ..
La procédure correspondante utilise un indice i qui marque la fin du préfixe à trier, et l'indice j qui permet de déplacer la bulle qui monte vers la borne i. On peut compter aussi très facilement le nombre d'opérations et se rendre compte qu'il s'agit d'un tri en O(N2) comparaisons et éventuellement échanges (si par exemple le tableau est donné en ordre strictement décroissant).
Une variante du tri par sélection est le tri bulle. Son principe est de parcourir la suite á a1, a2, ..., aN ñ en intervertissant toute paire d'éléments consécutifs (aj-1, aj) non ordonnés. Ainsi après un parcours, l'élément maximum se retrouve en aN. On recommence avec le préfixe á a1, a1, ..., aN-1 ñ, ... Le nom de tri bulle vient donc de ce que les plus grands nombres se déplacent vers la droite en poussant des bulles successives de la gauche vers la droite. L'exemple numérique précédent est donné avec le tri bulle dans la figure ..
La procédure correspondante utilise un indice i qui marque la fin du préfixe à trier, et l'indice j qui permet de déplacer la bulle qui monte vers la borne i. On peut compter aussi très facilement le nombre d'opérations et se rendre compte qu'il s'agit d'un tri en O(N2) comparaisons et éventuellement échanges (si par exemple le tableau est donné en ordre strictement décroissant).
