\documentclass[a4paper,11pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais,bloc,completemulti]{automultiplechoice}
\usepackage[french]{babel}
\usepackage{amsmath, amssymb}

\title{Tris par sélection et par insertion}
\date{Numérique et sciences informatiques}

\begin{document}

\noindent\textbf{Tris par sélection et par insertion} \hfill \textit{Numérique et sciences informatiques}\\[0.4em]
Nom~: \dotfill\ Prénom~: \dotfill

\bigskip

\element{premieretris}{
  \begin{question}{q01}
    Que signifie « \textbf{trier} une liste » en informatique ?
    \begin{choices}
    \correctchoice{Réorganiser ses éléments dans un ordre défini (par exemple croissant)}
    \wrongchoice{Supprimer les doublons}
    \wrongchoice{Convertir les éléments en chaînes}
    \wrongchoice{La couper en plusieurs morceaux}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q02}
    Quel est le principe du \textbf{tri par sélection} ?
    \begin{choices}
    \wrongchoice{Couper la liste en deux et trier chaque moitié}
    \wrongchoice{Insérer chaque élément à sa place dans la partie déjà triée}
    \correctchoice{Sélectionner le plus petit élément non trié et le placer en début de la partie non triée}
    \wrongchoice{Comparer chaque paire d'éléments adjacents}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q03}
    Quel est le principe du \textbf{tri par insertion} ?
    \begin{choices}
    \correctchoice{Insérer chaque nouvel élément à la bonne place dans la partie déjà triée à sa gauche}
    \wrongchoice{Compter le nombre d'occurrences}
    \wrongchoice{Sélectionner le minimum et le placer en tête}
    \wrongchoice{Inverser l'ordre des éléments}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q04}
    Quelle est la façon la plus simple d'\textbf{échanger
deux éléments} d'une liste en Python ?
    \begin{choices}
    \wrongchoice{\texttt{tmp = liste[i]; liste[i] = liste[j]; liste[j] = tmp}}
    \wrongchoice{\texttt{liste.swap(i, j)}}
    \wrongchoice{\texttt{liste[i] = liste[j]}}
    \correctchoice{\texttt{liste[i], liste[j] = liste[j], liste[i]}}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q05}
    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 ?
    \begin{choices}
    \wrongchoice{Logarithmique}
    \wrongchoice{Constant (indépendant de n)}
    \correctchoice{Quadratique (proportionnel à n²)}
    \wrongchoice{Linéaire (proportionnel à n)}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q06}
    Que signifie « tri \textbf{en place} » ?
    \begin{choices}
    \wrongchoice{Le tri se fait sur place dans le disque dur}
    \wrongchoice{Le tri remplace les valeurs par leurs indices}
    \wrongchoice{Le tri ne fonctionne que sur des listes courtes}
    \correctchoice{Le tri ne crée pas de nouvelle liste : il modifie la liste d'origine}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q07}
    Quel est le meilleur cas pour le \textbf{tri par
insertion} ?
    \begin{choices}
    \correctchoice{Liste déjà triée}
    \wrongchoice{Liste de longueur impaire}
    \wrongchoice{Liste de doublons identiques}
    \wrongchoice{Liste triée à l'envers}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q08}
    On trie \texttt{[4, 1, 3]} par tri par sélection
(croissant). Que vaut la liste après la
\textbf{première} passe ?
    \begin{choices}
    \wrongchoice{\texttt{[1, 3, 4]}}
    \correctchoice{\texttt{[1, 4, 3]}}
    \wrongchoice{\texttt{[3, 4, 1]}}
    \wrongchoice{\texttt{[4, 1, 3]}}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q09}
    Quel est le \textbf{pire cas} pour le tri par
insertion ?
    \begin{choices}
    \correctchoice{Liste triée à l'envers (décroissant)}
    \wrongchoice{Liste déjà triée}
    \wrongchoice{Liste avec doublons}
    \wrongchoice{Liste vide}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q10}
    Un tri est dit \textbf{stable} si :
    \begin{choices}
    \correctchoice{Il préserve l'ordre relatif des éléments égaux}
    \wrongchoice{Il fonctionne en temps constant}
    \wrongchoice{Il ne se trompe jamais}
    \wrongchoice{Il ne plante jamais}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q11}
    Quel code implémente correctement le \textbf{tri par
sélection} croissant ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
liste.sort()
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
for x in liste:
    x = min(liste)
\end{lstlisting}
}
    \correctchoice{\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}
}
    \wrongchoice{\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{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q12}
    Quel code implémente correctement le \textbf{tri par
insertion} croissant ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
for i in range(len(liste)):
    liste.append(min(liste))
\end{lstlisting}
}
    \correctchoice{\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}
}
    \wrongchoice{\begin{lstlisting}
while liste != sorted(liste):
    pass
\end{lstlisting}
}
    \wrongchoice{\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{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q13}
    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) ?
    \begin{choices}
    \wrongchoice{Les deux sont équivalents}
    \wrongchoice{Aucun des deux ne tire profit de la situation, ils sont aussi lents l'un que l'autre}
    \wrongchoice{Tri par sélection}
    \correctchoice{Tri par insertion}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q14}
    Quel \textbf{invariant} vérifie le tri par sélection
