[TP.05] Tri par insertion

Considérons l'algorithme de tri par insertion suivant :

Paste this command into your terminal:

The password to connect is

Please answer to all the questions. Εσωτερικό σφάλμα {} has not a valid extension. {} is too heavy.

Question 1: Pire cas

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

[0,1,2,3,4]

[4, 3, 2, 1, 0]

[1, 0]

[0, 1, 2, 3, 4, 5, ..., 2147483647]

Question 2: Nombre de comparaisons : pratique

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.

Question 3: Nombre de comparaisons

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.

$\Omega(n^2)$

$O(n^2)$

$\Theta(n)$

$O(n)$

$\Omega(n)$

$\Theta(n^2)$

Question 4: Nombre d'échanges : pratique

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.

Question 5: Nombre d'échanges

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.

$\Theta(n)$

$\Omega(n^2)$

$\Theta(n^2)$

$\Omega(n)$

$O(n)$

$O(n^2)$

Question 6: Complexité temporelle globale

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.

$\Theta(n^2)$

$O(n)$

$\Theta(n)$

$\Omega(n^2)$

$O(n^2)$

$\Omega(n)$

Question 7: Propriétés

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

L'algorithme de tri étudié dans cette tâche est stable

L'algorithme de tri étudié dans cette tâche est effectué en place

L'algorithme de tri étudié dans cette tâche est adaptatif

Author(s)	Vincent Branders, Pierre Dupont
Deadline	19/03/2025 14:00:00
Submission limit	No limitation

Information

Συνδεθείτε

Question 1: Pire cas

Question 2: Nombre de comparaisons : pratique

Question 3: Nombre de comparaisons

Question 4: Nombre d'échanges : pratique

Question 5: Nombre d'échanges

Question 6: Complexité temporelle globale

Question 7: Propriétés

Information

Συνδεθείτε