Tri

Qu'est-ce qu'un tri? On suppose qu'on se donne un suite de $n$ nombres entiers, et on veut les ranger en ordre croissant (ou décroissant) au sens large. Ainsi, pour $n=7$, la suite $(5,2,3,0,6,1,1)$ devra devenir $(0,1,1,2,3,5,6)$.

Dans tout ce qui suit, on suppose que l'on trie des nombres entiers et que ceux-ci se trouvent dans un tableau $tab$.

Sélection

L'algorithme de tri le plus simple est le tri par sélection. Il consiste à trouver l'emplacement de l'élément le plus petit du tableau, c'est-à-dire l'entier $m$ tel que $tab(i) \geqslant tab(m)$ pour tout $i$. Une fois cet emplacement trouvé, on échange les éléments $tab(1)$ et $tab(m)$. Puis on recommence ces opérations sur la suite $(tab(2),tab(3),\dots,tab(n))$, ainsi on recherche le plus petit élément de cette nouvelle suite et on l'échange avec $tab(2)$. Et ainsi de suite ...jusqu'au moment où on n'a plus qu'une suite composée d'un seul élément $(tab(n))$.

Un exemple numérique pour le tri par sélection est donné ci-dessous dans la figure 1.

Tableau: Exemple de par tri sélection.

i=1	2	1	5	0	9	4
i=2	0	1	5	2	9	4
i=3	0	1	5	2	9	4
i=4	0	1	2	5	9	4
i=5	0	1	2	4	9	5
i=6	0	1	2	4	5	9

Exercice 26   Écrire un algorithme triant un tableau par sélection Voir réponse 26.

Évaluez la complexité de cet algorithme. Voir réponse 26.

Traduisez cet algorithme en langage C. Voir réponse 26.

bulle

Une variante du tri par sélection est le tri bulle. Son principe est de parcourir la suite $(tab(1),tab(2),tab(3),\discretionary{}{}{}\dots,tab(n))$ en intervertissant toute paire d'éléments consécutifs $(tab(i),tab(i+1))$ non ordonnés. Ainsi aprés un parcours, l'élément maximum se retrouve en $tab(n)$. On recommence alors avec le préfixe $(tab(1),tab(2),tab(3),\discretionary{}{}{}\dots,tab(n-1))$, puis $(tab(1),tab(2),tab(3),\dots,\discretionary{}{}{}tab(n-2))$ ...

Le nom de tri bulle vient donc de ce que les plus grands nombres se déplacent vers la droite en poussant des bulles successives de la gauche vers la droite.La fonction correspondante utilise un indice i qui marque la fin du préfixe à trier, et l'indice j qui permet de déplacer la bulle qui monte vers la borne i.

L'exemple numérique précédent (Figure 1) est donné avec le tri bulle ci-dessous dans la figure 2.

Tableau 2: Exemple de tri bulle.

i=1	2	1	5	0	9	4
i=2	1	2	0	5	4	9
i=3	1	0	2	4	5	9
i=4	0	1	2	4	5	9
i=5	0	1	2	4	5	9

Exercice 27   Écrire un algorithme triant un tableau par sélection Voir réponse 27.

Évaluez la complexité de cet algorithme. Voir réponse 27.

Traduisez cet algorithme en langage C. Voir réponse 27.

fusion

Le tri fusion se base sur le fait qu'il est aisé de fusionner deux listes triées $l_1$ et $l_2$ en une liste triée $l$, et ce en temps $\ensuremath{\mathcal{O}}\xspace (\vert l_1\vert+\vert l_2\vert)$ (vu en TD et en section 7.2.2). Le tri se fait ensuite en divisant pour règner:

On obtient donc la récurrence $C(n) \leqslant \alpha.n + 2.C(n/2)$, qui se résout en utilisant le même type de technique qu'en section 4.2.2.

$$\begin{split}C(n) &\leqslant \alpha n + 2C(n/2) \\ &\leqslan... ...+ \ldots + \alpha n}_{i\text{ fois}} + 2^i C(n/2^i) \end{split}$$

Or, comme $C(1)=0$, dès que $n/2^i$ est inférieur à $1$, on a $C(n) = \alpha.i.n$. Or $\frac{n}{2^i}\leqslant 1$ ssi $\log n \leqslant \log 2^i = i \log 2$. Donc on a $C(n) = \alpha.(\frac{\log n}{\log 2}+1).n = \ensuremath{\mathcal{O}}\xspace (n\log n)$, ce qui est bien mieux que les autres tris précédemment étudiés.