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.

Activité

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 :

Toutes les fonctions de tri présentées devront trier les liste « 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.

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 » :

 


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.
i = 1
9 6 1 4 8
6 9 1 4 8
i = 2
6 9 1 4 8
1 6 9 4 8
i = 3
1 6 9 4 8
1 4 6 9 8
i = 4
1 4 6 9 8

1 4 6 8 9

Algorithme

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
Activité
  • Implémenter en Python une fonction tri_insertion(L) .
  • Déterminer un variant de la boucle while  et montrer la terminaison de cet algorithme.
  • Déterminer sa complexité.

 


Tri par sélection

  1. On cherche le minimum dans la liste.
  2. On échange ce minimum avec le premier élément de la liste.
  3. 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.

Activité

Implémenter en Python une fonction tri_selection(L) .


Ressource LUMNI

http://www.lumni.fr/video/les-algorithmes-de-tri

 

 

sources :

https://fr.wikipedia.org/wiki/Algorithme_de_tri

http://cache.media.eduscol.education.fr/file/ISN_Tle_S/29/6/lyceeGT_ressource_ISN_20_06_Tle_S_14_Vous_avez_dit_trier_1_algorithmes_218296.pdf

Vous aimerez aussi...

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*

code