Tâche 1

Question 1: test dans la boucle interne

Complétez la ligne 5 du pseudo-code avec l'instruction correcte.

if \(j < pos\) then \(pos \leftarrow j\);

if \(A[j] == A[pos]\) then \(pos \leftarrow j\);

if \(A[j] < A[pos]\) then \(pos \leftarrow j\);

if \(j > pos\) then \(pos \leftarrow j\);

if \(A[j] > i\) then \(pos \leftarrow j\);

if \(A[pos] > A[n-1]\) then \(pos \leftarrow j\);

if \(A[j] \le A[pos]\) then \(pos \leftarrow j\);

if \(j > A[pos]\) then \(pos \leftarrow j\);

if \(j < A[pos]\) then \(pos \leftarrow j\);

if \(A[j] > A[pos]\) then \(pos \leftarrow j\);

if \(j \neq pos\) then \(pos \leftarrow j\);

Question 2: test dans la boucle externe

Complétez la ligne 6 du pseudo-code avec l'instruction correcte.

if \(A[i] > A[pos]\) then swap \(\!(A[i], A[pos])\)

if \(i < j\) then swap \(\!(A[i], A[pos])\)

if \(pos \neq i\) then swap \(\!(A[i], A[pos])\)

if \(A[i] < A[pos]\) then swap \(\!(A[i], A[pos])\)

if \(pos > j\) then swap \(\!(A[i], A[pos])\)

if \(pos < i\) then swap \(\!(A[i], A[pos])\)

if \(A[i] == A[pos]\) then swap \(\!(A[i], A[pos])\)

if \(pos == j\) then swap \(\!(A[i], A[pos])\)

if \(A[i] < A[j]\) then swap \(\!(A[i], A[pos])\)

if \(pos \neq j\) then swap \(\!(A[i], A[pos])\)

if \(pos == i\) then swap \(\!(A[i], A[pos])\)

Question 3: rôle de la variable 'pos'

Lors de l'exécution de la ligne 6, la variable \(pos\) ...

la variable \(pos\) mémorise le nombre d'échange(s) (= swap) effectué(s)

la variable \(pos\) mémorise \(n-1\)

la variable \(pos\) mémorise la valeur maximale entre \(i\) et \(j\)

la variable \(pos\) mémorise l'indice de la valeur maximale dans le (sous-)tableau \(A[0 \dots i]\)

la variable \(pos\) mémorise \(i\)

la variable \(pos\) mémorise la valeur maximale dans le tableau \(A\)

la variable \(pos\) mémorise la valeur maximale dans le (sous-)tableau \(A[i \dots n-1]\)

la variable \(pos\) mémorise l'indice de la valeur minimale dans le (sous-)tableau \(A[0 \dots i]\)

la variable \(pos\) mémorise la valeur maximale entre \(A[i]\) et \(A[n-1]\)

la variable \(pos\) mémorise l'indice de la valeur minimale dans le (sous-)tableau \(A[i \dots n-1]\)

la variable \(pos\) mémorise la valeur minimale dans le (sous-)tableau \(A[i \dots n-1]\)

la variable \(pos\) mémorise la valeur minimale dans le tableau \(A\)

la variable \(pos\) mémorise l'indice de la valeur maximale dans le (sous-)tableau \(A[i \dots n-1]\)

Question 4: complexité temporelle de l'algorithme

Quelle est la complexité temporelle de l'algorithme de tri par sélection en ordre décroissant,
c'est-à-dire celle de l'algorithme décrit par le pseudo-code repris ci-dessus et correctement complété ?

On vous demande d'identifier la borne la plus appropriée.

Note : cette sous-question ne peut rapporter des points que si vos réponses aux 3 sous-questions précédentes sont correctes.

\(\Theta(n^2)\)

\(\Theta(1)\)

\(O(n \log n)\)

\(O(n)\)

\(O(n^3)\)

\(\Theta(n \log n)\)

\(O(n^2)\)

\(\Theta(\log n)\)

\(\Theta(n)\)

\(O(\log n)\)

Question 5: pire cas en nombre d'échanges (= swap) effectués

Sélectionnez, parmi les propositions suivantes, l(es) instance(s) qui correspond(ent) à un pire cas

en terme de nombre d'échanges à effectuer par l'algorithme correctement complété.

Pour rappel, un pire ou un meilleur cas s'évalue relativement à la taille du problème posé.

Note : cette sous-question ne peut rapporter des points que si vos réponses aux 3 premières sous-questions précédentes sont correctes.

\(A = [5, 5, 5, 5, 5, 5, 5, 10]\)

\(A = [8, 7, 6, 5, 2, 0]\)

\(A = [0, 4, 6, 9, 12]\)

\(A = [0, 15, 12]\)

\(A = [-1, 19, 17, 15, 13]\)

\(A = [-2, -25, -1, -3, -4]\)

\(A = [0, 2, 5, 6, 7, 8]\)

Author(s)	Pierre Dupont
Deadline	19/08/2025 13:15:00
Submission limit	No limitation

Information

Συνδεθείτε

Question 1: test dans la boucle interne

Question 2: test dans la boucle externe

Question 3: rôle de la variable 'pos'

Question 4: complexité temporelle de l'algorithme

Question 5: pire cas en nombre d'échanges (= swap) effectués

Information

Συνδεθείτε

Tâche 1 Collapse context

Question 1: test dans la boucle interne

Question 2: test dans la boucle externe

Question 3: rôle de la variable 'pos'

Question 4: complexité temporelle de l'algorithme

Question 5: pire cas en nombre d'échanges (= swap) effectués

Tâche 1