Algorithmes de tri
Comment ranger des données afin de faciliter leur accès futur ?
C’est par exemple l’ordre alphabétique du dictionnaire, où les mots sont rangés dans un ordre logique qui permet de ne pas devoir parcourir tout l’ouvrage pour retrouver une définition. Ce peut être aussi l’ordre intuitif dans lequel un joueur de cartes va ranger son jeu afin de limiter le temps de recherche pendant le déroulement de la partie.
Cette problématique permet d’introduire la notion de tri (avec plusieurs sens distincts : séparer, ordonner, choisir), puis d’étudier différents algorithmes de tri.
Le tri permet essentiellement d’accélérer les recherches, grâce à l’algorithme de recherche dichotomique.
Un joueur de tarot reçoit 18 cartes lors de la donne en début de partie ; il les trie ensuite pour faciliter la lecture de son jeu.
Par groupes de 3 :
- Trier un jeu de 18 cartes de tarot.
- Notez, de manière précise, la manière de procéder.
Pour la suite, nous utiliserons Python, et travaillerons sur une liste de nombres entiers générés aléatoirement :
from random import randint L0 = [randint(1, 1000) for i in range(100)]
Toutes les fonctions de tri présentées devront trier les listes « en place » : la liste passée en argument à la fonction de tri finit modifiée à la fin de l’exécution. Aucune copie n’est réalisée. La fonction ne renvoie rien.
Par conséquent, et afin de comparer l’efficacité des différentes fonctions, il faudra travailler sur des copies d’une même liste « mère » :
L = L0[:]
Tri par insertion
Le tri par insertion est le tri que la majorité des joueurs de cartes occasionnels pratiquent intuitivement.
Il consiste à «traiter» toutes les cartes dans l’ordre découlant de la donne, le «traitement» se résumant, pour chaque carte, à l’insérer au bon endroit dans l’ensemble des cartes déjà triées.
Matériellement, cette opération peut être réalisée selon deux variantes :
Soit avec deux tas de cartes, l’un sur la table, résultat de la donne, l’autre dans la main du joueur, contenant le jeu trié. L’opération de tri commence alors avec la totalité des cartes sur la table, et se termine avec la totalité des cartes dans la main du joueur.
- Soit directement dans la main du joueur, celle-ci étant partagée mentalement en un côté «trié» et un côté «pas encore trié». L’opération de tri consiste alors à faire passer les cartes de l’un à l’autre en les insérant au bon endroit.
Exemple :
Algorithme
Par sauvegarde et décalage
procédure tri_insertion(liste L) n ← taille de L pour i allant de 1 à n-1 x ← L[i] j ← i tant que j > 0 et L[j-1] > x faire L[j] ← L[j-1] j ← j - 1 fin tant que L[j] ← x fin pour fin procédure
Par permutations
procédure tri_insertion(liste L) n ← taille de L pour i allant de 1 à n-1 x ← L[i] j ← i tant que j > 0 et L[j-1] > x faire L[j] ← L[j-1] j ← j - 1 fin tant que L[j] ← x fin pour fin procédure
Tri par sélection
- On cherche le minimum dans la liste.
- On échange ce minimum avec le premier élément de la liste.
- On recommence avec le reste de la liste, jusqu’au dernier élément.
Algorithme
procédure tri_selection(liste L) n ← taille de L pour i allant de 1 à n-1 min ← i pour j allant de i+1 à n si L[j] < L[min] alors min ← j fin pour si min ≠ i alors échanger L[i] et L[min] fin pour fin procédure
Remarque : on peut, alternativement, prendre le plus grand et l’échanger avec le dernier.
Ressource LUMNI
http://www.lumni.fr/video/les-algorithmes-de-tri
sources :