5.6. Tris

On décrit les algorithmes au programmme permettant de trier un tableau de valeurs numériques.

5.6.1. Tri par insertion

Le principe est très simple : c’est l’algorithme qu’utilise naturellement l’être humain pour trier des objets coomme par exemple des cartes à jouer.

On procède en plusieurs étapes. On suppose qu’à l’étape \(i\), les éléments d’indice \(0\) à \(i-1\) du tableau sont déjà triés et on insère alors l’élément d’indice \(i\) à sa place parmi les éléments précédents.

Un dessin vaut probablement mieux qu’un long discours.

On peut alors proposer la fonction Python suivante.

In [1]: def tri_insertion(tab):
   ...:     for i in range(1,len(tab)):
   ...:         val = tab[i]
   ...:         pos = i
   ...:         while pos > 0 and tab[pos - 1] > val:
   ...:             tab[pos] = tab[pos-1]
   ...:             pos -= 1
   ...:         tab[pos] = val
   ...: 

On vérifie qu’elle fonctionne bien sur quelques tableaux choisis aléatoirement.

In [2]: from numpy.random import randint

In [3]: tab = randint(100, size=20)

In [4]: tab
Out[4]: 
array([11, 47, 10, 57, 95, 47, 56, 38, 37, 76, 90, 77,  0, 63, 72, 18, 54,
       48,  9, 15])

In [5]: tri_insertion(tab)

In [6]: tab
Out[6]: 
array([ 0,  9, 10, 11, 15, 18, 37, 38, 47, 47, 48, 54, 56, 57, 63, 72, 76,
       77, 90, 95])

5.6.2. Tri rapide

In [7]: def tri_rapide(tab):
   ...:     if tab == []:
   ...:         return []
   ...:     else:
   ...:         pivot = tab[0]
   ...:         t1, t2 = [], []
   ...:         for x in tab[1:]:
   ...:             if x < pivot:
   ...:                 t1.append(x)
   ...:             else:
   ...:                 t2.append(x)
   ...:         return tri_rapide(t1) + [pivot] + tri_rapide(t2)
   ...: 

In [8]: from numpy.random import randint

In [9]: tab = randint(100, size=20)

In [10]: tab
Out[10]: 
array([54, 68, 93,  2, 25, 64, 69, 19, 15, 67, 87, 33, 79, 62, 21, 71, 34,
        9, 19,  3])

In [11]: tri_rapide(tab)
Out[11]: [2, 3, 9, 15, 19, 19, 21, 25, 33, 34, 54, 62, 64, 67, 68, 69, 71, 79, 87, 93]

5.6.3. Tri par fusion

In [12]: def tri_fusion(tab):
   ....:     if len(tab) < 2:
   ....:         return tab
   ....:     else:
   ....:         m = len(tab)//2
   ....:         return fusion(tri_fusion(tab[:m]), tri_fusion(tab[m:]))
   ....: 

In [13]: def fusion(t1, t2):
   ....:     i1, i2, n1, n2 = 0, 0, len(t1), len(t2)
   ....:     t=[]
   ....:     while i1 < n1 and i2 < n2:
   ....:         if t1[i1] < t2[i2]:
   ....:             t.append(t1[i1])
   ....:             i1 += 1
   ....:         else:
   ....:             t.append(t2[i2])
   ....:             i2 += 1
   ....:     if i1 == n1:
   ....:         t.extend(t2[i2:])
   ....:     else:
   ....:         t.extend(t1[i1:])
   ....:     return t
   ....: 

In [14]: from numpy.random import randint

In [15]: tab = randint(100, size=20)

In [16]: tab
Out[16]: 
array([53, 85, 91, 88, 43,  3, 22, 51, 90,  6, 37, 22, 50, 11, 71, 95, 31,
       40, 55, 40])

In [17]: tri_fusion(tab)
Out[17]: [3, 6, 11, 22, 22, 31, 37, 40, 40, 43, 50, 51, 53, 55, 71, 85, 88, 90, 91, 95]