\documentclass[10pt,aspectratio=169]{beamer}

% --- Thème ---
\usetheme[language=french]{Celestia}

% Avec [allowframebreaks] sur les frames de questions, Beamer ajoute
% par défaut « (1) », « (2) », « (3) »... sur chaque sous-slide. On
% supprime entièrement cette annotation : un template vide pour
% « frametitle continuation ». L'enseignant identifie visuellement la
% continuation par le contenu de la slide. (Les variantes [from second]
% et [roman] interagissent mal avec un titre contenant \textemdash{}
% sous Celestia : elles déclenchent une erreur « Missing $ inserted ».)
\setbeamertemplate{frametitle continuation}{}

\subject{Numérique et sciences informatiques}
\title{Tris par sélection et par insertion}
\subtitle{QCM}
\author{Première}
\date{\today}

\begin{document}

\begin{frame}
    \titlepage
\end{frame}

% Q1 - Réponse en A
\begin{frame}[fragile]{Question 1 \textemdash{} Qu'est-ce qu'un tri ?}
    Que signifie « \textbf{trier} une liste » en informatique ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Réorganiser ses éléments dans un ordre défini (par exemple croissant)}
        \item[B.] Supprimer les doublons
        \item[C.] Convertir les éléments en chaînes
        \item[D.] La couper en plusieurs morceaux
    \end{itemize}
\end{frame}

% Q2 - Réponse en C
\begin{frame}[fragile]{Question 2 \textemdash{} Tri par sélection : principe}
    Quel est le principe du \textbf{tri par sélection} ?\medskip
    \begin{itemize}
        \item[A.] Couper la liste en deux et trier chaque moitié
        \item[B.] Insérer chaque élément à sa place dans la partie déjà triée
        \item[\alert<2>{C.}] \alert<2>{Sélectionner le plus petit élément non trié et le placer en début de la partie non triée}
        \item[D.] Comparer chaque paire d'éléments adjacents
    \end{itemize}
\end{frame}

% Q3 - Réponse en A
\begin{frame}[fragile]{Question 3 \textemdash{} Tri par insertion : principe}
    Quel est le principe du \textbf{tri par insertion} ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Insérer chaque nouvel élément à la bonne place dans la partie déjà triée à sa gauche}
        \item[B.] Compter le nombre d'occurrences
        \item[C.] Sélectionner le minimum et le placer en tête
        \item[D.] Inverser l'ordre des éléments
    \end{itemize}
\end{frame}

% Q4 - Réponse en D
\begin{frame}[fragile]{Question 4 \textemdash{} Échange Python}
    Quelle est la façon la plus simple d'\textbf{échanger
deux éléments} d'une liste en Python ?\medskip
    \begin{itemize}
        \item[A.] \texttt{tmp = liste[i]; liste[i] = liste[j]; liste[j] = tmp}
        \item[B.] \texttt{liste.swap(i, j)}
        \item[C.] \texttt{liste[i] = liste[j]}
        \item[\alert<2>{D.}] \alert<2>{\texttt{liste[i], liste[j] = liste[j], liste[i]}}
    \end{itemize}
\end{frame}

% Q5 - Réponse en C
\begin{frame}[fragile]{Question 5 \textemdash{} Coût au pire cas}
    Quel est le \textbf{coût} au pire cas du tri par
sélection et du tri par insertion sur une liste
de longueur n ?\medskip
    \begin{itemize}
        \item[A.] Logarithmique
        \item[B.] Constant (indépendant de n)
        \item[\alert<2>{C.}] \alert<2>{Quadratique (proportionnel à n²)}
        \item[D.] Linéaire (proportionnel à n)
    \end{itemize}
\end{frame}

% Q6 - Réponse en D
\begin{frame}[fragile]{Question 6 \textemdash{} Tri en place}
    Que signifie « tri \textbf{en place} » ?\medskip
    \begin{itemize}
        \item[A.] Le tri se fait sur place dans le disque dur
        \item[B.] Le tri remplace les valeurs par leurs indices
        \item[C.] Le tri ne fonctionne que sur des listes courtes
        \item[\alert<2>{D.}] \alert<2>{Le tri ne crée pas de nouvelle liste : il modifie la liste d'origine}
    \end{itemize}
\end{frame}

% Q7 - Réponse en A
\begin{frame}[fragile]{Question 7 \textemdash{} Tri par insertion : meilleur cas}
    Quel est le meilleur cas pour le \textbf{tri par
insertion} ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Liste déjà triée}
        \item[B.] Liste de longueur impaire
        \item[C.] Liste de doublons identiques
        \item[D.] Liste triée à l'envers
    \end{itemize}
