Il est possible de trier les données à partir d’un seul tableau.
On dit alors qu’on effectue un tri sur place.
Il existe plusieurs algorithmes de tri en place qui ont des efficacités différentes.
Nous allons en étudier plusieurs.
a) Tri par insertion
Le tri par insertion est un algorithme de tri classique dont le principe est très simple. C'est le tri que la plupart des personnes utilisent naturellement pour trier des cartes : prendre les cartes mélangées une à une sur la table, et former une main en insérant chaque carte à sa place.
Voici un algorithme de tri par insertion en pseudo-code :
$\color{blue}{\text{procédure tri_insertion (tableau T, entier n)}\\
\qquad \text{pour i de 1 à n-1}\\
\qquad \quad \rm x \leftarrow T[i]\\
\qquad \quad \rm j \leftarrow i\\
\qquad \quad \text{tant que j > 0 et T[j - 1] > x}\\
\qquad \qquad \rm T[j] \leftarrow T[j - 1]\\
\qquad \qquad \rm j \leftarrow j - 1\\
\qquad \quad\text{fin tant que}\\
\qquad \quad \rm T[j]\leftarrow x\\
\qquad \text{fin pour}\\
\quad\text{fin procédure}}$
Les éléments du tableau T sont numérotés de 0 à n – 1.
b) Complexité du tri par insertion
On montre (avec des maths !!) qu’en moyenne le nombre de boucles effectuées pour un tableau de taille n est $\displaystyle {\rm \frac{n^2}{4}}$
c) Des algorithmes de tri plus efficaces
Il existe d'autres algorithmes de tri :
- Tri à bulles (bubble sort)
- Tri par sélection (selection sort)
- Tri fusion (merge sort)
- Tri rapide (quick sort)
d) Complexité des algorithmes de tri
On trouve la complexité des algorithmes de tri dans le tableau suivant :
\[\begin{array}{|l|l|}
\hline
& \color{blue}{\text{Complexité en moyenne}}\\
\color{blue}{\text{Méthode de tri}}& \color{blue}{\text{pour un tableau de taille}}\\
& \color{blue}{\rm N.}\\
\hline
\text{Tri par insertion} & \rm N^2\\
\hline
\text{Tri par sélection} & \rm N^2\\
\hline
\text{Tri à bulles} & \rm N^2\\
\hline
\text{Tri fusion} & \rm N \times log(N)\\
\hline
\text{Tri rapide} & \rm N \times log(N)\\
\hline
\end{array}\]
Les algorithmes les plus efficaces en moyenne sont ceux de tri par fusion ou de tri rapide.