Pire cas du tri rapide — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 14)

Pire cas du tri rapide

Les tris · niveau 2

Énoncé

On remplace le pivot aléatoire du tri rapide par la dernière case de la zone. Mesurer le temps de calcul sur des tableaux déjà triés de tailles $10000$ , $20000$ et $40000$ . Que constate-t-on ? Que se passe-t-il pour $n = 100000$ ? Expliquer.

Corrigé


14.5 trie n=10000 : 8,3 ms
14.5 trie n=20000 : 33,0 ms
14.5 trie n=40000 : 131,4 ms
14.5 n=100000 : StackOverflowError

Quand $n$ double, le temps est multiplié par $4$ : le temps de calcul est quadratique. Sur un tableau trié, le pivot (la dernière case) est le maximum de la zone : la segmentation de $T [g : d]$ fait $d - g - 1$ comparaisons et laisse une zone de $d - g - 1$ cases à gauche et une zone vide à droite. Le temps vérifie $T (n) = T (n - 1) + α n$ , soit $Θ (n^{2})$ (exercice 13.3).


nom : T
cases : 8
colorier : 7
pointeurs : g=0 d=8
zone : 0..6 d - g - 1 cases
legende : tableau trié : le pivot T[d-1] est le maximum, la zone droite est vide

Pour $n = 100000$ , la profondeur de récursivité atteint $n$ : la pile d'appels de Java déborde (StackOverflowError). Le pivot aléatoire rend ce comportement extrêmement improbable ; on peut aussi n'appeler récursivement que la plus petite des deux zones et traiter l'autre par une boucle, ce qui borne la profondeur par $lo g_{2} n$ .