\end{frame}

% Q8 - Réponse en B
\begin{frame}[fragile]{Question 8 \textemdash{} Trace tri par sélection}
    On trie \texttt{[4, 1, 3]} par tri par sélection
(croissant). Que vaut la liste après la
\textbf{première} passe ?\medskip
    \begin{itemize}
        \item[A.] \texttt{[1, 3, 4]}
        \item[\alert<2>{B.}] \alert<2>{\texttt{[1, 4, 3]}}
        \item[C.] \texttt{[3, 4, 1]}
        \item[D.] \texttt{[4, 1, 3]}
    \end{itemize}
\end{frame}

% Q9 - Réponse en A
\begin{frame}[fragile]{Question 9 \textemdash{} Tri par insertion : pire cas}
    Quel est le \textbf{pire cas} pour le tri par
insertion ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Liste triée à l'envers (décroissant)}
        \item[B.] Liste déjà triée
        \item[C.] Liste avec doublons
        \item[D.] Liste vide
    \end{itemize}
\end{frame}

% Q10 - Réponse en A
\begin{frame}[fragile]{Question 10 \textemdash{} Stabilité d'un tri}
    Un tri est dit \textbf{stable} si :\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Il préserve l'ordre relatif des éléments égaux}
        \item[B.] Il fonctionne en temps constant
        \item[C.] Il ne se trompe jamais
        \item[D.] Il ne plante jamais
    \end{itemize}
\end{frame}

% Q11 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 11 \textemdash{} Code tri par sélection}
    Quel code implémente correctement le \textbf{tri par
sélection} croissant ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
liste.sort()
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
for x in liste:
    x = min(liste)
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
for i in range(len(liste)):
    j_min = i
    for j in range(i + 1, len(liste)):
        if liste[j] < liste[j_min]:
            j_min = j
    liste[i], liste[j_min] = liste[j_min], liste[i]
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
for i in range(len(liste) - 1):
    if liste[i] > liste[i + 1]:
        liste[i], liste[i + 1] = liste[i + 1], liste[i]
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q11 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 11 \textemdash{} Code tri par sélection}
    Quel code implémente correctement le \textbf{tri par
sélection} croissant ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
liste.sort()
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
for x in liste:
    x = min(liste)
\end{lstlisting}

        \item[\alert{C.}]~\\
\begin{lstlisting}
for i in range(len(liste)):
    j_min = i
    for j in range(i + 1, len(liste)):
        if liste[j] < liste[j_min]:
            j_min = j
    liste[i], liste[j_min] = liste[j_min], liste[i]
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
for i in range(len(liste) - 1):
    if liste[i] > liste[i + 1]:
        liste[i], liste[i + 1] = liste[i + 1], liste[i]
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q12 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 12 \textemdash{} Code tri par insertion}
    Quel code implémente correctement le \textbf{tri par
insertion} croissant ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
for i in range(len(liste)):
    liste.append(min(liste))
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
for i in range(1, len(liste)):
    j = i
    while j > 0 and liste[j - 1] > liste[j]:
        liste[j - 1], liste[j] = liste[j], liste[j - 1]
        j -= 1
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
while liste != sorted(liste):
    pass
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
for i in range(len(liste)):
    for j in range(i):
        if liste[i] < liste[j]:
            liste[i] = liste[j]
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q12 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 12 \textemdash{} Code tri par insertion}
    Quel code implémente correctement le \textbf{tri par
insertion} croissant ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
for i in range(len(liste)):
    liste.append(min(liste))
\end{lstlisting}

        \item[\alert{B.}]~\\
