Le tri rapide : partition et pire cas

Le tri rapide : partition et pire cas.

• Dérouler la fonction partition du cours sur tab = [7, 2, 9, 4, 3, 8, 5] avec g = 0 et d = 6 : donner l'état du tableau après chaque échange et la valeur renvoyée.
• On utilise maintenant la fonction tri_rapide du cours, dont le pivot est le premier élément. On appelle comparaison chaque test x <= pivot (on ne compte pas les tests x > pivot, qui refont les mêmes comparaisons). Combien de comparaisons fait-elle sur la liste déjà triée [1, 2, …, n] ? Vérifier pour $n=100$.