On envisage une collection, par exemple un tableau, dont on souhaite trier les items par exemple par ordre croissant.
Il est facile de comprendre ce que l'on veut dire par « trier par ordre croissant » si notre tableau ne contient que des nombres.
[14, 8, 17, 22, 3, 9] → [3, 8, 9, 14, 17, 22]
Mais les tris ne se limitent pas au nombres et trier de simples nombres est quasiment sans intérêt ! Sur un site internet, nous allons par exemple trier des articles sur un site marchand et alors il faut définir un critère de tri : par prix, par popularité, par pertinence…
On devra donc envisager de pouvoir trier des objets plus compliqués à condition d'indiquer un critère de tri.
Dans la suite, on envisage le tris d'items a, b, c, d… On considérera que des tests comme a < b ou a <= b sont compris. Pour faire plus simple, a, b, c, d… seront de simples nombres. Gardez à l'esprit qu'en pratique, ce seront des objets plus compliqués mais que cela ne change rien aux algorithmes que nous allons étudier.
Je souhaite avoir une fonction tri qui reçoit un tableau tab et qui le trie.
Un réflexe courant de débutant est de créer un tableau trié qui se construit en vidant progressivement tab, de sorte qu'à la fin de l'opération, tab est vidé. C'est un mauvaise pratique. On essaie autant que possible d'éviter qu'une fonction détruise le contenu d'une donnée fournie en entrée car cela entraîne de grandes difficultés.
En Python, les tableaux sont dynamiques. Cela signifie qu'ils ont la capacité de modifier leur taille. On peut ajouter des éléments, en enlever… Mais,
Ceci considéré, que veut-on ?
tab lui-même ? Dans ce cas on parle de tri en place. La fonction ne va pas à renvoyer de tableau puisque le tableau trié est tab.tab mais triée, tab restant inchangé. Dans ce cas, la fonction renvoie la copie triée.Les langages fournisse les deux options :
>>> tab = [14, 8, 17, 22, 3, 9] >>> tab.sort() # tri en place, ne renvoie rien >>> tab [3, 8, 9, 14, 17, 22] >>> tab = [14, 8, 17, 22, 3, 9] >>> sorted(tab) # renvoie une copie triée [3, 8, 9, 14, 17, 22] >>> tab # n'a pas changé [14, 8, 17, 22, 3, 9]
Nous allons envisager des tris en place. L'autre version ne crée pas de difficulté : il suffit de commencer par faire une copie de tab puis de trier en place la copie.
Pour trier, on doit comparer deux à deux les éléments d'un tableau. On n'est pas obligé de comparer chaque item avec tous les autres. Chaque comparaison prend un certain temps et il est possible d'accélérer le tri en choisissant bien les comparaisons à faire.
Prenons l'exemple du tri de trois items abc. Il y a six ordres possibles. En comparant les valeurs : a < b ? a < c ? b < c ? on peut déterminer l'ordre croissant. Ce graphique représente l'ensemble des cas.
2 tests suffisent parfois. Les cas bac et cba ne sont pas spécialement plus simples. C'est seulement que nous avons choisi de tester a < b en premier et b < c en deuxième. On peut dire que si le bon tri était bac ou cba et que nous avons choisi de tester a < b puis b < c, on a fini en deux tests, on a eu de la chance de faire juste ce qu'il fallait. Mais on ne peut pas le prévoir d'avance.
Dans ce cas on dirait que notre tri a un coût de 2 au mieux et 3 au pire. En général, seul le coût dans le pire des cas nous intéresse car nous ne voulons pas avoir à compter sur la chance.
Pourquoi 3 ici ? Avec 3 items à trier, nous avons $3! = 1 \times 2 \times 3 = 6$ ordre possibles. Chaque test bien choisi permet d'éliminer à peu près la moitié des possibilités restantes. $2^2 = 4 < 6 < 2^3 = 8$. Il nous faut donc 3 tests en général.
Avec 4 items à trier, $4! = 1 \times 2 \times 3 \times 4 = 24$, il nous faudra 5 tests car $2^5 = 32$.
Question : Combien faut-il de tests pour 10 items à trier ?
Comme souvent en informatique, on cherche à connaître le $x$ tel que $2^x = A$ pour un $A > 0$ donné. La fonction logarithme est là pour cela – maths de terminale. Je vous donne la formule :
$$2^x = A, \text{ avec } A > 0 \Rightarrow x = \log_2(A) = \frac{\ln(A)}{\ln(2)}$$
La touche $\ln$ – logarithme népérien – est présente sur vos calculatrices.
Pour un tableau de $n$ items, un algorithme ne pourra pas espérer faire moins que $\log_2(n!)$ comparaisons dans tous les cas. Pour $n$ assez grand, cela est comparable à $n\log_2(n)$. Certains algorithmes ont un coût de calcul du même ordre de grandeur et on sait qu'on ne pourra pas mieux faire. Les deux algorithmes que nous allons étudier en première (tri par sélection, tri par insertion) sont beaucoup moins efficace. Ce n'est pas gênant si le tableau à trier est de petite taille (jusqu'à 1000, ça va) mais pour de gros tableaux, ils deviennent inutilisables.
On appelle complexité une estimation du temps d'exécution d'un algorithme. Le temps réel dépendrait de la machine. À ce niveau théorique on s'intéresse seulement au nombre d'instructions exécutées en supposant qu'elles sont toutes élémentaires et exécutées en un même temps.
Le calcul que l'on fait peut dépendre du tableau. Est-il plus rapide de trier un tableau déjà dans l'ordre ? En général on s'intéresse à la complexité dans le cas le plus défavorable.
On n'a pas besoin de trop se poser de questions d'efficacité si le tableau ne contient que 10, 50 ou 100 items. Les cas intéressant sont ceux avec n grand.
Supposons que vous ayez trouvé que $C(n) = 3n^2 + 17n + 32$. On comprend que si $n = 1\,000\,000$, le terme $3n^2$ pèse incomparablement plus lourd que les deux autres. On ne s'intéresse alors qu'à celui là.
On parle de coût asymptotique car on s'intéresse à $n\to+\infty$ – vous comprendrez mieux le sens du mot quand vous aurez fait le cours de math correspondant.
Ce qu'on cherche à savoir, c'est comment évolue le temps de calcul en fonction de n. Si par exemple j'ai estimé que le temps était en $3n^2$, on obtient le tableau suivant :
| n | 100 | 1000 | 10 000 |
| C | 30 000 | 3 000 000 | 300 000 000 |
On constate que quand $n \to 10 n$, alors $C \to 100 C$. Par exemple un tableau 10 fois plus gros mettrait 100 fois plus de temps à être trier. Ce rapport dépend seulement de $n^2$, le 3 devant $n^2$ n'a pas grande importance.
On donne donc souvent l'ordre de l'algorithme, ici c'est $n^2$.
Si on a calculé que tel algorithme, pour un tableau de taille $n$, doit exécuter $C(n) = 3n^2 + 17n + 32$ instructions élémentaires, alors on dit que cet algorithme est d'ordre $n^2$.
Nous allons étudier deux algorithmes de tri. Ils ne sont pas les plus efficaces mais ils ont l'avantage d'être facile à comprendre car assez naturels.