\begin{lstlisting}
for i in range(1, len(liste)):
    j = i
    while j > 0 and liste[j - 1] > liste[j]:
        liste[j - 1], liste[j] = liste[j], liste[j - 1]
        j -= 1
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
while liste != sorted(liste):
    pass
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
for i in range(len(liste)):
    for j in range(i):
        if liste[i] < liste[j]:
            liste[i] = liste[j]
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q13 - Réponse en D
\begin{frame}[fragile]{Question 13 \textemdash{} Liste presque triée}
    Entre le \textbf{tri par insertion} et le \textbf{tri par
sélection}, lequel est le plus rapide sur une
liste « presque triée » (peu d'éléments mal
placés) ?\medskip
    \begin{itemize}
        \item[A.] Les deux sont équivalents
        \item[B.] Aucun des deux ne tire profit de la situation, ils sont aussi lents l'un que l'autre
        \item[C.] Tri par sélection
        \item[\alert<2>{D.}] \alert<2>{Tri par insertion}
    \end{itemize}
\end{frame}

% Q14 - Réponse en C
\begin{frame}[fragile]{Question 14 \textemdash{} Invariant tri par sélection}
    Quel \textbf{invariant} vérifie le tri par sélection
après l'itération \texttt{i} de la boucle externe ?\medskip
    \begin{itemize}
        \item[A.] La liste est inchangée
        \item[B.] Les \texttt{i} premiers éléments sont les plus grands
        \item[\alert<2>{C.}] \alert<2>{Les \texttt{i} premiers éléments sont triés et plus petits ou égaux à tous les autres}
        \item[D.] La liste est entièrement triée
    \end{itemize}
\end{frame}

% Q15 - Réponse en A
\begin{frame}[fragile]{Question 15 \textemdash{} Terminaison}
    Pourquoi les tris par sélection et par
insertion \textbf{terminent} toujours ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Parce que chaque boucle a un variant strict : le \texttt{for} parcourt un \texttt{range} fini, et le \texttt{while} interne du tri par insertion fait décroître strictement \texttt{j}, minoré par $0$}
        \item[B.] Parce que Python limite les boucles à 1000 itérations
        \item[C.] Parce qu'aucun tri n'a de boucle while
        \item[D.] Parce que les listes Python sont finies
    \end{itemize}
\end{frame}

% Q16 - Réponse en B
\begin{frame}[fragile]{Question 16 \textemdash{} Trace tri par insertion}
    On trie \texttt{[3, 1, 4, 1, 5]} par tri par
