Algorithmique et langage Java
Tri par sélection
Le code écrit précedemment peut être utilisé pour ranger les éléments d'un tableau par ordre croissant, en utilisant la méthode de tri "par sélection". Exercice 8 :
Dans un programme appelé "SelectionSimple" :
Créer un tableau contenant des nombres aléatoires entre 0 et 100. Afficher les éléments du tableau.
Créer un second tableau de même type et même taille, sans donner de valeur à ses éléments (par défaut, ils valent 0)
Ecrire le code qui réalise l'algorithme suivant, ou représenter son algorigramme :
Afficher les éléments du tableau pour vérifier l'efficacité du tri. A quoi sert de remplacer chaque valeur copiée dans le second tableau par un nombre plus grand que 100 dans le premier tableau?
Ce programme effectue un tri par sélection, mais il consomme inutilement de la mémoire,
puisqu'il faut utiliser deux tableaux, d'autant que le contenu du premier est modifié par le programme.
Créer un tableau contenant des nombres aléatoires entre 0 et 100. Afficher les éléments du tableau.
Créer un second tableau de même type et même taille, sans donner de valeur à ses éléments (par défaut, ils valent 0)
Ecrire le code qui réalise l'algorithme suivant, ou représenter son algorigramme :
- Chercher la plus petite valeur contenue dans le premier tableau, et la placer en position 0 dans le second tableau. Dans le premier tableau, la remplacer par un nombre plus grand que 100.
- Recommencer, en plaçant cette fois la valeur trouvée en position 1 dans le second tableau, et en la remplaçant toujours par un nombre plus grand que 100 dans le premier tableau.
- et ainsi de suite jusqu'à avoir atteint la fin des tableaux
Afficher les éléments du tableau pour vérifier l'efficacité du tri. A quoi sert de remplacer chaque valeur copiée dans le second tableau par un nombre plus grand que 100 dans le premier tableau?
On peut cependant améliorer l'algorithme pour pouvoir réaliser un tri "en place", c'est à dire à l'intérieur du tableau lui-même.
- Pour un tri par ordre croissant :
- On considère le premier élément du tableau (indice 0). L'objectif de la première étape est d'amener dans cette position le plus petit élément du tableau.
On parcourt le reste du tableau, à partir de l'indice 1. Quand on trouve un élément plus petit que celui d'indice 0, on les échange. On va ainsi jusqu'au bout du tableau. - On considère ensuite le deuxième élément du tableau (indice 1). Il faut amener à cette position le plus petit des éléments restants.
On parcourt le reste du tableau, à partir de l'indice 2. Quand on trouve un élément plus petit que celui d'indice 1, on les échange. - et ainsi de suite jusqu'à ce qu'on soit arrivé à la fin du tableau.
Exercice 9 : Ecrire le code réalisant cet algorithme, ou représenter son algorigramme.
Auteur : Nathalie Bonnin
Professeur de Physique, Chimie, Informatique au lycée La Martinière Monplaisir (Lyon 8ème)
Contact :
nathalie.bonnin (chez) scientillula.net