informatique (tronc commun des prépas scientifiques) · Chapitre 9 · Exercice de TD

Le pire cas du tri rapide, construit de ses mains

Les tris · niveau 2

Énoncé

Démontrer que le tri rapide avec pivot t[0] présente une complexité quadratique de $\frac{n ( n - 1 )}{2}$ comparaisons sur un tableau déjà trié.

Sur un tableau $[1, 2, \dots, n]$ :

Le pivot choisi est $1$ .
La partition crée petits = [] et grands = [2, 3, ..., n], ce qui demande $n - 1$ comparaisons.
L'appel récursif sur grands (taille $n - 1$ ) choisit le pivot $2$ et demande $n - 2$ comparaisons. En itérant, la somme des comparaisons vaut : $(n - 1) + (n - 2) + \dots + 1 = \frac{n ( n - 1 )}{2} = O (n^{2})$ Le tri rapide naïf s'effondre donc sur les tableaux triés ou inversés.