insertion croissant. Quel est l'état de la
liste \textbf{après l'itération i = 3} ?\medskip
    \begin{itemize}
        \item[A.] \texttt{[3, 1, 4, 1, 5]}
        \item[\alert<2>{B.}] \alert<2>{\texttt{[1, 1, 3, 4, 5]}}
        \item[C.] \texttt{[1, 3, 4, 1, 5]}
        \item[D.] \texttt{[1, 3, 1, 4, 5]}
    \end{itemize}
\end{frame}

% Q17 - Réponse en B
\begin{frame}[fragile]{Question 17 \textemdash{} Nombre d'échanges sélection}
    Combien d'échanges (au maximum) effectue le
tri par sélection sur une liste de longueur n ?\medskip
    \begin{itemize}
        \item[A.] \texttt{log n}
        \item[\alert<2>{B.}] \alert<2>{\texttt{n - 1}}
        \item[C.] \texttt{n × (n - 1) / 2}
        \item[D.] \texttt{n}
    \end{itemize}
\end{frame}

% Q18 - Réponse en D
\begin{frame}[fragile]{Question 18 \textemdash{} Sélection vs insertion}
    Sur une liste \textbf{déjà triée} de 1000 éléments,
quel tri est le plus rapide ?\medskip
    \begin{itemize}
        \item[A.] Aucun ne fonctionne
        \item[B.] Le tri par sélection
        \item[C.] Les deux sont équivalents
        \item[\alert<2>{D.}] \alert<2>{Le tri par insertion}
    \end{itemize}
\end{frame}

% Q19 - Réponse en C
\begin{frame}[fragile]{Question 19 \textemdash{} Trier puis chercher}
    On veut faire \textbf{plusieurs recherches}
d'éléments dans une liste. Pourquoi peut-il
être intéressant de la \textbf{trier} d'abord ?\medskip
    \begin{itemize}
        \item[A.] Pour économiser de la mémoire
        \item[B.] Aucun intérêt
        \item[\alert<2>{C.}] \alert<2>{Parce qu'on pourra ensuite utiliser la recherche dichotomique (coût logarithmique) plutôt que linéaire}
        \item[D.] Pour éviter les bugs
    \end{itemize}
\end{frame}

% Q20 - Réponse en D
\begin{frame}[fragile]{Question 20 \textemdash{} Tris natifs Python}
    Pourquoi \texttt{liste.sort()} n'utilise-t-il \textbf{pas}
le tri par sélection ou par insertion ?\medskip
    \begin{itemize}
        \item[A.] Parce que Python ne sait pas les implémenter
        \item[B.] Parce que les listes Python ne sont pas modifiables
        \item[C.] Parce qu'aucun tri n'est implémenté
        \item[\alert<2>{D.}] \alert<2>{Parce que Python utilise un tri plus efficace (Timsort, en n log n) sur les grandes listes}
    \end{itemize}
\end{frame}

% Q21 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 21 \textemdash{} Bug d'indice}
    \begin{lstlisting}
for i in range(1, len(liste) + 1):
    j = i
    while j > 0 and liste[j - 1] > liste[j]:
        liste[j - 1], liste[j] = liste[j], liste[j - 1]
        j -= 1
\end{lstlisting}
Pourquoi ce code (tentative de tri par
insertion) est-il \textbf{bogué} ?\medskip
    \begin{itemize}
        \item[A.] La complexité est trop élevée
        \item[B.] La borne externe est \texttt{len(liste) + 1} au lieu de \texttt{len(liste)} ; à la dernière itération, on accède à \texttt{liste[len(liste)]} qui n'existe pas → \texttt{IndexError}
        \item[C.] La fonction \texttt{range} n'accepte pas deux paramètres
        \item[D.] Aucun bug
    \end{itemize}
\end{frame}

% Q21 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 21 \textemdash{} Bug d'indice}
    \begin{lstlisting}
for i in range(1, len(liste) + 1):
    j = i
    while j > 0 and liste[j - 1] > liste[j]:
        liste[j - 1], liste[j] = liste[j], liste[j - 1]
        j -= 1
\end{lstlisting}
Pourquoi ce code (tentative de tri par
insertion) est-il \textbf{bogué} ?\medskip
    \begin{itemize}
        \item[A.] La complexité est trop élevée
        \item[\alert{B.}] \alert{La borne externe est \texttt{len(liste) + 1} au lieu de \texttt{len(liste)} ; à la dernière itération, on accède à \texttt{liste[len(liste)]} qui n'existe pas → \texttt{IndexError}}
        \item[C.] La fonction \texttt{range} n'accepte pas deux paramètres
        \item[D.] Aucun bug
    \end{itemize}
\end{frame}

% Q22 - Réponse en A
\begin{frame}[fragile]{Question 22 \textemdash{} Nombre de comparaisons}
    Combien de comparaisons effectue le tri par
\textbf{sélection} sur une liste de longueur n,
quel que soit l'ordre initial ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Environ n²/2 comparaisons (toujours)}
        \item[B.] Environ log n
        \item[C.] Environ n comparaisons
        \item[D.] Aucune si la liste est déjà triée
    \end{itemize}
\end{frame}

% Q23 - Réponse en B
\begin{frame}[fragile]{Question 23 \textemdash{} Stabilité de la sélection}
    Pourquoi le tri par \textbf{sélection} n'est-il en
général \textbf{pas stable} ?\medskip
    \begin{itemize}
        \item[A.] Parce qu'il modifie la liste en place
        \item[\alert<2>{B.}] \alert<2>{Parce que l'échange entre \texttt{liste[i]} et \texttt{liste[j\_min]} peut faire passer un élément avant un autre élément égal}
        \item[C.] Parce qu'il est lent
        \item[D.] Parce qu'il utilise des doubles boucles
    \end{itemize}
\end{frame}

% Q24 - Réponse en C
\begin{frame}[fragile]{Question 24 \textemdash{} Choisir un tri}
    Pour trier une liste de \textbf{5 éléments} dans un
microcontrôleur où l'on doit \textbf{minimiser
l'écriture en mémoire flash} (les écritures
sont lentes), quel tri choisir parmi
sélection et insertion ?\medskip
    \begin{itemize}
        \item[A.] Aucun, il faut un tri à bulles
        \item[B.] Tri par insertion
        \item[\alert<2>{C.}] \alert<2>{Tri par sélection}
        \item[D.] Aucun, on doit utiliser Timsort
    \end{itemize}
\end{frame}

% Q25 - Réponse en C
\begin{frame}[fragile]{Question 25 \textemdash{} Synthèse}
    Parmi les affirmations suivantes sur les tris
au programme (sélection, insertion), laquelle
est \textbf{fausse} ?\medskip
    \begin{itemize}
        \item[A.] Le coût au pire des deux est quadratique.
        \item[B.] Les deux tris peuvent être implémentés en place (sans liste auxiliaire).
        \item[\alert<2>{C.}] \alert<2>{Le tri par sélection est stable par défaut.}
        \item[D.] Le tri par insertion est en coût linéaire sur une liste déjà triée.
    \end{itemize}
\end{frame}

% Q26 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 26 \textemdash{} Tri par insertion par décalage}
    Une variante classique du tri par insertion ne
fait \textbf{pas} d'échanges deux à deux mais un
\textbf{décalage} suivi d'une insertion. Quel code
met cette idée en œuvre correctement ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
for i in range(1, len(liste)):
    valeur = liste[i]
    j = i
    while j > 0 and liste[j - 1] > valeur:
        liste[j] = liste[j - 1]
        j -= 1
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
for i in range(1, len(liste)):
    valeur = liste[i]
    for j in range(i, 0, -1):
        liste[j] = valeur
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
for i in range(1, len(liste)):
    valeur = liste[i]
    j = i
    while j > 0 and liste[j - 1] > valeur:
        liste[j] = liste[j - 1]
        j -= 1
    liste[j] = valeur
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
for i in range(1, len(liste)):
    j = i
    while j > 0 and liste[j - 1] > liste[j]:
        liste[j] = liste[j - 1]
        j -= 1
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q26 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 26 \textemdash{} Tri par insertion par décalage}
    Une variante classique du tri par insertion ne
fait \textbf{pas} d'échanges deux à deux mais un
\textbf{décalage} suivi d'une insertion. Quel code
met cette idée en œuvre correctement ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
for i in range(1, len(liste)):
    valeur = liste[i]
    j = i
    while j > 0 and liste[j - 1] > valeur:
        liste[j] = liste[j - 1]
        j -= 1
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
for i in range(1, len(liste)):
    valeur = liste[i]
    for j in range(i, 0, -1):
        liste[j] = valeur
\end{lstlisting}

        \item[\alert{C.}]~\\
\begin{lstlisting}
for i in range(1, len(liste)):
    valeur = liste[i]
    j = i
    while j > 0 and liste[j - 1] > valeur:
        liste[j] = liste[j - 1]
        j -= 1
    liste[j] = valeur
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
for i in range(1, len(liste)):
    j = i
    while j > 0 and liste[j - 1] > liste[j]:
        liste[j] = liste[j - 1]
        j -= 1
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q27 - Réponse en D
\begin{frame}[fragile]{Question 27 \textemdash{} Comparaisons précises sur exemple}
    Combien de comparaisons (entre éléments)
effectue le tri par \textbf{sélection} sur la liste
\texttt{[5, 3, 8, 1]} (n = 4) ?\medskip
    \begin{itemize}
        \item[A.] 4
        \item[B.] 16
        \item[C.] 3
        \item[\alert<2>{D.}] \alert<2>{6}
    \end{itemize}
\end{frame}

% Q28 - Réponse en D
\begin{frame}[fragile]{Question 28 \textemdash{} Stabilité : application pratique}
    On a une liste d'élèves représentée par des
couples \texttt{(nom, classe)}, déjà triée par nom.
On veut maintenant la trier par classe \textbf{tout
en conservant l'ordre alphabétique des noms à
l'intérieur de chaque classe}. Pourquoi
faut-il un tri stable ?\medskip
    \begin{itemize}
        \item[A.] Parce qu'un tri stable est plus rapide qu'un tri non stable
        \item[B.] Parce qu'un tri stable consomme moins de mémoire
        \item[C.] Parce que les classes sont des chaînes de caractères
        \item[\alert<2>{D.}] \alert<2>{Parce qu'un tri stable préserve l'ordre
relatif des élèves ayant la même classe ;
ainsi, à l'intérieur de chaque classe,
l'ordre alphabétique des noms (issu du
premier tri) est conservé
}
    \end{itemize}
\end{frame}

% Q29 - Réponse en A
\begin{frame}[fragile]{Question 29 \textemdash{} Trace pas-à-pas du tri par sélection}
    On trie la liste \texttt{[3, 1, 4, 2]} par tri par
sélection croissant. Quels sont les états
successifs de la liste \textbf{après chaque
itération de la boucle externe} (chaque
« passe ») ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Après passe $1$ : \texttt{[1, 3, 4, 2]}. Après
passe $2$ : \texttt{[1, 2, 4, 3]}. Après passe
$3$ : \texttt{[1, 2, 3, 4]}. La passe $4$
(sur le dernier élément seul) ne
change rien
}
        \item[B.] Après passe $1$ : \texttt{[3, 1, 4, 2]}
(inchangée). Après passe $2$ :
\texttt{[1, 3, 4, 2]}. Après passe $3$ :
\texttt{[1, 2, 4, 3]}

        \item[C.] Après passe $1$ : \texttt{[1, 3, 4, 2]}. Après
passe $2$ : \texttt{[1, 3, 2, 4]}. Après passe
$3$ : \texttt{[1, 2, 3, 4]}

        \item[D.] Après passe $1$ : \texttt{[1, 2, 3, 4]}. Les
passes suivantes ne changent rien

    \end{itemize}
\end{frame}

% Q30 - Réponse en A
\begin{frame}[fragile]{Question 30 \textemdash{} Trace pas-à-pas du tri par insertion}
    On trie la même liste \texttt{[3, 1, 4, 2]} par
tri par insertion croissant. Quels sont
les états successifs \textbf{après chaque
itération de la boucle externe} ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Après $i = 1$ (insertion du $1$) :
\texttt{[1, 3, 4, 2]}. Après $i = 2$
(insertion du $4$) : \texttt{[1, 3, 4, 2]}
(inchangée, $4$ est déjà à sa place).
Après $i = 3$ (insertion du $2$) :
\texttt{[1, 2, 3, 4]}
}
        \item[B.] Après $i = 1$ : \texttt{[3, 1, 4, 2]}
