Informatique -- Tronc Commun
TD 0 -- Animation du tri par sélection et du tri par bulles

Benjamin Werner, Eric Schost

18 Octobre 1999






Le but de ce TD est de manipuler la structure de tableau, en implémentant un algorithme simple de tri. De plus, on utilisera la bibliothèque graphique MacLib, déjà vue en TD d'initiation, pour construire une illustration animée du fonctionnement de l'algorithme.



1  Ecrivez-moi !

A mon grand désespoir, je n'ai pas encore reçu de courrier de chacun de vous. Si vous ne l'avez pas encore fait, envoyez-moi un mail à l'adresse Benjamin.Werner@inria.fr.

Envoyez-moi également votre travail à la fin du TD.



2  Principe du tri par sélection

L'algorithme est très simple. On se donne un tableau t à trier, dont les élèment sont indicés de 0 à n. On parcours le tableau pour trouver (``sélectionner'') l'élèment le plus petit, puis on le met à sa place en l'échangeant avec le premier élèment du tableau. On ré-itère ensuite l'opération mais en se restreignant aux élèments 1 à n, puis 2 à n, etc.

Il est facile de voir que ce tri se fait en temps quadratique, en O(n2).

Vous voyez ci-dessous une animation de cet algorithme de tri. Notez que nous partons d'une permutation aléatoire de [0,...,n], ce qui explique que nous aboutissions à une diagonale, une fois le tableau trié (en x, les indices i du tableau; en y les valeurs des t[i]).

Le tri par sélection



Cliquez sur Reload en appuyant sur Shift pour relancer l'animation.


3  Programme

Le programme fera partie d'une classe appellée, par exemple, Select. On utilisera donc un fichier nommé Select.java. Il commence donc par: 
class Select extends MacLib {
Créez donc le fichier, puis définissez les constantes suivantes: la taille du tableau, et l'abscisse et l'ordonnée de la fenêtre dans l'écran.



4  Le tri

Définissez une méthode swap prenant en argument un tableau d'entiers t et deux entiers i et j, puis qui échange les valeurs des cases i et j du tableau.

On rappelle qu'un tableau est toujours passé en argument par référence. C'est-à-dire tout simplement que les opérations faites sur le tableau dans la méthode resteront valables ensuite.

En utilisant la méthode swap, définissez une méthode triant un tableau par sélection.



Pour tester le programme

Insérez dans la procédure un affichage textuel du tableau aprés chaque étape de permutation. Utilisez pour cela la fonction System.out.print qui affiche un entier ou une chaine de caractères. La fonction System.out.println permet d'aller à la ligne à la fin du tableau.

Lancez ensuite le programme sur un petit tableau initialisé à la main. Par exemple quelque chose comme: 
int tableau[] = {0,5,2,4,3,1};
Pour faire tourner le programme, il faut définir la méthode main.



5  Permutation aléatoire

La fonction Math.random renvoie un nombre aléatoire entre 0.0 et 1.0. On peut l'utiliser pour obtenir un entier aléatoire entre 0 et k-1 par: 
 (int) (Math.random() * k)
En utilisant cette fonction, on peut obtenir une permutation aléatoire de 1,...,n en effectuant n tirages aléatoires. À la ième étape, on tire un entier k entre 1 et n-i+1, puis on cherche la kème position libre (c'est-à-dire contenant 0) du tableau et on y met i.

Ecrivez la méthode qui initialise le tableau de manière aléatoire et modifiez la méthode main pour l'utiliser (le tout étant paramètré par la constante définissant la taille du tableau).



6  Animation graphique

Commencez par définir la affiche méthode qui affiche graphiquement l'état du tableau. On rappelle qu'il suffit pour cela de disposer d'une variable r de type Rect. La taille et la position du tableau est définie par 
setRect(r,x,y,largeur,hauteur);
fillRect(r);
où x et y sont le coin en haut à gauche du rectangle. La seconde ligne sert à l'afficher. La couleur à pue être choisie précedemment par foreColor(blackColor); ou foreColor(whiteColor); par exemple.

Vous pouvez essayer votre animation en réaffichant votre tableau à chaque étape. Pour eviter tout clignotement, il est préférable de juste re-dessiner les points modifiés à chaque permutation en modifiant la méthode swap.



7  Solution

Vous trouverez une solution ici vers la fin du TD.



8  Tri à bulles

Il est facile d'utiliser vos outils d'animation pour illustrer un autre programme de tri quadratique, le tri à bulles. L'algorithme consiste à parcourir le tableau en comparant deux éléments successifs et les échangeant le cas échéant. On recommence jusqu'à ce qu'il n'y ait aucune permutation à faire.

Vous trouverez ici une animation du tri à bulles.

Créez un fichier Bulles.java qui fasse la même chose, en utilisant la plupart des méthodes crées précédemment.

Remarquez qu'un coté du tableau est toujours trié plus vite que l'autre. Pourquoi ? Pouvez-vous améliorer votre tri à bulles en évitant cela ?

Voici une solution.

9  Un mot sur les applets

Les applets sont des petits programmes java qui peuvent être exécutés dans une page web. Comme la bibliothèque MacLib ne peut être utilisée dans une applet, les animation de ces pages sont un peu différentes des programmes que vous écrivez. A titre indicatif, voici le code de l'applet du tri par sélection.


Enfin, comme friandise, voici le jeu de Pong de la semaine dernière en applet.



This document was translated from LATEX by HEVEA.