Sélectionnez, parmi les propositions suivantes, celle(s) qui corresponde(nt) à un pire cas pour l'algorithme de tri étudié dans cette tâche.

Supposons le tableau suivant:

[65, 97, 43, 12, 29, 14, 99]

Déterminez le nombre de comparaisons effectuées par l'algorithme de tri étudié dans cette tâche.

Nous nous concentrons ici sur les comparaisons entre éléments du tableau ou entre un élément du tableau et une valeur mémorisée (par exemple dans key). Nous ne comptons pas les comparaisons sur les valeurs des variables de boucle (comparaison explicite sur $j$ dans la boucle while ou implicite sur $i$ dans la boucle for ).

Ne pas oublier la comparaison $A[j] > key$ lorsque c'est cette comparaison (évaluée à False) qui permet de sortir de la boucle while.

Combien de comparaisons sont effectuées par l'algorithme de tri étudié dans cette tâche? Déterminez la borne la plus simple et la plus stricte possible.

Supposons le tableau suivant:

[65, 97, 43, 12, 29, 14, 99]

Déterminez le nombre d'échanges effectuées par l'algorithme de tri étudié dans cette tâche.

Pour cet algorithme, un "échange" est une assignation d'une valeur à un élément du tableau, plutôt qu'un réel échange entre 2 éléments du tableau. On parle donc parfois de "demi-échange".

Ne pas oublier l'assignation effectuée lorsque l'on est sorti de la boucle while.

Combien d'échanges sont effectuées par l'algorithme de tri étudié dans cette tâche ? Déterminez la borne la plus simple et la plus stricte possible.

Quelle est la complexité temporelle globale de l'algorithme de tri étudié dans cette tâche ? Déterminez la borne la plus simple et la plus stricte possible.

Sélectionnez, parmi les propositions suivantes, celle(s) qui est (sont) correcte(s).