après l'itération \texttt{i} de la boucle externe ?
    \begin{choices}
    \wrongchoice{La liste est inchangée}
    \wrongchoice{Les \texttt{i} premiers éléments sont les plus grands}
    \correctchoice{Les \texttt{i} premiers éléments sont triés et plus petits ou égaux à tous les autres}
    \wrongchoice{La liste est entièrement triée}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q15}
    Pourquoi les tris par sélection et par
insertion \textbf{terminent} toujours ?
    \begin{choices}
    \correctchoice{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$}
    \wrongchoice{Parce que Python limite les boucles à 1000 itérations}
    \wrongchoice{Parce qu'aucun tri n'a de boucle while}
    \wrongchoice{Parce que les listes Python sont finies}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q16}
    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} ?
    \begin{choices}
    \wrongchoice{\texttt{[3, 1, 4, 1, 5]}}
    \correctchoice{\texttt{[1, 1, 3, 4, 5]}}
    \wrongchoice{\texttt{[1, 3, 4, 1, 5]}}
    \wrongchoice{\texttt{[1, 3, 1, 4, 5]}}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q17}
    Combien d'échanges (au maximum) effectue le
tri par sélection sur une liste de longueur n ?
    \begin{choices}
    \wrongchoice{\texttt{log n}}
    \correctchoice{\texttt{n - 1}}
    \wrongchoice{\texttt{n × (n - 1) / 2}}
    \wrongchoice{\texttt{n}}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q18}
    Sur une liste \textbf{déjà triée} de 1000 éléments,
quel tri est le plus rapide ?
    \begin{choices}
    \wrongchoice{Aucun ne fonctionne}
    \wrongchoice{Le tri par sélection}
    \wrongchoice{Les deux sont équivalents}
    \correctchoice{Le tri par insertion}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q19}
    On veut faire \textbf{plusieurs recherches}
d'éléments dans une liste. Pourquoi peut-il
être intéressant de la \textbf{trier} d'abord ?
    \begin{choices}
    \wrongchoice{Pour économiser de la mémoire}
    \wrongchoice{Aucun intérêt}
    \correctchoice{Parce qu'on pourra ensuite utiliser la recherche dichotomique (coût logarithmique) plutôt que linéaire}
    \wrongchoice{Pour éviter les bugs}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q20}
    Pourquoi \texttt{liste.sort()} n'utilise-t-il \textbf{pas}
le tri par sélection ou par insertion ?
    \begin{choices}
    \wrongchoice{Parce que Python ne sait pas les implémenter}
    \wrongchoice{Parce que les listes Python ne sont pas modifiables}
    \wrongchoice{Parce qu'aucun tri n'est implémenté}
    \correctchoice{Parce que Python utilise un tri plus efficace (Timsort, en n log n) sur les grandes listes}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q21}
    \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é} ?
    \begin{choices}
    \wrongchoice{La complexité est trop élevée}
    \correctchoice{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}}
    \wrongchoice{La fonction \texttt{range} n'accepte pas deux paramètres}
    \wrongchoice{Aucun bug}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q22}
    Combien de comparaisons effectue le tri par
