[TP.05] Tri par sélection

Considérons l'algorithme de tri par sélection suivant :

Paste this command into your terminal:

The password to connect is

Please answer to all the questions. Internal error {} 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.

[1, 0]

[4, 3, 2, 1, 0]

[0,1,2,3,4]

[4,0,1,2,3]

[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.

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.

$\Theta(n^2)$

$\Omega(n)$

$\Omega(n^2)$

$O(n^2)$

$O(n)$

$\Theta(n)$

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.

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.

$\Omega(n^2)$

$\Theta(n)$

$O(n)$

$\Omega(n)$

$\Theta(n^2)$

$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)$

$\Theta(n^2)$

$O(n)$

$\Omega(n^2)$

$\Omega(n)$

$O(n^2)$

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 adaptatif

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

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

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

Information

Sign in

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

Sign in