Tri des programmes sur ordinateur

Projet Tri population en France

Complexité du tri :  Pour les deux tris auxquels on a affaire, nous allons calculer la complexité. Si on veut calculer le temps que met un algorithme lors de son exécution du début à la fin, il faut compter le nombre d’opérations effectuées, dont on connait de temps d’exécution, plus précisément on prend en compte les opérations fondamentales.

Il faut appliquer ce que nous venons de dire numériquement. Le tri par sélection, effectue (n*(n-1))/2 comparaisons, avec n le nombre d’éléments d’une liste, en comptant les opérations fondamentales de notre algorithme. On en déduit le calcul (n² -n)/2 (simple distributivité) et que sa complexité est O(n 2 ), quadratique. Pour le tri par insertion il y a plusieurs cas possibles, elle peut être quadratique dans certains cas, de l’ordre de n2/4 ou encore il peut y avoir n-1 dans le meilleur des cas. La complexité (dans le pire des cas)  est quadratique, on retrouve le calcul (n² -n)/2.

Comptage d’opérations fondamentales : Nous avons précédemment dit que les opérations fondamentales prises en compte sont les comparaisons. Dans nos deux algorithmes « tri_par_selection » et « tri_par_insertion »  nous avons ajouté une variable compteur :    

[pic 1]

Mesure du temps :

Pour mesurer le temps, on importe le module « time » et on applique la fonction.

[pic 2]

Bilan : On prend le nombre d’éléments par lignes, ce qui correspond au nombres d’éléments à trier. Pour l’Ain, 407. Pour les 5 départements, 1849. Pour les 10 départements, 3604 et pour la population de la France, 35382.

On peut alors vérifier les calculs de complexité en remplaçant n par le nombre d’éléments à trier (comparer).

...