<jupyter_start><jupyter_text>notebook consultable, exécutable, modifiable et téléchargeable en ligne :         	- se rendre à : https://github.com/nsi-acot/continuite_pedagogique_premiere- cliquer sur l'icone "launch binder" en bas de page- patienter quelques secondes que le serveur Jupyter démarre- naviguer dans le dossier `"./algorithmique/tri_selection/"`- cliquer sur le nom de ce notebook   TRIER  Le tri est une activité fondamentale et omniprésente de l'informatique. * On l'utilise régulièrement, par exemple :   * Lorsque l'on consulte sur Internet des listes de produits que l'on souhaite afficher par prix croissant ou décroissant, par popularité...   * Lorsque dans un tableur on souhaite trier des noms par ordre alphabétique   * Lorsque l'on affiche ses photos par date* Cela permet d'étudier des concepts algorithmiques puissants et efficaces* Pour simplifier, on cherche ici à trier des liste d'entiers dans l'ordre croissant. Le but d’un algorithme de tri est ainsi de calculer une nouvelle liste, oude modifier la liste initiale, de manière à ce qu’elle contienne les mêmesnombres que la liste de départ, mais que ces éléments soient ordonnés.<jupyter_code>#Générer une liste d'entiers aléatoires
from random import *
L=[randint(-32,32) for i in range(5)]
print(L)<jupyter_output>[12, -16, -21, -10, -9]<jupyter_text>1. De quoi dispose un ordinateur pour trier ?* Une fonction de comparaison ($$ ), pour comparer deux valeurs.* Des zones de stockage pour mémoriser des emplacements(à l'aide de l'index des éléments d'une liste), déplacer des valeurs...* Il existe des dizaines d'algorithmes de tri, nous allons en étudier 2 cette année :   * **Le tri par sélection.**  * **Le tri par insertion.**  2. Le tri par sélection Présentation * On commence par chercher, parmi les nombres à trier, un élément plus petit que tous les autres. Cet élément sera le premier de la liste triée. * On cherche ensuite, parmi ceux qui restent, un élément plus petit que tous les autres, qui sera le deuxième du tableau trié* On recommence pour trouver le troisième élément trié et ainsi de suite jusqu'à ce que toute la liste soit triée. Exemple : On cherche à trier la liste suivante : `[29, -6, 12, -11, 10]`* Le plus petit élement est $-11$, on le place au premier index 0* Que fait-on du $29$ ? Il prend la place de $-11$, la liste devient donc : `[-11,-6,12,29,10]`* Le plus petit des élements restants à trier est $-6$, il est déjà bien placé à l'index 1.* Le plus petit des élements restants à trier est $10$, on le place en troisième position (index 2).* Que fait-on du $12$ ? Il prend la place de $10$, la liste devient donc : `[-11,-6,10,29,12]`* Le plus petit des élements restants à trier est $12$, on le place en quatrième position (index 3).* Que fait-on du $29$ ? Il prend la place de $12$, la liste devient donc : `[-11,-6,10,12,29]`* Le dernier élément est nécéssairement le plus grand, la liste est triée.  Exercice 1 :1. En indiquant les listes intermédiaires, trier la liste `[5, -27, -14, 10, 7]` par sélection     *       *      *      *   2. Même exercice avec la liste `[30, 24, -7, -19, 26, 21, -18]`   *     *     *     *     *    Complexité Exercice 2 : On cherche à trier la liste suivante par sélection : `[12, 31, -2, -14, 8]`1. Au premier parcours, la liste devient `[-14, 31, -2, 12, 8]`. Combien de comparaisons ont été nécéssaires pour identifier que $-14$ est le plus petit élement ?2. Au deuxième parcours la liste devient `[-14, -2, 31, 12, 8]`. Combien de comparaisons ont été nécéssaires pour identifier que $-2$ est le plus petit des éléments restant à trier ?3. Combien de comparaisons sont nécéssaires pour trier toute la liste ?4. Est-ce vrai pour toutes les listes de cinq éléments ? Réponse :1.  2.  3.  4.    Exercice 3 :1. Combien de comparaisons sont nécéssaires pour trier par sélection une liste de 7 éléments ?2. Et pour une liste de 10 éléments ?3. Et pour $n$ éléments ? Réponse : 1.  2.  3.    A retenirQuelque soit le nombre d'éléments $n$ d'éléments à trier et dans tous les cas( par exemple même quand la liste est partiellement triée), le nombre de comparaisons est exactement $\frac{n\times(n-1)}{2}=\frac{n^{2}-n}{2}$, c'est à dire de l'ordre de $n^2$.On dit que cet algorithme est de complexité quadratique en $\mathcal{O}(n^2)$.Par exemple , une liste de $25000$ éléments à trier nécéssite de l'ordre de $25000^2=625000000$ comparaisons.  Programmation  Recherche du minimum et échangeLa première étape de l'algorithme est de rechercher le minimum de la liste et d'échanger sa place avec le premier élément:  $(1)\; L \; est\;une\;liste\\(2)\; indexmin \leftarrow 0\\(3)\; Pour\; j\; de \;1\;à \; index\;du\;dernier\;élément\;de\;L \\(4)\; \; \; \; \;  Si\; L[j]<L[indexmin] \\(5) \; \; \; \; \; \; \; \;\;indexmin \leftarrow j \\(6)\; L[0],L[indexmin]=L[indexmin],L[0]$  Exercice 4 :1. Que représente la variable `indexmin` ?2. Expliquer la ligne 6 de l'algorithme.3. En remplaçant les commentaires, programmer cet algorithme. Réponses :1.  2.<jupyter_code>L=[randint(-32,32) for i in range(5)]
print(L)

#ligne2
#ligne3
#ligne4
#ligne5
#ligne6

print(L)<jupyter_output><empty_output><jupyter_text>Exercice 5 :On suppose que le minimum de la liste est désormais le premier élément. L'étape suivante est d'identifier le plus petit élément parmi ceux restant à trier et de le placer en deuxième position.1. Recopier et modifier l'algorithme précédent en ce sens. On utilisera la liste`[-29, 24, 31, -15, 8]`. l'instruction`print(L)` doit renvoyer `[-29, -15, 31, 24, 8]`.2. Qu'a-t-on modifié précisement ?3. Que doit-on modifier pour trouver le troisième élement de la liste triée ?<jupyter_code>#1
L=[-29, 24, 31, -15, 8]

#ligne2
#ligne3
#ligne4
#ligne5

print(L)<jupyter_output><empty_output><jupyter_text>2.  3. Pour trouver le troisième élément trié , il faut :   *     *     *    Algorithme du tri par sélection  Exercice 6 :La fonction `tri_select(L)` prend en paramètre une liste `L` d'entiers et doit renvoyer cette liste triée par sélection.En vous aidant des résultats précédents, compléter cette fonction en remplaçant les `?`.<jupyter_code>#Algorithme de tri par sélection
def tri_select(L):
    for i in ?:
        imin = ?
        for j in range(?,len(L)):
            if L[j]<L[imin]:
                imin=j
                
        L[?],L[imin]=L[imin],L[?]
    
    return L
        
L=[randint(-32,32) for i in range(5)]
print (L)
print(tri_select(L))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10629738511527155, 'fraction_numerical': 0.03759863840321832, 'mean_word_length': 3.8601503759398494, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 16, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '665559', 'license': 'CC0-1.0', 'n_tokens_mistral': 2390, 'n_tokens_neox': 2264, 'n_words': 906, 'path': 'algorithmique/tri_selection/Tris_Selection.ipynb', 'repo_name': 'herve-vasseur/python-lycee', 'size': '6463'}