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
        j ← i
        tant que j > 0 et L[j-1] > L[j] faire
            L[j], L[j-1] ← L[j-1], L[j]
            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.

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 plus petite taille, puis de fusionner les résultats.On pousse ce raisonnement jusqu’à obtenir des tableaux de taille 1 (déjà triés !!).

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 si
   fin pour
fin procédure

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

Comparaison des algorithmes de tri

Le script ci-dessous permet de comparer les performance des divers algorithmes de tri.

# -*- coding: utf-8 -*-

import timeit

import matplotlib.pyplot as pl

import numpy as np

from random import *


taille = 1000
T = [random() for i in range(taille)]     # Liste de nombres aléatoires en désordre
T_trie = sorted(T)                      # Liste de nombres aléatoires triée
T_inv = list(reversed(T_trie) )         # Liste de nombres aléatoires en ordre inverse



###############################################################################
#  Tri sélection
###############################################################################

def tri_selection(t):
    pass


###############################################################################
#  Tri insertion
###############################################################################
def tri_insertion(t):
    pass


###############################################################################
#  Tri à bulles
###############################################################################
def tri_a_bulles(t):
    pass


###############################################################################
#  Tri fusion
###############################################################################
def fusion(t1, t2):
    pass

   
def tri_fusion(t):
    pass


###############################################################################
#  Tri python
###############################################################################
def tri_python(t):
    t.sort()




########################################################################################################
# Comparaison des algorithmes de tri
########################################################################################################
pl.subplot(2,1,2)
n = range(taille//40, taille, taille//40)
liste_fct = [tri_selection, tri_insertion, tri_a_bulles, tri_fusion, tri_python]
for tri in liste_fct:
    print(tri.__name__)
    d = []
    Y = []
    for TT in [T, T_trie, T_inv]:
        d = []
        for i in n:
            t = TT[:i]
            d.append( timeit.timeit("tri(t)", globals=globals(), number=100))
        #print(tri.__name__, i, ":",d[-1])
        Y.append(np.array(d))
        
    p, = pl.plot(n, Y[0], label = tri.__name__)
    pl.fill_between(n, Y[1], Y[2], color = pl.getp(p, 'color'), alpha=0.5)

pl.legend(loc=2)
pl.xlabel('taille du tableau') 
pl.ylabel('durée du tri [s]')
pl.show()

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