Algorithmes de tris
Un opération que l'on veut faire couramment sur des lists est le tri. Un tri consiste à réorganiser les éléments selon un ordre.
Par exemple, si on trie la liste 1, 5, 2, 7, 8 par ordre croissant, on obtient 1, 2, 5, 7, 8.
Il y a de nombreuses raisons de vouloir trier une liste, comme par exemple avoir un affichage plus lisible pour un humain. Une autre raison est de pouvoir utiliser des algorithmes plus efficaces.
Activité : liste triée ?
Prenez les cartes du chapitre précédent (2 - 10 et l'As). Retirez le 3. Appliquez l'algorithme du chapitre précédent pour trouver le 3 (qui est absent) et comptez le nombre de fois où vous retournez une carte.
Récupérez les cartes et triez-les de la plus forte à la moins forte. Vous pouvez regarder toutes les cartes à la fois pour les trier. Laissez toujours le 3 en dehors du paquet. Disposez-les ensuite face cachée, de la moins forte (à gauche) à la plus forte (à droite). Appliquez l'algorithme suivant en comptant le nombre de cartes que vous retournez :
On commence par la carte de gauche, qui devient la *carte courante*.
(1) On retourne la *carte courante* :
- Si elle est le 3, on s'arrête et le 3 est présent.
- Sinon, si elle est plus forte que le 3, on s'arrête et le 3 n'est pas présent.
- Sinon, si elle n'a pas de carte à sa droite, on s'arrête et le 3 n'est pas présent.
- Sinon, la carte à sa droite devient la *carte courante*, et on retourne en (1).
Si on n'exclut le temps passé pour trier les cartes, quel algorithme vous a fait retourner le moins de cartes ?
Tri de cartes
Bon c'est bien sympa, mais... Comment on trie une liste ? Et là normalement vous devez vous dire quelque chose comme :
Oueche le prof il est teubé, il nous a fait trier les cartes juste avant, on sait faire, lol !
Oui, mais rappelez-vous de les contraintes qu'on s'était fixé à la base :
On supposera les cartes posées sur la table, côte à cote sur une ligne, face cachée. On s'autorisera, au maximum, à avoir deux cartes face visible à la fois, et à ne déplacer que des cartes visibles.
Et là, vous faites moins les marioles. Allez hop, activité !
Actitivé
Proposez un algorithme qui permet de trier les cartes de la moins forte (a gauche) à la plus forte (à droite) en respectant la règle mentionnée plus haut. Vous montrerez cette méthode aux autres groupes.
Cette activité est longue et difficile ! Ne perdez pas espoir !
Essayez de trier les cartes face visible et observez comment vous faites.
Essayez de trier un petit nombre de cartes, par exemple 4 ou 5, puis passez à un grand nombre quand vous pensez avoir la solution.
Peut-être que vous aurez besoin de chercher la carte la moins forte dans une partie de la liste. N'hésitez pas à élaborer un sous-algorithme pour celà.
Essayez éventuellement de "reconstituer" une autre liste triée, à côté, en déplaçant les cartes.
Numérotons les positions des cartes de gauche à droite en partant de 0. On supposera qu'on a n cartes.
Voici un algorithme qui permet de trouver la carte la moins forte :
Si il n'y a qu'une carte, alors c'est celle-ci la moins forte et on s'arrête.
On retourne la carte la plus a gauche, face visible.
La deuxième carte en partant de la gauche devient la *carte courante*.
(1) On retourne la carte courante face visible:
- On retourne la carte la plus des deux cartes visibles en face cachée.
- Si il n'y a pas de carte à droite de la *carte courante*, on va en (2)
- Sinon, la carte à droite de la *carte courante* devient la *carte courante*.
(2) La carte la plus faible est celle qui est face visible. On s'arrête.
Voici un algorithme qui permet de trier les cartes :
Tri par sélection
TODO (prof) ici ajouter des étapes pour passer des cartes à l'algo ?
On peut commenser par définir un algorithme qui fait la recherche du minumum dans une partie de la liste.
(recherche indice minimum)
Entrée : une liste (ou tableau) l, de longueur n > 0, un entier i < n
Sortie : m est l'indice de la plus petite valeur dans l à partir de la position i inclus
m = i
pour j allant de i + 1 à n (exclut):
si l[j] < l[m]:
m = j
Le tri par sélection est alors :
(tri par sélection)
Entrée : une liste (ou tableau) l, de longueur n
Sortie : la liste (ou tableau) l est triée en ordre croissant
pour i allant de 0 à n - 1 (exclut):
rechercher l'indice m de la plus petite valeur de l à partir de l'indice i.
echanger l[i] et l[m]
D'un seul bloc, le pseudocode du tri par sélection est:
(tri par sélection)
Entrée : une liste (ou tableau) l, de longueur n
Sortie : la liste (ou tableau) l est triée en ordre croissant
pour i allant de 0 à n - 1 (exclut):
m = i
pour j allant de i + 1 à n (exclut):
si l[j] < l[m]:
m = j
echanger l[i] et l[m]
Tri par insertion
Activité : insertion triée
Retirez deux cartes au hasard de votre paquet, sans les regarder. Triez les cartes restantes comme vous le souhaitez, puis disposez les dans l'ordre fache cachée, côte à côte.
Toujours en respectant les contraintes précédentes, proposez un algorithme qui permet d'ajouter une carte à votre liste de carte face cachée. A la fin de votre ajout, votre liste de carte doit être triée.
Attention, vous ne pouvez déplacer que des cartes face visible !
Voici un algorithme possible :
On ajoute la carte à insérer toute à droite de la liste (donc du côté de la carte la plus forte), face visible.
tant que la carte à insérer a une carte à sa gauche :
on retourne la carte à sa gauche face visible.
Si la carte à insérer est moins forte que la carte à sa gauche, on les échange de place, puis on retourne en face cachée la carte à la gauche de la carte à insérer.
Si la carte à insérer est plus forte ou aussi forte que la carte à sa gauche, on s'arrête.
On pose la carte à un des deux bouts de la liste. Puis on trie la liste.
Activité : tri par insertion
Proposez un algorithme qui utilise l'insertion triée dans une liste de cartes pour trier une liste de cartes.
Essayez d'abord en recréant une nouvelle liste triée.
L'algorithme de sélection peut donc être décrit comme suit :
(insertion triée)
Entree : une liste l de n éléments, i un entier < n. les i-1 premiers éléments de l sont triés en ordre croissant.
Sortie : Les i premiers éléments de l sont triés en ordre croissant.
j = i
tant que j > 0 et l[j] < l[j-1]:
echanger l[j] et l[j-1]
j = j - 1
(tri par insertion)
Entrée : une liste (ou tableau) l, de longueur n
Sortie : la liste (ou tableau) l est triée en ordre croissant
pour i allant de 1 à n - 1 (inclus):
on fait une insertion triée avec l et i
D'un seul bloc, le pseudocode du tri par insertion donne :
Entrée : une liste (ou tableau) l, de longueur n
Sortie : la liste (ou tableau) l est triée en ordre croissant
pour i allant de 1 à n - 1 (inclus):
j = i
tant que j > 0 et l[j] < l[j-1]:
echanger l[j] et l[j-1]
j = j - 1
Comparateur
En fait, parfois on veut pouvoir trier de plusieurs manières différentes : ordre croissant, ordre décroissant, ...
Activité : ordre des cartes
Proposez au moins 3 manières différentes d'ordonner les cartes.
- Par "force", sans regarder les couleurs
- Par "numéros", en considérant J = 11, Q = 12, K = 13 et A = 1
- Par "couleurs puis force", c'est à dire d'abord par couleur (trefle < pique < carreau < coeur), puis dans chaque couleur par "force".
En fait, pour trier, seul l'ordre change, et non le principe de l'algorithme de tri. Dans notre tri par sélection plus haut, l'ordre est donné par le comparateur <.
TODO (prof) continuer ici