Insérer un élément dans une liste triée en Python : méthodes, complexités et bonnes pratiques
Il est fréquent que l’on doive trier une liste de nombres par ordre croissant, par exemple en mathématiques, pour déterminer la médiane ou les quartiles. L’algorithme de tri par insertion est sans doute le plus simple des algorithmes de tri. Bien entendu, toute la force d’un algorithme se voit lorsqu’on trie une longue liste. Prenons le premier chiffre qui se présente : 2. On prend ensuite le chiffre suivant : 0. Que fait-on quand on prend une nouvelle carte ? On pose cette carte à la droite des autres, puis on la permute successivement avec les autres, en partant de la droite, jusqu’à obtenir une carte qui lui est inférieure.
Autrement dit, on va d’abord coller item à la fin de liste, puis parcourir liste à partir de la fin. Pour cela peut utiliser une fonction permuter. Une deuxième fonction : permuter. La fonction permuter suivante prend trois paramètres : liste est une liste ; index1 est un nombre entier supérieur ou égal à 0 et strictement inférieur à la longueur de liste ; index2 est un nombre entier strictement supérieur à index1 et strictement inférieur à la longueur de liste. Cette fonction va permuter les éléments de rangs index1 et index2 de liste. Retour à l’insertion. Notre fonction insertion consiste donc à coller un item à la fin d’une liste déjà ordonnée, puis à le permuter avec l’élément précédent tant que cet élément précédent est plus grand que lui. Le test place>=0 dans la boucle sert à ne pas dépasser : place ne doit pas devenir inférieur à 0. Notez que cette fonction peut insérer un nombre dans une liste vide.
Il reste à programmer une fonction trierParInsertion qui prend en paramètre une liste de nombres et renvoie une liste contenant les mêmes nombres, dans l’ordre. On va créer une première liste ordonnée : la liste vide. Quelques remarques pour aller plus loin. Pour faciliter la compréhension de la méthode et du code, ce qui est l’objectif principal de ce blog, celui-ci a été découpé en plusieurs fonctions. On peut remarquer que la fonction insertion ne renvoie rien : elle modifie la liste qui lui est donnée « en place », sans créer de nouvelle liste. Ce n’est pas le cas de la fonction trierParInsertion qui crée une nouvelle liste. L’avantage de travailler sur des listes « en place » est parfois essentiel : imaginez que vous deviez trier tous les fichiers de votre ordinateur par date de création. Il vaut mieux éviter de tout recopier !
Il faut bien comprendre que l’algorithme comprend deux boucles : une première sur les index croissants et, à l’intérieur de celle-ci, une autre boucle « while » décroissante, qui part de index et s’arrête lorsqu’on a trouvé un élément plus petit ou atteint le début du tableau (la partie while j>0 and liste[j-1] > item). I. L'opération, pour chaque position i, consiste à prendre l'éléments d'indice i (la clef) et à l'insérer à la bonne place dans le tableau des éléments d'indices 0 à i - 1. Ce processus assure que les i premiers éléments seront triés. Cette étape réalisée, on va comparer sa valeur à la carte précédente.
II. 1. Contrairement à l'exemple du tri de cartes, il est impossible de « sortir un élément » du tableau. Les décalages vers la droite vont, quant à eux, alors dupliquer des valeurs ! Toutefois, chaque valeur dupliquée sera « écrasée » de proche en proche lors des décalages. L'illustration ci-dessous présente ce fonctionnement dans le cadre d'un tableau. 2. 3. Tester ci-dessous. La fonction n'a pas de return, c'est une procédure. Tester ci-dessous. C'est ce qu'on appelle un effet de bord. III. La première itération étudie la deuxième valeur, le 1. La troisième itération décale le 5. La performance du tri par insertion peut s'évaluer en nombre d'itérations élémentaires. La boucle principale est une boucle « Pour ». On présente ci-dessous les différentes étapes du tri. Combien d'itérations ? Le pire des cas est atteint lorsque le tableau est trié dans l'ordre décroissant. On effectue donc au total 1 + 2 + 3 + …+(N-1) décalages. On retrouve la somme étudiée dans cette page. 💣 Attention, il y a une difficulté supplémentaire. Le tri par insertion est beaucoup plus lent si la liste n'est pas triée. Nous avons vu que nous mesurons le pire des cas. Or le tri par insertion est à effet de bord. ⌛ Il faut attendre un peu ... Que se passe-t-il ? Lorsque la taille de la liste et multipliée par 3, le temps est multiplié par 9. IV. 1. Cela se comprend aisément car dans chaque tour de boucle nous avions utilisé la fonction insere dont le rôle est de ranger les i premiers éléments de la liste par ordre croissant. V. 😒 La procédure de tri par insertion contient une boucle while. Avant la boucle, j vaut i et 0 <= i < n. 😀 Notons que si i = 0 on n'entre pas dans la boucle, elle se termine d'emblée sans commencer. 🏃 Sinon, on démarre avec j > 0, on entre donc dans la boucle. Ceci prouve que la boucle se termine. j est un variant de boucle qui nous a permis de démontrer la terminaison de l'algorithme. VI. VII. Python inclut par défaut toute une série de méthodes qui simplifient et accélèrent l’exécution des programmes. Parmi celles-ci, on peut noter la méthode Python insert() qui permet d’insérer un seul élément dans une Python List existante. La méthode Python insert se construit avec deux paramètres : l’élément à insérer et l’index (l’emplacement) où cet élément doit être inséré. Comme les listes Python sont hétérogènes, cet élément peut être une donnée de n’importe quel type (par ex. une liste, un entier, etc.). En revanche, l’index doit être indiqué sous forme d’entier. Dans cet exemple, la chaîne de caractères (ou « string » en anglais) "sucre" est insérée à la position 1 dans la liste ingredients. L’index où l’élément est inséré constitue le premier argument, l’élément lui-même le second. Comme d’habitude, les deux paramètres peuvent être insérés directement ou définis comme des variables avant l’appel de la méthode. Dans cet exemple, on complète une liste d’ingrédients de pâtisserie par des ingrédients supplémentaires, insérés respectivement aux index 0 et 2. Il est important de noter que l’indéxation en Python commence à 0, comme dans la plupart des autres langages de programmation. Cela signifie que le premier élément reçoit l’indice 0, le deuxième élément l’indice 1 et ainsi de suite. Lorsque qu’un élément est inséré dans une liste Python avec insert(), le programme va bien sûr lui faire de la place. Si l’index spécifié est situé en dehors de la plage valide dans la liste (plus grand que le nombre d’éléments de la liste, par exemple), l’élément sera simplement inséré en fin de liste. Dans ce cas, insert() se comporte exactement comme la méthode Python append(). Cependant, si on associe à un élément un index négatif, il sera interprété comme distance depuis la fin de la liste. Par exemple, -1 correspondrait à l’avant-dernier élément, -2 à l’antépénultième, etc. Vous cherchez à mettre en ligne votre site Internet ou votre application Web rapidement, facilement et sans problème ? Selon la fonction dont vous avez besoin, il existe plusieurs opérateurs Python utiles comme des variantes de la méthode insert().
Lire aussi: Modifier Activité Kbis Auto-Entrepreneur
L’opérateur d’index permet de lire ou remplacer un élément à un index donné dans une liste. Il est donc possible de remplacer un élément d’une liste par un autre avec cet opérateur index. Il se peut aussi que vous ne souhaitiez pas supprimer d’élément de votre liste, voire que vous souhaitiez insérer plusieurs éléments en même temps au milieu de votre liste. Dans ce cas, le mieux est de passer par l’opérateur Slice. Contrariement à l’opérateur Index, l’opérateur Slice ne renvoie pas un seul élément d’une liste, mais une sous-séquence de la liste. Ainsi, on pourrait faire sortir de notre liste ingredients les éléments des indices 3 à 5 et obtenir ainsi la sous-séquence [‘sel’, ‘beurre’, ‘levure chimique’].
Pour cela, nous avons d’abord pris tous les éléments de ingredients jusqu’à l’index 3 avec l’opérateur Slice et nous les avons concaténés avec inserer. Ensuite, nous avons pris tous les éléments de ingredients à partir de l’index 3 et avons concaténé notre liste avec celle-ci. Il est important de noter que cette solution nécessite de nombreuses écritures. En effet, avec elle toute la liste est écrasée.
Je ne connais pas Python, mais quand tu parles d'une liste triée, c'est une propriété de la liste ou simplement toi qui la trie ? Pour une liste normale (triée ou triable par en O(n log n)) vous pourriez poser l'élément à trier comme dernier élément (append donc O(1)) puis quicksort - ce qui reviendra à faire une recherche dichotomique en O(log n) + l'insert qui se fait en O(n). On finit alors avec un O(n) si on considère la liste initiale comme étant triée. La solution en O(log n) serait d'utiliser une linked list, dans laquelle on peut accéder à n'importe quel index en temps constant, et donc insérer en temps constant. Mais bon, ça c'est la théorie, la vérité est que le cache s'en prendra un coup et que bien qu'en complexité on y gagne, en temps effectif je ne suis pas sûr que cela vaille le coup.
Envoyé par Dicedead: La solution en O(log n) serait d'utiliser une linked list, dans laquelle on peut accéder à n'importe quel index en temps constant, Une linked list nécessite de parcourir toute la liste depuis le début pour accéder à un élément. Donc pas en temps constant mais en O(n). Ce qui donne accès à n'importe quel élément en temps constant, c'est le tableau mais qui est aussi appelé list en python. Envoyé par Dicedead
Mais bon, ça c'est la théorie, la vérité est que le cache s'en prendra un coup et que bien qu'en complexité on y gagne, en temps effectif je ne suis pas sûr que cela vaille le coup. J'aimerais savoir quelle est la manière optimale d'insérer un élément dans une liste triée. Par liste, tu entends liste chainée ou liste au sens Python c'est-à dire tableau ? Ou plutôt dois-je rajouter l'élément à la liste et procéder à un quicksort ? Une insertion naïve dans une liste chainée triée tout en gardant le tri est en O(n). Un quicksort est au mieux en O(n log(n)). Ne serait-ce pas append qui est en O(n) et l'insertion (par la méthode push) en temps constant pour une linked list? Et en ce qui concerne le quicksort, vu que l'on ne l'applique qu'à un seul élément, une seule recherche dichotomique sera effectuée, d'où O(log n) pour cette étape et donc ensuite + O(n) si insert dans liste normale aka list ie array d'autres langages, ou + O(1) si push en linked. Envoyé par Dicedead
Lire aussi: INPI et Micro-Entreprise : Démarches
Lire aussi: Comment Calculer la TVA ?
balises: