عاجل من فضلكم و جازاكم الله خير
Soit l'algorithme de tri suivant avec un compteur inséré pour compter le nombre de comparaisons de la clé:
Fonction SortA nalysis (A [O .. n -1]: Typeqq) :Typeqq //Entrée : un tableau A[O.. n -1] de n éléments friable
//Sortie Le nombre total de comparaisons de la clé effectuées Début
cairn! EO
Pour I De I A n - I Faire
Début
y (—A[i]
JE i-1
Tantque (j>= 0) ET (AU] > y) Faire
Debut
('ount E count + I
Afl+ 1] EA[iJ
JE»
AU--1] Ev
Fin
Fin
SortAnalysis E count
Fin
1. Est ce que le compteur de comparaisons est inséré dans l'endroit juste ? Sinon proposer l'endroit approprié.
Exercice 25:
1. Elaborer et exécuter un programme pour l'algorithme de l'exercice précédent, avec l'insertion d'un compteur (des compteurs) dans l'endroit (les endroits) approprié(s) pour le calcul du nombre de comparaisons de la clé, ceci sur 20 tableaux aléatoires de tailles 1000, 1500, 2000, 2500,..., 9000,9500.
2.Analyser les données résultats obtenues pour former une hypothèse concernant l'efficacité de l'algorithme dans le cas moyen.
3.Estimer le nombre de comparaisons de la clé effectuées pour un tableau de taille 10.000, généré aléatoirement, et trié par le même algorithme.
Reprendre les questions 1,2,3 en mesurant le temps d'exécution du programme en millisecondes.