Le pire cas du tri rapide, construit de ses mains

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 9 — Les tris

É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.

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.