Jouez bien le jeu en n'allant pas rechercher des indices ou des réponses sur Internet car les sujets abordés dans ce T.P. dont des grands classiques de la programmation.
Dans le corrigé, nous préciserons ce qui est communément appelé un "tri par sélection", et aussi pour les plus rapides, nous indiquerons ce que l'on nomme habituellement le "tri par insertion" et le "tri par fusion".
En déménageant sur Chambéry, le professeur LAB a dû déplacer le contenu de sa bibliothèque. Malheureusement pour lui, l'ensemble de son encyclopédie numérotée du chocolat en 20 volumes a bien été placée sur son rayon par les déménageurs mais ces derniers n'ont pas pris le temps de ranger correctement les livres dans le bon ordre.
Le professeur LAB s'étant cassé un bras décide d'utiliser son temps chômé pour remédier enfin à ce problème laissé de côté pendant plusieurs mois. Il décide de s'y prendre comme suit.
Il va chercher le premier livre de son encyclopédie, celui numéroté $1$, et non $0$ comme en Python.
Il prend ce livre et le place tout à gauche à sa position. Pour cela, il suffit...
Il cherche ensuite le livre numéroté $2$ parmi les livres après le premier bien rangé pour le placer à sa bonne deuxième position en partant de la gauche. La méthode est similaire au point précédent si ce n'est que l'on ne touche plus au premier livre qui est sa bonne position.
Le professeur LAB poursuit alors le rangement avec le livre numéro $3$ en le cherchant parmi les livres après les deux premiers bien rangés, puis vient celui numéroté $4$ en le cherchant parmi les livres après les trois premiers bien rangés, etc...
Voici ce que vous devez faire.
Traduire et adapter la méthode utilisée par le professeur LAB en un algorithme triant, du plus petit élément au plus grand, une liste quelconque d'entiers. Autrement dit, l'algorithme doit fonctionner quelque soit la taille de la liste, et aussi si cette liste contient des entiers se répetant et/ou non forcément tous consécutifs une fois rangés. Attention ! Pour M. LAB, la liste de taille égale à 20 ne contient que des entiers consécutifs à ordonner. **Si vous ne trouvez pas comment commencer**, vous pouvez jetez un oeil à [cette animation](images/selection-sort.gif) *(image en licence CC BY-SA 3.0 dont la source sera donnée dans le corrigé)*.
Traduire l'algorithme en une fonction tri_lab_bc à l'aide du langage Python.
Tester la fonction en l'appliquant à certaines listes particulières.
Ajouter enfin des tests aléatoires (voir les indications données dans le code ci-dessous).
Remarque : l'énoncé étant assez ouvert, rien ne vous interdit de choisir une technique particulière d'algorithmique puis de programmation, et/ou d'utiliser d'autres fonctions intermédiaires dans votre code. Le tout est de respecter la méthode de tri.
# --------------------- #
# -- À VOUS DE JOUER -- #
# --------------------- #
# tri_lab_bc : [tri] du professeur [LAB] au [b]ras [c]assé.
def tri_lab_bc(une_liste):
...
# --------------- #
# -- VOS TESTS -- #
# --------------- #
import random
# Étant donnée une liste ``une_liste``, l'utilisation de
# ``random.shuffle(une_liste)`` a pour effet de "mélanger"
# au hasard la liste.
Testez votre fonction non plus sur une liste d'entiers mais sur une liste de chaînes de caractères. Comment Python réagit-il ? En cas de problème, sauriez-vous améliorer votre fonction tri_lab_bc pour qu'elle fonctionne aussi avec une liste de chaînes de caractères ?
# ATTENTION !
#
# La cellule précédente contenant le code de la fonction ``tri_lab_bc``
# a dû étre activée juste avant !
# ---------------------- #
# -- À VOUS DE TESTER -- #
# ---------------------- #
...
Reprendre la démarche suivie pour le tri de type "par sélection" au cas concret suivant. Les avertissements sont identiques à ceux pour le(s) tri(s) de type "par sélection".
La convalescence du professeur LAB étant fini, il peut s'adonner à son activité favorite, à savoir jouer aux cartes (mais avec un jeu utilisant la numérotation bibi-binaire mais peu importe). Il range de gauche à droite ses cartes dans l'ordre croissant pour les valeurs chiffrés de $2$ à $10$, puis viennent le valet, la dame, le roi et l'as, et il range toujours les cartes par catégorie de gauche à droite dans l'ordre "carreau", "pic", "coeur" et "treffle". En fait ceci n'est pas très important mais cela montre qu'il y a plusieurs façons de ranger des objets. **Dans la suite, vous pouvez considérer que le jeu de cartes est constitué de cartes portant toutes des numéros naturels distincts.**
Devant répondre au téléphone lors de la distribution des cartes, le professeur LAB doit ranger toutes ses cartes en main et non au fur et à mesure comme à son habitude (et aussi comme beaucoup de joueurs le font).
Dans sa main, il part de la deuxième carte à partir de la gauche. Si cette carte doit être rangée avant la première il échange leurs places respectives.
Vient ensuite le cas de la troisième carte qu'il place à la bonne position parmi les trois cartes tout à gauche. Notons que comme les deux premières cartes sont bien rangées, il suffit de déplacer la troisième carte vers la gauche tant qu'à sa gauche se trouve une carte de rang plus élevé.
Pour la carte à la quatrième position, la démarche reste la même. Toujours en notant que les trois premières cartes étant bien rangées, il suffit de déplacer la quatrième carte vers la gauche tant qu'à sa gauche se trouve une carte de rang plus élevé.
Le professeur continue ainsi jusqu'à bien placer sa carte la plus à droite dans sa main initiale.
**Si vous ne trouvez pas comment commencer**, vous pouvez jetez un oeil à [cette animation](images/insertion-sort.gif) *(image en licence CC BY-SA 3.0 dont la source sera donnée dans le corrigé)*.
Remarque : le tri de type "par insertion" est intéressant car il s'adapte facilement au cas de données à trier reçues les unes après les autres et non toutes d'un coup. Dans la vraie vie, imaginons avoir un tas de livres sur une table à ranger dans une bibliothèque. Dans ce cas, on peut les ranger les uns après les autres assez efficacement grâce à un tri de type "par insertion".
# --------------------- #
# -- À VOUS DE JOUER -- #
# --------------------- #
def tri_insertion(une_liste):
...
# --------------- #
# -- VOS TESTS -- #
# --------------- #
...
Reprendre la démarche suivie pour le tri de type "par sélection" au cas concret suivant. Les avertissements sont identiques à ceux pour le(s) tri(s) de type "par sélection".
La partie de cartes étant finie, le professeur Lab propose pour détendre l'atmosphère d'écouter un peu de musique algorithmique dans son salon qui contient une très grande table d'époque. Malheureusement pour lui, ses $256$ CDs sont disposés totalement en vrac car il n'avait pas pu les ranger lors de son déménagement (pour ceux qui ont oublié ce qu'est un CD, se rendre sur Wikipédia par exemple). Le professeur Lab propose à ses huit amis de l'aider à mettre de l'ordre dans ce réel fatras musico-numérique en rangeant ses CDs qui sont numérotés sur la tranche par leur date d'édition. Voici sa méthode.
Faire deux tas contenant exactement le même nombre de CDs, soit $128$ ici. Concrètement il suffit de faire des piles de même hauteur sans chercher à compter les CDs.
Diviser chacun des deux tas en deux sous-tas contenant exactement le même nombre de CDs, soit $64$ ici.
On continue ainsi jusqu'à n'avoir que des CDs isolés. Combien d'étapes a-t-il fallu pour arriver à ce stade ?
Le professeur demande alors à chacun de s'occuper de deux CDs consécutifs pour les mettre sur leur tranche dans le bon ordre de gauche à droite. Il va falloir traiter tous les couples de CDs : chacun va ordonner $\dfrac{128}{8} = 16$ couples de CDs.
Ensuite, chacun prend deux piles rangés de couples de CDs pour former une séries bien ordonnée de quatre CDs. Chacun va s'occuper de $\dfrac{64}{8} = 8$ fusions de couples de CDs. Étant donné que chaque couple est bien rangé, le travail n'est pas trop complexe.
On poursuit ensuite jusqu'à n'avoir qu'une grande rangée de $256$ CDs tous bien rangés (l'histoire ne dit pas si les amis du professeur lui en ont voulu longtemps pour cette activité de rangement fort passionnante).
Remarque 1: les lycées proposant des formations post-bac doivent courant avril-mai trier des dossiers d'élèves avant de pouvoir les analyser en vue d'une intégration à l'une des formations proposées. Dans certains cas, les dossiers sont encore gérés sous forme de dossiers réels. Si, si, vous ne rêvez pas. L'utilisation d'un tri de type "par fusion" peut s'avérer dans ce cas être très utile.
Remarque 2: si programmer de la musique vous attire, vous pouvez essayer en dehors du cours le programme Sonic Pi.
# --------------------- #
# -- À VOUS DE JOUER -- #
# --------------------- #
def tri_fusion(une_liste):
...
# --------------- #
# -- VOS TESTS -- #
# --------------- #
...
Cette page propose divers tris tous appliqués à différents types "intéressants" de listes. Si le sujet vous intéresse il y a là de quoi s'amuser à programmer certains tris.