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)