{"id":7335,"date":"2022-02-22T18:31:41","date_gmt":"2022-02-22T17:31:41","guid":{"rendered":"https:\/\/www.mathweb.fr\/euclide\/?page_id=7335"},"modified":"2023-10-10T10:40:16","modified_gmt":"2023-10-10T08:40:16","slug":"effectuer-un-tri-en-python","status":"publish","type":"page","link":"https:\/\/www.mathweb.fr\/euclide\/effectuer-un-tri-en-python\/","title":{"rendered":"Effectuer un tri en Python"},"content":{"rendered":"\n

Nous allons voir comment \u00e9crire des fonctions de tri en Python.<\/p>\n\n\n\n\n\n\n\n

Tri en Python: avant-propos<\/h2>\n\n\n\n

Les histoires de tris en Python sont d’un importance capitale. En effet, si l’on souhaite trier une collection colossale, nous n’avons pas le droit d’utiliser un algorithme lent, un algorithme dit “na\u00eff”. Pourquoi ?<\/p>\n\n\n\n

La raison est simple: plus ce qu’il y a \u00e0 trier est grand, plus \u00e7a va prendre de temps… et des ressources mat\u00e9rielles que nous n’avons pas toujours.<\/p>\n\n\n\n

D’o\u00f9 la question de trouver un algorithme efficace…<\/p>\n\n\n\n

Un tri na\u00eff en Python<\/h2>\n\n\n\n

Le tri na\u00eff consiste \u00e0 parcourir la liste \u00e0 trier et construire une autre liste cr\u00e9\u00e9e \u00e0 partir de la premi\u00e8re en y ins\u00e9rant chaque \u00e9l\u00e9ment convenablement.<\/p>\n\n\n\n

Un premier tri na\u00eff<\/h3>\n\n\n\n
def insertNaif(A,e):\n    if e < A[0] :\n        return [e] + A\n    else:\n        for n in range( 1 , len(A) ):\n            if e > A[n-1] and e <= A[n]:\n                return A[:n] + [e] + A[n:]\n        return A + [e]\n\ndef triNaif(L):\n    R = [ L[0] ]\n    for n in range(1,len(L)):\n        R = insertNaif(R,L[n])\n        \n    return R<\/pre>\n\n\n\n
Un deuxi\u00e8me tri na\u00eff<\/h3>\n\n\n\n
def triNaif(L):\n    R = []\n    while len(L) > 0:\n        m = L[0]\n        for i in range(1,len(L)):\n            if L[i] < m:\n                m = L[i]\n        R += [ m ]\n        L.pop( L.index(m) )\n        \n    return R<\/pre>\n\n\n\n
Tri \u00e0 bulles<\/h3>\n\n\n
\n
\"tri<\/figure>\n<\/div>\n\n\n
Sans doute le plus na\u00eff des algorithmes, et donc le plus “gourmand” (en m\u00e9moire et en temps): il consiste \u00e0 parcourir la liste \u00e0 rebours en partant de sa fin, et de comparer chaque \u00e9l\u00e9ment cons\u00e9cutif en partant du d\u00e9but jusqu’\u00e0 l’\u00e9l\u00e9ment courant. Si deux \u00e9l\u00e9ments ne sont pas dans l’ordre croissant, ils sont permut\u00e9s.<\/p>\n\n\n\n
Bien entendu, il faut absolument \u00e9viter les tris na\u00effs car leur complexit\u00e9 est quadratique.<\/p>\n\n\n\n
def triBulles(L):\n    for i in range(len(L),0,-1):\n        for j in range(0,i-1):\n            if L[j+1] < L[j]:\n                L[j+1] , L[j] = L[j] , L[j+1]\n                \n    return L<\/pre>\n\n\n\n
La version r\u00e9cursive:<\/p>\n\n\n\n
def triPlace(L):\n    for n in range( 1 , len(L) ):\n        if L[n] < L[n-1]:\n            L[n-1] , L[n] = L[n] , L[n-1]\n            return triPlace( L )\n        \n    return L<\/pre>\n\n\n\n
Une variante est d’ins\u00e9rer un bool\u00e9en pour rompre la boucle principale.<\/p>\n\n\n\n
def triBulles(L):\n    for i in range(len(L),0,-1):\n        liste_tri\u00e9e = True\n        for j in range(0,i-1):\n            if L[j+1] < L[j]:\n                L[j+1] , L[j] = L[j] , L[j+1]\n                liste_tri\u00e9e = False\n        if liste_tri\u00e9e == True:\n            break\n                \n    return L<\/pre>\n\n\n\n
Le tri fusion en Python<\/h2>\n\n\n\n
Sur la page https:\/\/fr.wikipedia.org\/wiki\/Tri_fusion#Algorithme<\/a>, on peut y voir un algorithme de tri fusion. Il consiste \u00e0 fusionner deux listes en triant leurs \u00e9l\u00e9ments afin de donner une liste ordonn\u00e9e.<\/p>\n\n\n\n
Cet algorithme donne en Python:<\/p>\n\n\n\n
def triFusion(L):\n    if len(L) == 1:\n        return L\n    else:\n        return fusion( triFusion(L[:len(L)\/\/2]) , triFusion(L[len(L)\/\/2:]) )\n    \ndef fusion(A,B):\n    if len(A) == 0:\n        return B\n    elif len(B) == 0:\n        return A\n    elif A[0] <= B[0]:\n        return [A[0]] + fusion( A[1:] , B )\n    else:\n        return [B[0]] + fusion( A , B[1:] )<\/pre>\n\n\n\n
>>> L = [2,55,12,10,23,87,11,74,36,42,58]\n>>> triFusion(L)\n[2, 10, 11, 12, 23, 36, 42, 55, 58, 74, 87]<\/code><\/pre>\n\n\n\n
Cet algorithme fait partie des algorithmes r\u00e9cursifs utilisant le paradigme du “diviser pour r\u00e9gner<\/a>“.<\/p>\n\n\n\n
[Revenir \u00e0 la page pr\u00e9c\u00e9dente]<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
Nous allons voir comment \u00e9crire des fonctions de tri en Python.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"open","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-7335","page","type-page","status-publish","hentry"],"yoast_head":"\nEffectuer un tri en Python - Mathweb.fr<\/title>\n<meta name=\"description\" content=\"Nous allons voir comment \u00e9crire des fonctions de tri en Python: tri na\u00eff, tri \u00e0 bulles, tri en place, tri fusion, etc.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.mathweb.fr\/euclide\/effectuer-un-tri-en-python\/\" \/>\n<meta property=\"og:locale\" content=\"fr_FR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Effectuer un tri en Python - Mathweb.fr\" \/>\n<meta property=\"og:description\" content=\"Nous allons voir comment \u00e9crire des fonctions de tri en Python: tri na\u00eff, tri \u00e0 bulles, tri en place, tri fusion, etc.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.mathweb.fr\/euclide\/effectuer-un-tri-en-python\/\" \/>\n<meta property=\"og:site_name\" content=\"Mathweb.fr\" \/>\n<meta property=\"article:modified_time\" content=\"2023-10-10T08:40:16+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2022\/02\/triBulles.png\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Dur\u00e9e de lecture estim\u00e9e\" \/>\n\t<meta name=\"twitter:data1\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/effectuer-un-tri-en-python\\\/\",\"url\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/effectuer-un-tri-en-python\\\/\",\"name\":\"Effectuer un tri en Python - Mathweb.fr\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/effectuer-un-tri-en-python\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/effectuer-un-tri-en-python\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2022\\\/02\\\/triBulles.png\",\"datePublished\":\"2022-02-22T17:31:41+00:00\",\"dateModified\":\"2023-10-10T08:40:16+00:00\",\"description\":\"Nous allons voir comment \u00e9crire des fonctions de tri en Python: tri na\u00eff, tri \u00e0 bulles, tri en place, tri fusion, etc.\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/effectuer-un-tri-en-python\\\/#breadcrumb\"},\"inLanguage\":\"fr-FR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/effectuer-un-tri-en-python\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"fr-FR\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/effectuer-un-tri-en-python\\\/#primaryimage\",\"url\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2022\\\/02\\\/triBulles.png\",\"contentUrl\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2022\\\/02\\\/triBulles.png\",\"width\":343,\"height\":74},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/effectuer-un-tri-en-python\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Accueil\",\"item\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Effectuer un tri en Python\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/#website\",\"url\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/\",\"name\":\"Mathweb.fr\",\"description\":\"Math\u00e9matiques, LaTeX et Python\",\"publisher\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/#\\\/schema\\\/person\\\/e4d3bb07968238378f0d5052a70dcd69\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"fr-FR\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/#\\\/schema\\\/person\\\/e4d3bb07968238378f0d5052a70dcd69\",\"name\":\"St\u00e9phane Pasquet\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"fr-FR\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2025\\\/06\\\/cropped-logo-mathweb.webp\",\"url\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2025\\\/06\\\/cropped-logo-mathweb.webp\",\"contentUrl\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2025\\\/06\\\/cropped-logo-mathweb.webp\",\"width\":74,\"height\":77,\"caption\":\"St\u00e9phane Pasquet\"},\"logo\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2025\\\/06\\\/cropped-logo-mathweb.webp\"}}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Effectuer un tri en Python - Mathweb.fr","description":"Nous allons voir comment \u00e9crire des fonctions de tri en Python: tri na\u00eff, tri \u00e0 bulles, tri en place, tri fusion, etc.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.mathweb.fr\/euclide\/effectuer-un-tri-en-python\/","og_locale":"fr_FR","og_type":"article","og_title":"Effectuer un tri en Python - Mathweb.fr","og_description":"Nous allons voir comment \u00e9crire des fonctions de tri en Python: tri na\u00eff, tri \u00e0 bulles, tri en place, tri fusion, etc.","og_url":"https:\/\/www.mathweb.fr\/euclide\/effectuer-un-tri-en-python\/","og_site_name":"Mathweb.fr","article_modified_time":"2023-10-10T08:40:16+00:00","og_image":[{"url":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2022\/02\/triBulles.png","type":"","width":"","height":""}],"twitter_card":"summary_large_image","twitter_misc":{"Dur\u00e9e de lecture estim\u00e9e":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.mathweb.fr\/euclide\/effectuer-un-tri-en-python\/","url":"https:\/\/www.mathweb.fr\/euclide\/effectuer-un-tri-en-python\/","name":"Effectuer un tri en Python - Mathweb.fr","isPartOf":{"@id":"https:\/\/www.mathweb.fr\/euclide\/#website"},"primaryImageOfPage":{"@id":"https:\/\/www.mathweb.fr\/euclide\/effectuer-un-tri-en-python\/#primaryimage"},"image":{"@id":"https:\/\/www.mathweb.fr\/euclide\/effectuer-un-tri-en-python\/#primaryimage"},"thumbnailUrl":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2022\/02\/triBulles.png","datePublished":"2022-02-22T17:31:41+00:00","dateModified":"2023-10-10T08:40:16+00:00","description":"Nous allons voir comment \u00e9crire des fonctions de tri en Python: tri na\u00eff, tri \u00e0 bulles, tri en place, tri fusion, etc.","breadcrumb":{"@id":"https:\/\/www.mathweb.fr\/euclide\/effectuer-un-tri-en-python\/#breadcrumb"},"inLanguage":"fr-FR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.mathweb.fr\/euclide\/effectuer-un-tri-en-python\/"]}]},{"@type":"ImageObject","inLanguage":"fr-FR","@id":"https:\/\/www.mathweb.fr\/euclide\/effectuer-un-tri-en-python\/#primaryimage","url":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2022\/02\/triBulles.png","contentUrl":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2022\/02\/triBulles.png","width":343,"height":74},{"@type":"BreadcrumbList","@id":"https:\/\/www.mathweb.fr\/euclide\/effectuer-un-tri-en-python\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Accueil","item":"https:\/\/www.mathweb.fr\/euclide\/"},{"@type":"ListItem","position":2,"name":"Effectuer un tri en Python"}]},{"@type":"WebSite","@id":"https:\/\/www.mathweb.fr\/euclide\/#website","url":"https:\/\/www.mathweb.fr\/euclide\/","name":"Mathweb.fr","description":"Math\u00e9matiques, LaTeX et Python","publisher":{"@id":"https:\/\/www.mathweb.fr\/euclide\/#\/schema\/person\/e4d3bb07968238378f0d5052a70dcd69"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.mathweb.fr\/euclide\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"fr-FR"},{"@type":["Person","Organization"],"@id":"https:\/\/www.mathweb.fr\/euclide\/#\/schema\/person\/e4d3bb07968238378f0d5052a70dcd69","name":"St\u00e9phane Pasquet","image":{"@type":"ImageObject","inLanguage":"fr-FR","@id":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2025\/06\/cropped-logo-mathweb.webp","url":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2025\/06\/cropped-logo-mathweb.webp","contentUrl":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2025\/06\/cropped-logo-mathweb.webp","width":74,"height":77,"caption":"St\u00e9phane Pasquet"},"logo":{"@id":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2025\/06\/cropped-logo-mathweb.webp"}}]}},"_links":{"self":[{"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/pages\/7335","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/comments?post=7335"}],"version-history":[{"count":0,"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/pages\/7335\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/media?parent=7335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}