- 6 heures
- Facile
Ce cours est visible gratuitement en ligne.
course.header.alt.is_video
course.header.alt.is_certifying
J'ai tout compris !Mis à jour le 11/01/2024
Appliquer les concepts avancés de l’algorithmique
Compétences évaluées
- Appliquer les concepts avancés de l’algorithmique
Description
Au fil des questions de ce quiz, vous allez aider un libraire à faire un choix pour trouver une méthode pour trier les livres qu’il vend dans son magasin.
Chaque livre est numéroté de 1 à 1 000, ce chiffre permet de les classer facilement dans les rayons.
Question 1
Le libraire a choisi d’utiliser un tri par sélection pour trier ses livres à l’aide de leur numéro, du plus petit au plus grand.
Voici les étapes du tri par sélection :
- Rechercher le plus petit élément du tableau, et l'échanger avec l'élément d'indice 0 ;
- Rechercher le second plus petit élément du tableau, et l'échanger avec l'élément d'indice 1 ;
- Continuer de cette façon jusqu'à ce que le tableau soit entièrement trié.
Quel pseudo-code correspond à la description du tri par sélection ?
Algorithme Tri(tableau) N ← Taille du tableau Pour i allant de 0 jusqu’à N - 2 : min ← i Pour j allant de i + 1 jusqu’à N - 1 : Si tableau[j] < tableau[min] : min ← j Fin Si Fin Pour Si min != i : echanger(tableau[i], tableau[min]) Fin Si Fin Pour Fin
Algorithme Tri(tableau) N ← Taille du tableau Pour i allant de 1 jusqu’à N - 1 : x ← tableau[i] j ← i Tant que j > 0 ET tableau[j-1] > x : tableau[j-1] ← tableau[j] j ← j - 1 Fin Tant que tableau[j] ← x Fin Pour Fin
Algorithme Tri(tableau) N ← Taille du tableau Pour i allant de N - 1 jusqu’à 1 : Pour j allant de 0 jusqu’à i - 1 Si tableau[j+1] < tableau[j] : echanger(tableau[j+1], tableau[j]) Fin Si Fin Pour Fin Pour Fin
Question 2
Considérons que le libraire a 5 livres placés dans cet ordre : [9,6,2,5,1].
Quelles étapes correspondent à un algorithme de tri par sélection sur le tableau ci-dessus, dans l’ordre croissant ?
- Point de départ : [9, 6, 2, 5, 1]
- Résultat après la première itération : [1, 9, 6, 2, 5]
- Résultat après la seconde itération : [1, 2, 5, 9, 6]
- Résultat après la troisième itération : [1, 2, 5, 9, 6]
- État final : [1, 2, 5, 6, 9]
- Point de départ : [9, 6, 2, 5, 1]
- Résultat après la première itération : [1, 6, 2, 5, 9]
- Résultat après la seconde itération : [1, 2, 6, 5, 9]
- Résultat après la troisième itération : [1, 2, 5, 6, 9]
- État final : [1, 2, 5, 6, 9]
- Point de départ : [9, 6, 2, 5, 1]
- Résultat après la première itération : [9, 6, 5, 2, 1]
- Résultat après la seconde itération : [9, 6, 5, 2, 1]
- Résultat après la troisième itération : [1, 2, 5, 6, 9]
- État final : [1, 2, 5, 6, 9]
Question 3
Le libraire a finalement changé d’avis, il souhaite trier ce tableau dans l'ordre décroissant.
Quelles étapes correspondent à un algorithme de tri par sélection dans l’ordre décroissant ?
- Point de départ : [9, 6, 2, 5, 1]
- Résultat après la première itération : [9, 6, 2, 5, 1]
- Résultat après la seconde itération : [9, 6, 5, 1, 2]
- Résultat après la troisième itération : [9, 6, 5, 1, 2]
- État final : [9, 6, 5, 2, 1]
- Point de départ : [9, 6, 2, 5, 1]
- Résultat après la première itération : [9, 6, 2, 1, 5]
- Résultat après la seconde itération : [9, 6, 5, 1, 2]
- Résultat après la troisième itération : [9, 6, 5, 1, 2]
- État final : [9, 6, 5, 2, 1]
- Point de départ : [9, 6, 2, 5, 1]
- Résultat après la première itération : [9, 6, 2, 5, 1]
- Résultat après la seconde itération : [9, 6, 2, 5, 1]
- Résultat après la troisième itération : [9, 6, 5, 2, 1]
- État final : [9, 6, 5, 2, 1]
- Formations jusqu’à 100 % financées
- Date de début flexible
- Projets professionnalisants
- Mentorat individuel