\textbf{sélection} sur une liste de longueur n,
quel que soit l'ordre initial ?
    \begin{choices}
    \correctchoice{Environ n²/2 comparaisons (toujours)}
    \wrongchoice{Environ log n}
    \wrongchoice{Environ n comparaisons}
    \wrongchoice{Aucune si la liste est déjà triée}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q23}
    Pourquoi le tri par \textbf{sélection} n'est-il en
général \textbf{pas stable} ?
    \begin{choices}
    \wrongchoice{Parce qu'il modifie la liste en place}
    \correctchoice{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}
    \wrongchoice{Parce qu'il est lent}
    \wrongchoice{Parce qu'il utilise des doubles boucles}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q24}
    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 ?
    \begin{choices}
    \wrongchoice{Aucun, il faut un tri à bulles}
    \wrongchoice{Tri par insertion}
    \correctchoice{Tri par sélection}
    \wrongchoice{Aucun, on doit utiliser Timsort}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q25}
    Parmi les affirmations suivantes sur les tris
au programme (sélection, insertion), laquelle
est \textbf{fausse} ?
    \begin{choices}
    \wrongchoice{Le coût au pire des deux est quadratique.}
    \wrongchoice{Les deux tris peuvent être implémentés en place (sans liste auxiliaire).}
    \correctchoice{Le tri par sélection est stable par défaut.}
    \wrongchoice{Le tri par insertion est en coût linéaire sur une liste déjà triée.}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q26}
    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 ?
    \begin{choices}
    \wrongchoice{\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}
}
    \wrongchoice{\begin{lstlisting}
for i in range(1, len(liste)):
    valeur = liste[i]
    for j in range(i, 0, -1):
        liste[j] = valeur
\end{lstlisting}
}
    \correctchoice{\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}
}
    \wrongchoice{\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{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q27}
    Combien de comparaisons (entre éléments)
effectue le tri par \textbf{sélection} sur la liste
\texttt{[5, 3, 8, 1]} (n = 4) ?
    \begin{choices}
    \wrongchoice{4}
    \wrongchoice{16}
    \wrongchoice{3}
    \correctchoice{6}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q28}
    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 ?
    \begin{choices}
    \wrongchoice{Parce qu'un tri stable est plus rapide qu'un tri non stable}
    \wrongchoice{Parce qu'un tri stable consomme moins de mémoire}
    \wrongchoice{Parce que les classes sont des chaînes de caractères}
    \correctchoice{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{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q29}
    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 ») ?
    \begin{choices}
    \correctchoice{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
}
    \wrongchoice{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]}
}
    \wrongchoice{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]}
}
    \wrongchoice{Après passe $1$ : \texttt{[1, 2, 3, 4]}. Les
passes suivantes ne changent rien
}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q30}
    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} ?
    \begin{choices}
    \correctchoice{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]}
}
    \wrongchoice{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]}
}
    \wrongchoice{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]}
}
    \wrongchoice{Identique au tri par sélection :
\texttt{[1, 3, 4, 2]} puis \texttt{[1, 2, 4, 3]}
puis \texttt{[1, 2, 3, 4]}
}
    \end{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q31}
    Comment adapter un tri par insertion
croissant pour qu'il trie en ordre
\textbf{décroissant} ?
    \begin{choices}
    \wrongchoice{Appliquer le tri croissant puis
inverser la liste finale avec
\texttt{liste.reverse()}
}
    \wrongchoice{Trier la liste à l'envers d'abord, puis
appliquer le tri croissant
}
    \wrongchoice{Multiplier toutes les valeurs par
$-1$, trier, puis multiplier à
nouveau par $-1$
}
    \correctchoice{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{choices}
  \end{question}
}

\element{premieretris}{
  \begin{question}{q32}
    Que se passe-t-il quand on trie une liste
contenant des \textbf{doublons}, par exemple
\texttt{[3, 1, 3, 2, 3]} ?
    \begin{choices}
    \correctchoice{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é
}
    \wrongchoice{Les doublons sont automatiquement
supprimés
}
    \wrongchoice{L'algorithme tombe en boucle infinie
}
    \wrongchoice{Le tri lève une exception
}
    \end{choices}
  \end{question}
}


\onecopy{1}{
  \shufflegroup{premieretris}
  \insertgroup{premieretris}
}

\end{document}
