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.

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

def tri_insertion_i2(L): 
    n = len(L) 
    for i in range(n-1, 0, -1): 
        j = i 
        while j+1 < n and L[j+1] > L[j]: 
            L[j], L[j+1] = L[j+1], L[j]
            j += 1

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.

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