(inchangée). Après $i = 2$ :
\texttt{[1, 3, 4, 2]}. Après $i = 3$ :
\texttt{[1, 2, 3, 4]}

        \item[C.] Après $i = 1$ : \texttt{[1, 3, 4, 2]}. Après
$i = 2$ : \texttt{[1, 2, 3, 4]}. Après
$i = 3$ : \texttt{[1, 2, 3, 4]}

        \item[D.] Identique au tri par sélection :
\texttt{[1, 3, 4, 2]} puis \texttt{[1, 2, 4, 3]}
puis \texttt{[1, 2, 3, 4]}

    \end{itemize}
\end{frame}

% Q31 - Réponse en D
\begin{frame}[fragile]{Question 31 \textemdash{} Trier en ordre décroissant}
    Comment adapter un tri par insertion
croissant pour qu'il trie en ordre
\textbf{décroissant} ?\medskip
    \begin{itemize}
        \item[A.] Appliquer le tri croissant puis
inverser la liste finale avec
\texttt{liste.reverse()}

        \item[B.] Trier la liste à l'envers d'abord, puis
appliquer le tri croissant

        \item[C.] Multiplier toutes les valeurs par
$-1$, trier, puis multiplier à
nouveau par $-1$

        \item[\alert<2>{D.}] \alert<2>{Inverser le sens de la comparaison dans
la boucle interne : utiliser
\texttt{liste[j - 1] < liste[j]} au lieu de
\texttt{liste[j - 1] > liste[j]}
}
    \end{itemize}
\end{frame}

% Q32 - Réponse en A
\begin{frame}[fragile]{Question 32 \textemdash{} Comportement avec doublons}
    Que se passe-t-il quand on trie une liste
contenant des \textbf{doublons}, par exemple
\texttt{[3, 1, 3, 2, 3]} ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Le tri fonctionne normalement et
renvoie \texttt{[1, 2, 3, 3, 3]}. Si le tri
est stable, l'ordre relatif des
trois \texttt{3} (qui étaient en positions
$0$, $2$, $4$ d'origine) est préservé
}
        \item[B.] Les doublons sont automatiquement
supprimés

        \item[C.] L'algorithme tombe en boucle infinie

        \item[D.] Le tri lève une exception

    \end{itemize}
\end{frame}

\begin{frame}[standout]{}
    Fin de l'évaluation
\end{frame}

\end{document}
