Comparaison d'algorithmes de tri — exercice corrigé de Python (école d'ingénieur) (chapitre 6)

Comparaison d'algorithmes de tri

Complexité algorithmique

Énoncé

Comparer asymptotiquement les complexités temporelles des algorithmes de tri suivants :

Tri à bulles : $T_{bulles} (n) \approx \frac{n ( n - 1 )}{2}$

Tri par insertion (pire cas) : $T_{insertion} (n) \approx \frac{n ( n - 1 )}{2}$

Tri fusion : $T_{fusion} (n) \approx n lo g_{2} n$

Tri rapide (cas moyen) : $T_{rapide} (n) \approx n lo g_{2} n$

Pour $n = 1 0^{6}$ , estimer le nombre d'opérations et le temps d'exécution théorique de chaque algorithme sur un processeur effectuant $1 0^{9}$ opérations par seconde (1 GHz).

Corrigé

Calculons pour $n = 1 0^{6}$ :

Tri à bulles / Tri par insertion : Le nombre d'opérations est de l'ordre de : $\frac{n ^{2}}{2} = \frac{1 0 ^{12}}{2} = 5 \times 1 0^{11} op e ˊ rations$ À une vitesse de $1 0^{9}$ opérations par seconde, le temps requis est : $\frac{5 \times 1 0 ^{11}}{1 0 ^{9}} = 500 secondes \approx 8.3 minutes$

Tri fusion / Tri rapide (cas moyen) : Puisque $lo g_{2} (1 0^{6}) \approx 20$ , nous obtenons : $n lo g_{2} n \approx 1 0^{6} \times 20 = 2 \times 1 0^{7} op e ˊ rations$ Le temps d'exécution théorique vaut : $\frac{2 \times 1 0 ^{7}}{1 0 ^{9}} = 0.02 seconde = 20 millisecondes$

Nous résumons ces valeurs dans le tableau suivant :

Algorithme	Complexité	Opérations (pour $n = 1 0^{6}$ )	Temps (1 GHz)
Tri à bulles / Insertion	$Θ (n^{2})$	$5 \times 1 0^{11}$	$\approx 8.3$ min
Tri fusion / Rapide (moyen)	$Θ (n lo g n)$	$2 \times 1 0^{7}$	$\approx 20$ ms
Tri rapide (pire cas)	$Θ (n^{2})$	$1 0^{12}$	$\approx 16.7$ min

Ce tableau met en évidence l'écart colossal entre une complexité quadratique et une complexité quasi-linéaire sur de grands volumes de données.