{"cells":[{"metadata":{},"cell_type":"markdown","source":"# Fonctions à savoir écrire rapidement autour de la notion de tri"},{"metadata":{"trusted":false},"cell_type":"code","source":"from _autotests import *","execution_count":5,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Indiquer si une liste est triée"},{"metadata":{},"cell_type":"markdown","source":"Écrire une fonction `est_triée` d'interface `est_triée(tableau: list) -> bool` qui renvoie `True` si la liste est bien triée et `False` sinon."},{"metadata":{"trusted":false},"cell_type":"code","source":"def est_triée(tableau: list) -> bool:\n ...","execution_count":3,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"assert est_triée([1, 2, 3, 4])","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"assert not est_triée([2, 3, 1, 4])","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"test_resultats(est_triée, [[1, 2, 3, 4], [2, 3, 1, 4]])","execution_count":4,"outputs":[{"output_type":"execute_result","execution_count":4,"data":{"text/plain":"","text/html":"\n \n \n \n \n \n \n \n \n \n \n \n \n
(tableau: list) -> boolest_triée(tableau: list) -> bool
attendu		est_triée(tableau: list) -> bool
calculé		Test
[1, 2, 3, 4]TrueNone❌
[2, 3, 1, 4]FalseNone❌
"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"En fonction de la longueur `n` du tableau, quel est le nombre d'opérations nécessaires dans le pire des cas ?"},{"metadata":{},"cell_type":"raw","source":""},{"metadata":{},"cell_type":"markdown","source":"## Renvoyer le minimum"},{"metadata":{},"cell_type":"markdown","source":"Écrire une fonction `indice_mini`, d'interface `indice_mini(tableau: list) -> int` qui renvoie l'indice du premier minimum d'un tableau."},{"metadata":{"trusted":false},"cell_type":"code","source":"def indice_mini(tableau: list) -> int:\n ...","execution_count":5,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"assert indice_mini([2, 3, 1, 4]) == 2","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"test_resultats(indice_mini, [[2, 3, 1, 4]])","execution_count":7,"outputs":[{"output_type":"execute_result","execution_count":7,"data":{"text/plain":"","text/html":"\n \n \n \n \n \n \n \n \n
(tableau: list) -> intindice_mini(tableau: list) -> int
attendu		indice_mini(tableau: list) -> int
calculé		Test
[2, 3, 1, 4]2None❌
"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"Écrire une fonction `mini_borne`, d'interface `mini_borne(tableau: list[float|int], indice: int) -> float|int` qui renvoie la plus petite valeur à partir d'une borne passé en argument."},{"metadata":{"trusted":false},"cell_type":"code","source":"def mini_borne(tableau: list[float|int], indice: int) -> float|int:\n \"\"\"\n Renvoie le minimum d'une sous liste à partir d'un indice de la liste\n \n Args:\n tableau (list): une liste Python d'entier ou de float\n indice (int): un indice du tableau\n Returns (float or int): une valeur du tableau\n \n Examples:\n >>> mini_borne([1, 2, 3], 1)\n 2\n >>> mini_borne([4, 7, 8, 9], 0)\n 4\n >>> mini_borne([4, 2, 5, 6, 10, 2], 3)\n 2\n \n \"\"\"\n ...","execution_count":8,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"assert ...","execution_count":9,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"test_resultats(mini_borne, [[[1, 2, 3], 1]])","execution_count":11,"outputs":[{"output_type":"execute_result","execution_count":11,"data":{"text/plain":"","text/html":"\n \n \n \n \n \n \n \n \n
(tableau: list[float | int], indice: int) -> float | intmini_borne(tableau: list[float | int], indice: int) -> float | int
attendu		mini_borne(tableau: list[float | int], indice: int) -> float | int
calculé		Test
[[1, 2, 3], 1]2None❌
"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"Écrire une fonction `mini_indice_borne` d'interface `mini_indice_borne(tableau: list[float|int], indice: int) -> float|int` qui renvoie l'indice de la plus petite valeur"},{"metadata":{"trusted":false},"cell_type":"code","source":"def mini_borne_indice(tableau: list[float|int], indice: int) -> float|int:\n \"\"\"\n Renvoie le minimum d'une sous liste à partir d'un indice (inclus) de la liste\n \n Args:\n tableau (list): une liste Python d'entier ou de float\n indice (int): un indice du tableau\n Returns (float or int): une valeur du tableau\n \n Examples:\n >>> mini_borne([1, 2, 3], 1)\n 1\n >>> mini_borne([4, 7, 8, 9], 0)\n 0\n >>> mini_borne([4, 2, 5, 6, 10, 2], 3)\n 5\n \n \"\"\"\n ...","execution_count":12,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"assert ...","execution_count":13,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"test_resultats(mini_borne_indice, [[[1, 2, 3], 1]])","execution_count":14,"outputs":[{"output_type":"execute_result","execution_count":14,"data":{"text/plain":"","text/html":"\n \n \n \n \n \n \n \n \n
(tableau: list[float | int], indice: int) -> float | intmini_borne_indice(tableau: list[float | int], indice: int) -> float | int
attendu		mini_borne_indice(tableau: list[float | int], indice: int) -> float | int
calculé		Test
[[1, 2, 3], 1]1None❌
"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"Reprendre les exercices précédents avec le maximum."},{"metadata":{"trusted":false},"cell_type":"code","source":"","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Utiliser les fonctions de tri de Python"},{"metadata":{},"cell_type":"markdown","source":"Afficher l'aide des fonctions `list.sort` et `sorted`. Quelle est la différence entre ces deux fonctions ?"},{"metadata":{"trusted":false},"cell_type":"code","source":"","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"raw","source":""},{"metadata":{},"cell_type":"markdown","source":"## Échanger des valeurs dans différents contextes."},{"metadata":{},"cell_type":"markdown","source":"Écrire une fonction `echanger(tableau: list, indice: int)` qui échange une valeur avec la suivante si c'est possible. Cette fonction utilisera le caractère mutable des `list` de Python. _On fera attention aux bornes de l'indice_."},{"metadata":{"trusted":false},"cell_type":"code","source":"def echanger(tableau: list, indice: int) -> None:\n ...","execution_count":15,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"tableau = [1, 2, 3, 4]\nechanger(tableau, 2)\nassert tableau == [1, 2, 4, 3]","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"test_resultats(echanger, [[[1, 2, 3, 4], 2]])","execution_count":17,"outputs":[{"output_type":"execute_result","execution_count":17,"data":{"text/plain":"","text/html":"\n \n \n \n \n \n \n \n \n
(tableau: list, indice: int) -> Noneechanger(tableau: list, indice: int) -> None
attendu		echanger(tableau: list, indice: int) -> None
calculé		Test
[[1, 2, 3, 4], 2]NoneNone✅
"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"Écrire une fonction `echanger_tuple(uplet: tuple, indice: int) -> tuple` qui renvoie un $n$-uplet où la valeur d'indice `indice` a été échangé avec la suivante."},{"metadata":{"trusted":false},"cell_type":"code","source":"def echanger_tuple(uplet: tuple, indice: int) -> tuple:\n ... ","execution_count":18,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"assert echanger_tuple((1, 2, 3, 4), 1) == (1, 3, 2, 4)","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"test_resultats(echanger_tuple, [[(1, 2, 3, 4), 2]])","execution_count":19,"outputs":[{"output_type":"execute_result","execution_count":19,"data":{"text/plain":"","text/html":"\n \n \n \n \n \n \n \n \n
(uplet: tuple, indice: int) -> tupleechanger_tuple(uplet: tuple, indice: int) -> tuple
attendu		echanger_tuple(uplet: tuple, indice: int) -> tuple
calculé		Test
[(1, 2, 3, 4), 2](1, 2, 4, 3)None❌
"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"Écrire une fonction `permute(tableau: list, i: int, j: int) -> list` qui renvoie une liste où la $i$ème etla $j$ème valeur ont été échangée."},{"metadata":{"trusted":false},"cell_type":"code","source":"def permute(tableau: list, i: int, j: int) -> list:\n ...","execution_count":2,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"assert permute([1, 2, 3, 4, 5], 2, 3) == [1, 2, 4, 3, 5]\nassert permute([1, 2, 3, 4, 5], 1, 4) == [1, 5, 3, 4, 2]\nassert permute([1, 2, 3, 4, 5], 2, 2) == [1, 2, 3, 4, 5]","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"test_resultats(permute, [[[1, 2, 3, 4, 5], 2, 3], [[1, 2, 3, 4, 5], 1, 4], [[1, 2, 3, 4, 5], 2, 2]])","execution_count":3,"outputs":[{"output_type":"execute_result","execution_count":3,"data":{"text/plain":"","text/html":"\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
(tableau: list, i: int, j: int) -> listpermute(tableau: list, i: int, j: int) -> list
attendu		permute(tableau: list, i: int, j: int) -> list
calculé		Test
[[1, 2, 3, 4, 5], 2, 3][1, 2, 4, 3, 5]None❌
[[1, 2, 3, 4, 5], 1, 4][1, 5, 3, 4, 2]None❌
[[1, 2, 3, 4, 5], 2, 2][1, 2, 3, 4, 5]None❌
"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"??? note Les permutations\n\nLes permutations sont un sujet d'étude en mathématiques. La fonciton d'échange s'appelle une transposition. Une permutation de deux éléments peut s'écrire comme un « produit » de ces transpositions.\nLes permutations présentées ici ne permuttent que deux éléments parmi tous les éléments, mais les permutations peuvent échanger tous les éléments d'une liste. On représente ces transpositions de la façon suivante :\n$$\\begin{pmatrix}\n1 & 2 & 3 & 4 & 5 \\\\\n4 & 3 & 2 & 5 & 1\n \\end{pmatrix}$$\n\nCes permutations sont en nombres finis si l'ensemble de départ est fini. Il y en a exactement $n!$ qui est un nombre qui représente $n × (n-1) × … × 1$.\n???"},{"metadata":{},"cell_type":"markdown","source":"## Des tris dans différents contextes"},{"metadata":{},"cell_type":"markdown","source":"Donner le principe du tri à bulles"},{"metadata":{},"cell_type":"raw","source":""},{"metadata":{},"cell_type":"markdown","source":"À l'aide d'une simple boucle, montrer sur un exemple que le plus grand élément d'une liste, par des échanges avec le voisins, se retrouve en dernière position."},{"metadata":{"trusted":false},"cell_type":"code","source":"tableau = [3, 2, 4, 1]\nfor i in range(...):\n if ... > ...:\n tableau[i], tableau[i+1] = tableau[i+1], tableau[i]\ntableau","execution_count":15,"outputs":[{"output_type":"execute_result","execution_count":15,"data":{"text/plain":"[2, 3, 1, 4]"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"Préciser le rôle de la ligne 4 ? Par quelle fonction pourrait-on la remplacer ?"},{"metadata":{},"cell_type":"raw","source":""},{"metadata":{},"cell_type":"markdown","source":"Écrire une fonction `tri_bulles(tableau: list) -> list:` qui met en œuvre le tri à bulles. _De façon excpetionnelle, on utilisera `print` dans le corps de la fonction pour montrer les différents états du tableau._"},{"metadata":{"trusted":false},"cell_type":"code","source":"def tri_bulles(tableau: list) -> list:\n ...","execution_count":4,"outputs":[]},{"metadata":{"trusted":false,"scrolled":true},"cell_type":"code","source":"assert tri_bulles([2, 3, 1, 4]) == [1, 2, 3, 4]","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"test_resultats(tri_bulles, [[2, 3, 1, 4]])","execution_count":6,"outputs":[{"output_type":"stream","text":"[2, 3, 1, 4]\n[2, 1, 3, 4]\n[2, 1, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n[1, 2, 3, 4]\n","name":"stdout"},{"output_type":"execute_result","execution_count":6,"data":{"text/plain":"","text/html":"\n \n \n \n \n \n \n \n \n
(tableau: list) -> listtri_bulles(tableau: list) -> list
attendu		tri_bulles(tableau: list) -> list
calculé		Test
[1, 2, 3, 4][1, 2, 3, 4]None❌
"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"Donner un résumé du rôle des fonctions `list.pop` et `list.append`."},{"metadata":{},"cell_type":"raw","source":""},{"metadata":{},"cell_type":"markdown","source":"En utilisant `valeur = list.pop(tableau, indice)` et `list.append(tableau, valeur)`, écrire une fonction `tri_selection` qui renvoie une liste triée. On pourra, au choix, utiliser la fonction `mini` du début de cette fiche ou la fonction `min` de Python."},{"metadata":{"trusted":false},"cell_type":"code","source":"def tri_selection(tableau):\n ...\n for ...:\n indice = ...\n valeur = ...\n list.append(tableau_trie, valeur)\n return ...","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"assert tri_selection([2, 3, 1, 4]) == [1, 2, 3, 4]","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"test_resultats(tri_selection, [2, 3, 1, 4])","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"!!! info Ordre dans les dictionnaires\nDe façon générale, la structure de dictionnaire est réputée ne pas être ordonnée. Cependant, Python, depuis la version 3.7 dans les faits et officiellement depuis la version 3.11, garantit l'ordre d'insertion des couples `(clefs, valeurs)`.\n!!!"},{"metadata":{},"cell_type":"markdown","source":"En utilisant les fonctions `dict.pop` et `dict.update` dont un exemple d'usage est donné dessous, écrire une fonction qui renvoie un dictionnaire trié suivant les clefs."},{"metadata":{"trusted":false},"cell_type":"code","source":"nombres = {3: 'trois', 1: 'un', 2: 'deux'}\ndict.pop(nombres, 1)","execution_count":2,"outputs":[{"output_type":"execute_result","execution_count":2,"data":{"text/plain":"'un'"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"nombres_triés = {}\ndict.update(nombres_triés, {1: 'un'})","execution_count":5,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"nombres_triés","execution_count":6,"outputs":[{"output_type":"execute_result","execution_count":6,"data":{"text/plain":"{1: 'un'}"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"def tri_dictionnaire(dictionnaire: dict) -> dict:\n ...","execution_count":9,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"assert tri_dictionnaire({3: 'trois', 1: 'un', 2: 'deux'}) == {1: 'un', 2: 'deux', 3: 'trois'}","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"test_resultats(tri_dictionnaire, [{3: 'trois', 1: 'un', 2: 'deux'}])","execution_count":10,"outputs":[{"output_type":"execute_result","execution_count":10,"data":{"text/plain":"","text/html":"\n \n \n \n \n \n \n \n \n
(dictionnaire: dict) -> dicttri_dictionnaire(dictionnaire: dict) -> dict
attendu		tri_dictionnaire(dictionnaire: dict) -> dict
calculé		Test
{3: 'trois', 1: 'un', 2: 'deux'}{1: 'un', 2: 'deux', 3: 'trois'}None❌
"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"## Tris de structures plus complexes"},{"metadata":{},"cell_type":"markdown","source":"On veut trier une liste de coordonnées (par exemple `(latitude, longitude)`) suivant la longitude. Il va donc falloir jouer sur la clef de tri."},{"metadata":{},"cell_type":"markdown","source":"!!! tip Avec Python\nOn peut, avec la fonction `sorted` de Python, utiliser une clef de sélection différente pour effectuer un tri.\n\nPour cela, il faut définir une fonction de sélection qu'on utilisera comme argument de la fonction `sorted`.\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"def projection_y(couple: tuple[float]) -> float:\n return couple[1]","execution_count":6,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"coordonnées = [(2.34, 45.71), (2.35, 45.70), (2.37, 45.69)]","execution_count":4,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"sorted(coordonnées, key=projection_y)","execution_count":26,"outputs":[{"output_type":"execute_result","execution_count":26,"data":{"text/plain":"[(2.37, 45.69), (2.35, 45.7), (2.34, 45.71)]"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"Écrire une fonction `tri_longitude` qui met en œuvre un tri par insertion des coordonnées en les triant par longitude. _On peut réutiliser la fonction `projection_y`."},{"metadata":{"trusted":false},"cell_type":"code","source":"def tri_longitude(coordonnees: list[tuple]) -> list[tuple]:\n ...","execution_count":2,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"assert tri_longitude(coordonnées) == [(2.37, 45.69), (2.35, 45.7), (2.34, 45.71)]","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"test_resultats(tri_longitude, [coordonnées])","execution_count":5,"outputs":[{"output_type":"execute_result","execution_count":5,"data":{"text/plain":"","text/html":"\n \n \n \n \n \n \n \n \n
(coordonnees: list[tuple]) -> list[tuple]tri_longitude(coordonnees: list[tuple]) -> list[tuple]
attendu		tri_longitude(coordonnees: list[tuple]) -> list[tuple]
calculé		Test
[(2.34, 45.71), (2.35, 45.7), (2.37, 45.69)][(2.37, 45.69), (2.35, 45.7), (2.34, 45.71)]None❌
"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"??? tip Les fonctions `lambda`\nOn trouve parfois des fonctions non nommées définies par la syntaxe suivante appliquée à l'exemple ci-dessus `lambda x: x[1]`.\n???"},{"metadata":{"trusted":false},"cell_type":"code","source":"def valeur_cartes(carte: str|int) -> int:\n assert type(carte) in [int, str]\n cartes = {'as': 1, 'valet': 11, 'dame': 12, 'roi': 13}\n if type(carte) is str:\n assert str.lower(carte) in cartes\n return cartes[str.lower(carte)]\n else:\n assert 2 <= carte <= 10\n return carte\n ","execution_count":1,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"jeu = ['As', 'Dame', 7, 8, 'Valet']\nsorted(jeu, key=valeur_cartes)","execution_count":2,"outputs":[{"output_type":"execute_result","execution_count":2,"data":{"text/plain":"['As', 7, 8, 'Valet', 'Dame']"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"min(jeu, key=valeur_cartes)","execution_count":35,"outputs":[{"output_type":"execute_result","execution_count":35,"data":{"text/plain":"'As'"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"Écrire une fonction `trier_jeu` qui effectue un tri par sélection d'un jeu de carte. _La clef de tri doit être mis en œuvre dans la fonction `mini`._"},{"metadata":{"trusted":false},"cell_type":"code","source":"","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"name":"python3","display_name":"Python 3","language":"python"}},"nbformat":4,"nbformat_minor":2}