La meilleure façon de trier

 

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.

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

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.


Tri à bulles

  • On balaye la liste :

si deux éléments consécutifs sont dans le mauvais ordre, on les échange.

Le plus grand élément de la liste est donc repoussé à la fin.

  • On recommence à partir du début, avec les n‒1 premiers éléments et ainsi de suite.

Cela ressemble un peu au tri par sélection, à ceci près qu’on utilise la recherche du maximum pour corriger quelques autres inversions.

 

Algorithme

procédure tri_à_bulles(liste L)
   n ← taille de L
   pour i allant de n-1 à 1
      pour j allant de 0 à i-1
         si L[j+1] < L[j] alors
            échanger L[j+1] et L[j]
      fin pour
   fin pour
fin procédure

Tri fusion

Le tri fusion est construit suivant la stratégie « diviser pour régner ». Le principe de base de cette stratégie est que pour résoudre un gros problème, il est souvent plus facile de le diviser en petits problèmes élémentaires. Une fois chaque petit problème résolu, il n’y a plus qu’à combiner les différentes solutions pour résoudre le problème global.

Cette stratégie est tout à fait applicable au problème de tri : plutôt que de trier le tableau complet, il est préférable de trier deux sous-tableaux de taille égale, puis de fusionner les résultats. C’est lors de la fusion que l’on ordonne les éléments.

On est en présence d’une procédure récursive : la procédure de tri s’appelle elle-même.

Algorithme

procédure fusion(liste L, liste L1, liste L2)
   j ← k ← 0
   n1 ← taille de L1
   n2 ← taille de L2
   pour i allant de 0 à n1+n2-1
      si j < n1 et (k >= n2 ou L1[j] <= L2[k]) alors
         L[i] ← L1[j]
         j ← j + 1
      sinon
         L[i] = L2[k]
         k ← k + 1
   fin pour
fin procédure

procédure tri_fusion(liste L)
   n ← taille de L
   si n == 1 alors
      retour
   n1 ← n/2
   pour i allant de 0 à n1-1
      L1[i] ← L[i]
   pour i allant de 0 à n-n1-1
      L2[i] ← L[n1+i]
   tri_fusion(L1)
   tri_fusion(L2)
   fusion(L, L1, L2)
fin procédure

 

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