{"id":190078,"date":"2021-08-17T09:11:10","date_gmt":"2021-08-17T07:11:10","guid":{"rendered":"https:\/\/sherpas.com\/blog\/algorithmes-de-tri\/"},"modified":"2023-09-12T12:24:19","modified_gmt":"2023-09-12T10:24:19","slug":"algorithmes-de-tri","status":"publish","type":"post","link":"https:\/\/sherpas.com\/blog\/algorithmes-de-tri\/","title":{"rendered":"[NSI] Les algorithmes de tri \ud83d\udcbb"},"content":{"rendered":"\n

L\u2019\u00e9tude des algorithmes de tri est un passage oblig\u00e9 pour tous les \u00e9tudiants en informatique.<\/strong> Tu n’as pas bien compris ce cours et tu cherches des comparaisons entre les diff\u00e9rents algorithmes de tri ? Tu souhaites mieux comprendre la notion de complexit\u00e9 ? \ud83d\udcc2<\/p>\n\n\n\n

Pas de souci, les Sherpas t\u2019expliquent tout ce que tu dois conna\u00eetre sur ce sujet afin de r\u00e9ussir ton prochain contr\u00f4le.<\/strong> Let\u2019s go ! \u2728<\/p>\n\n\n\n

Comprendre les algorithmes de tri en informatique \u2328\ufe0f<\/h2>\n\n\n\n

Qu\u2019est-ce qu\u2019un algorithme de tri ?<\/h3>\n\n\n\n

\ud83d\udc49 Un algorithme de tri<\/a> est une suite finie d\u2019op\u00e9rations permettant d\u2019organiser des \u00e9l\u00e9ments dans un ordre d\u00e9termin\u00e9 pr\u00e9alablement.<\/strong> Le plus souvent, les informaticiens trient des tableaux d\u2019entiers du plus petit au plus grand.<\/p>\n\n\n\n

Les algorithmes de tri ont de nombreuses utilit\u00e9s et leur \u00e9tude est un sujet majeur de recherche en informatique.<\/p>\n\n\n\n

\ud83d\udc49 En cours de NSI, les algorithmes de tri permettent \u00e0 tes professeurs de v\u00e9rifier ta compr\u00e9hension des concepts de terminaison d\u2019algorithme et d\u2019invariants de boucle.<\/strong><\/p>\n\n\n\n

En effet, lorsque l\u2019on utilise une boucle (while et for), il faut faire attention \u00e0 la terminaison de celle-ci. Sinon, la boucle est infinie et le programme ne s\u2019arr\u00eatera pas. L’oubli le plus fr\u00e9quent est li\u00e9 au compteur qu\u2019il faut incr\u00e9menter en fin de boucle.<\/p>\n\n\n\n

Le terme \u201cinvariants de boucle\u201d d\u00e9signe une propri\u00e9t\u00e9 qui est vraie pour tous les passages de la boucle, y compris avant d\u2019y entrer et d\u2019en sortir.<\/p>\n\n\n\n

Tu cherches quelqu\u2019un pouvant t\u2019aider en NSI ?<\/strong> Retrouve nos cours particuliers d\u2019informatique<\/a>.<\/strong> Le premier cours est offert et te permettra de savoir si un Sherpa peut t\u2019aider \u00e0 progresser ! \ud83d\ude09<\/p>\n\n\n\n

La complexit\u00e9 d\u2019un algorithme \ud83d\ude23<\/h3>\n\n\n\n

Plusieurs strat\u00e9gies existent pour trier des tableaux. On peut d\u00e9terminer leur efficacit\u00e9 gr\u00e2ce au calcul de la complexit\u00e9. Cela correspond \u00e0 la quantit\u00e9 de ressources n\u00e9cessaires \u00e0 l’ex\u00e9cution du programme. \ud83d\udd27<\/strong><\/p>\n\n\n\n

\ud83d\udc49 La complexit\u00e9 d\u2019un algorithme se note g\u00e9n\u00e9ralement par une fonction d\u00e9pendant du nombre de valeurs pr\u00e9sentes dans celui-ci. On parle ainsi de complexit\u00e9 : <\/strong><\/p>\n\n\n\n

    \n
  • constante<\/strong>, O(1), si le temps de calcul est toujours le m\u00eame, quel que soit le nombre d\u2019\u00e9l\u00e9ments<\/li>\n\n\n\n
  • logarithmique<\/strong>, O(log n), si le temps de calcul est proportionnel au logarithme du nombre d\u2019\u00e9l\u00e9ments<\/li>\n\n\n\n
  • lin\u00e9aire<\/strong>, O(n), si le temps de calcul est proportionnel au nombre d\u2019\u00e9l\u00e9ments<\/li>\n\n\n\n
  • lin\u00e9arithmique<\/strong>, O(n log n), si le temps de calcul est proportionnel au nombre d\u2019\u00e9l\u00e9ments multipli\u00e9 par le logarithme du nombre d\u2019\u00e9l\u00e9ments.<\/li>\n\n\n\n
  • quadratique<\/strong>, O(n\u00b2), si le temps de calcul et proportionnel au carr\u00e9 du nombre d\u2019\u00e9l\u00e9ments<\/li>\n\n\n\n
  • exponentielle<\/strong>, O(2^n), si le temps de calcul est proportionnel \u00e0 2 exposant le nombre d’\u00e9l\u00e9ments<\/li>\n<\/ul>\n\n\n
    \n
    \"algorithmes<\/figure><\/div>\n\n\n

    Sur un tableau de petite taille, la diff\u00e9rence de temps mis par l\u2019algorithme est quasiment invisible selon sa complexit\u00e9. Cependant, si le tableau a plusieurs millions d\u2019\u00e9l\u00e9ments, la dur\u00e9e de son tri peut varier de plusieurs jours selon l\u2019algorithme utilis\u00e9.<\/strong> Il est donc primordial de comprendre les avantages et inconv\u00e9nients des algorithmes de tri. \u23f0
    En l\u2019\u00e9tat actuel des connaissances, les meilleurs algorithmes de tri ont une complexit\u00e9 lin\u00e9arithmique (O(n log n)).<\/p>\n\n\n

    \n
    \n \n
    \n
    \n
    \n \"Logo\n <\/div>\n
    \n
    \n
    \n
    \n \n <\/div>\n

    Fabien<\/p>

    T\u00e9l\u00e9com Paris<\/p>

    \n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n <\/div>\n

    20\u20ac\/h<\/p> <\/div>\n <\/div>\n

    \n
    \n \n <\/div>\n

    Nicolas<\/p>

    CentraleSup\u00e9lec<\/p>

    \n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n <\/div>\n

    17\u20ac\/h<\/p> <\/div>\n <\/div>\n

    \n
    \n \n <\/div>\n

    Louise<\/p>

    Mines ParisTech<\/p>

    \n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n <\/div>\n

    24\u20ac\/h<\/p> <\/div>\n <\/div>\n

    \n
    \n \n <\/div>\n

    Fanny<\/p>

    Ponts ParisTech<\/p>

    \n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n <\/div>\n

    19\u20ac\/h<\/p> <\/div>\n <\/div>\n <\/div>\n <\/div>\n<\/div>\n

    \n
    \n \"Logo\n <\/div>\n

    Besoin d’un prof particulier<\/span> d’informatique ? \u2728<\/span><\/p>\n<\/div>\n

    Nos Sherpas sont l\u00e0 pour t’aider \u00e0 progresser et prendre confiance en toi !<\/p>\n<\/div>\n

    \n \n JE PRENDS UN COURS GRATUIT !\n <\/div>\n <\/div>\n <\/div>\n <\/div>\n <\/div>\n <\/section>\n\n\n\n

    Les diff\u00e9rents algorithmes de tri \u00e0 conna\u00eetre \u2699\ufe0f<\/h2>\n\n\n\n

    Le tri par s\u00e9lection \u267b<\/h3>\n\n\n\n

    \ud83d\udc49 Cet algorithme est intuitif. D\u2019abord, il cherche l\u2019\u00e9l\u00e9ment le plus petit du tableau. Puis, il \u00e9change cet \u00e9l\u00e9ment avec l\u2019\u00e9l\u00e9ment en premi\u00e8re place du tableau. Enfin, il r\u00e9it\u00e8re ces actions jusqu\u2019\u00e0 ce que le tableau soit enti\u00e8rement tri\u00e9. \ud83d\udd01<\/strong><\/p>\n\n\n\n

    Voici le pseudo-code correspondant :
    \n<\/code><\/p>\n\n\n\n

    tri_selection(Tableau T)\n      n \u2190 longueur(T) \n      pour i de 0 \u00e0 n - 2\n          min \u2190 i       \n          pour j de i + 1 \u00e0 n - 1\n              si T[j] < T[min], alors min \u2190 j\n          fin pour\n          si min \u2260 i, alors \u00e9changer T[i] et T[min]\n      fin pour\nfin tri_selection<\/pre>\n\n\n\n
    La complexit\u00e9 du tri par s\u00e9lection est en O(n\u00b2). Il n\u2019est donc pas tr\u00e8s efficace. Mais, il fait tr\u00e8s peu d\u2019\u00e9changes (au maximum, n-1). Donc, il peut \u00eatre utilis\u00e9 si les \u00e9l\u00e9ments sont co\u00fbteux \u00e0 d\u00e9placer (ce qui n\u2019est pas le cas d\u2019un tableau d\u2019entier) et peu co\u00fbteux \u00e0 comparer.<\/p>\n\n\n\n
    Le tri \u00e0 bulle \u23fa<\/h3>\n\n\n\n
    \ud83d\udc49  Cette m\u00e9thode de tri consiste \u00e0 inverser tous les couples de nombres non ordonn\u00e9s.<\/strong> Par exemple, avec les 3 \u00e9l\u00e9ments : 6|5|4 : le tri \u00e0 bulle va comparer 6 et 5, comme ils ne sont pas ordonn\u00e9s, ils vont \u00eatre invers\u00e9s (on aura 5|6|4), puis va comparer 6 et 4 et les \u00e9changer (5|4|6). \u2611\ufe0f<\/p>\n\n\n\n
    \u00c0 la fin de la premi\u00e8re boucle, le plus grand \u00e9l\u00e9ment du tableau sera forc\u00e9ment bien plac\u00e9. Puis, l\u2019algorithme recommence jusqu\u2019\u00e0 la fin du tri.<\/strong><\/p>\n\n\n\n
    Voici le pseudo-code du tri \u00e0 bulle :<\/p>\n\n\n\n
    tri_\u00e0_bulles(Tableau T)\n   pour i allant de (taille de T)-1 \u00e0 1\n       pour j allant de 0 \u00e0 i-1\n           si T[j+1] < T[j]\n               (T[j+1], T[j]) = (T[j], T[j+1])\n           fin_si\n       fin_pour\n   fin_pour\nfin_tri_\u00e0_bulles<\/pre>\n\n\n\n
    Cet algorithme a aussi une complexit\u00e9 quadratique en O(n\u00b2). Cependant, plus le tableau est pr\u00e9alablement tri\u00e9, plus il est efficace. En moyenne, il est aussi efficace que le tri par s\u00e9lection, mais dans les cas particuliers o\u00f9 le tableau est en partie ordonn\u00e9, il est plus efficace.<\/p>\n\n\n\n
    Le tri par insertion<\/h3>\n\n\n\n
    \ud83d\udc49  Cette strat\u00e9gie consiste \u00e0 placer trier \u00e9l\u00e9ment par \u00e9l\u00e9ment le tableau. D\u2019abord, l\u2019algorithme trie les 2 premi\u00e8res valeurs. Puis, il place la troisi\u00e8me \u00e0 sa place vis-\u00e0-vis des 2 premi\u00e8res. Au global, il s\u2019agit de placer la valeur i dans la partie du tableau d\u00e9j\u00e0 tri\u00e9e allant de la premi\u00e8re valeur \u00e0 la i-1\u00e8me.<\/strong><\/p>\n\n\n\n
    Voici le pseudo-code correspondant :
    \n<\/code><\/p>\n\n\n\n
    tri_insertion(Tableau T)\n       pour i de 1 \u00e0 taille(T) - 1\n            x \u2190 T[i]                            \n            j \u2190 i                               \n            tant que j > 0 et T[j - 1] > x\n                     T[j] \u2190 T[j - 1]\n                     j \u2190 j - 1\n            fin_tant_que\n            T[j] \u2190 x  \n       fin_pour\nfin_tri_insertion<\/pre>\n\n\n\n
    En moyenne, le tri par insertion a une complexit\u00e9 quadratique (O(n\u00b2)), mais si le tableau est d\u00e9j\u00e0 ordonn\u00e9, sa complexit\u00e9 est lin\u00e9aire (O(n)).<\/p>\n\n\n
    \n        
    \n            \n                                                
    \n                                                                        
    \n    
    \n        \"Logo\n    <\/div>\n    
    \n        
    \n                                            
    \n                    
    \n                        \n                    <\/div>\n                         
    Margot<\/p>                          
    Arts et M\u00e9tiers ParisTech<\/p>                                                     
    \n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                            <\/div>\n                                                 
    22\u20ac\/h\/h<\/p>                     <\/div>\n                <\/div>\n                                            
    \n                    
    \n                        \n                    <\/div>\n                         
    Bastien<\/p>                          
    Polytechnique<\/p>                                                     
    \n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                            <\/div>\n                                                 
    26\u20ac\/h<\/p>                     <\/div>\n                <\/div>\n                                            
    \n                    
    \n                        \n                    <\/div>\n                         
    Hugo<\/p>                          
    Insa Lyon<\/p>                                                     
    \n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                            <\/div>\n                                                 
    16\u20ac\/h<\/p>                     <\/div>\n                <\/div>\n                                            
    \n                    
    \n                        \n                    <\/div>\n                         
    Thibault<\/p>                          
    ENS Paris Ulm<\/p>                                                     
    \n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                            <\/div>\n                                                 
    20\u20ac\/h<\/p>                     <\/div>\n                <\/div>\n                    <\/div>\n    <\/div>\n<\/div>\n                                                    
    \n                                                            
    \n                                    \"Logo\n                                <\/div>\n                                                                                        
    Ton premier cours particulier<\/span> d’informatique est offert<\/span> ! \ud83c\udf81<\/span><\/p>\n<\/div>\n                                                                                        
    Tous nos profs sont pass\u00e9s par les meilleures \u00e9coles de France !<\/p>\n<\/div>\n                                                        
    \n                                                                                                    \n                                        J\u2019EN PROFITE !\n                                    <\/div>\n                                                            <\/div>\n                                                    <\/div>\n                                    <\/div>\n                                    <\/div>\n    <\/section>\n\n\n\n
    Le tri rapide<\/h3>\n\n\n\n
    Le tri rapide est un peu plus complexe \u00e0 comprendre, mais il a de nombreux avantages que nous d\u00e9taillerons apr\u00e8s son explication. \ud83d\udcaa<\/p>\n\n\n\n
    \ud83d\udc49  L\u2019id\u00e9e est de choisir un \u00e9l\u00e9ment au hasard dans le tableau et de s\u2019en servir comme pivot. On va placer d\u2019un c\u00f4t\u00e9 toutes les valeurs inf\u00e9rieures au pivot, et de l\u2019autre les valeurs sup\u00e9rieures \u00e0 celui-ci. Puis, il faudra r\u00e9it\u00e9rer cela pour chaque partie du tableau, jusqu\u2019\u00e0 que les partitions soient compos\u00e9es d\u2019un seul \u00e9l\u00e9ment. <\/strong><\/p>\n\n\n\n
    Voici comment on le code :<\/p>\n\n\n\n
    partitionner(tableau T, entier premier, entier dernier, entier pivot)\n    \u00e9changer T[pivot] et T[dernier] \n    j := premier\n    pour i de premier \u00e0 dernier - 1 \/\/ la boucle se termine quand i = (dernier-1).\n        si T[i] <= T[dernier] alors\n            \u00e9changer T[i] et T[j]\n            j := j + 1\n        fin_si\n    fin_pour\n    \u00e9changer T[dernier] et T[j]\n    renvoyer j\nfin_partitionner\n\ntri_rapide(tableau T, entier premier, entier dernier)\n    si premier < dernier alors\n        pivot := choix_pivot(T, premier, dernier)\n        pivot := partitionner(T, premier, dernier, pivot)\n        tri_rapide(T, premier, pivot-1)\n        tri_rapide(T, pivot+1, dernier)\n    fin_si\nfin_tri_rapide<\/pre>\n\n\n\n
    La complexit\u00e9 de cet algorithme est lin\u00e9arithmique (O(n log n)). L’espace m\u00e9moire utilis\u00e9 est aussi faible.<\/p>\n\n\n\n
    Le tri fusion<\/h3>\n\n\n\n
    \ud83d\udc49  Le tri fusion consiste \u00e0 fusionner 2 listes en les triant. Puis, recommencer cela de mani\u00e8re it\u00e9rative de mani\u00e8re \u00e0 fusionner d\u2019abord les valeurs une \u00e0 une, puis deux \u00e0 deux\u2026 \ud83d\udd00<\/strong><\/p>\n\n\n\n
    Voici son pseudo-code :<\/p>\n\n\n\n
    fonction triFusion(Tableau T)\n      si n \u2264 1\n              renvoyer T\n      sinon\n              renvoyer fusion(triFusion(T[1, \u2026, n\/2]), triFusion(T[n\/2 + 1, \u2026, n]))\n      fin_si_sinon\nfin_triFusion\n\n\nfonction fusion(Tableau A, Tableau B)\n      si A est le tableau vide\n              renvoyer B\n      si B est le tableau vide\n              renvoyer A\n      si A[1] \u2264 B[1]\n              renvoyer A[1] \u2295 fusion(A[2, \u2026, a], B)\n      sinon\n              renvoyer B[1] \u2295 fusion(A, B[2, \u2026, b])\n      fin_si_sinon\nfin_fusion<\/pre>\n\n\n\n
    Il poss\u00e8de aussi une complexit\u00e9 lin\u00e9arithmique (O(n log n)) mais il a le d\u00e9faut de n\u00e9cessiter un tableau annexe de taille n. Si la m\u00e9moire est restreinte, c\u2019est un inconv\u00e9nient.<\/p>\n\n\n\n
    Conclusion sur les algorithmes de tri \ud83d\udeae<\/h2>\n\n\n\n
    Nous avons vu que de nombreux algorithmes permettent de trier un tableau. Cependant, certains sont plus efficaces que d\u2019autres, car leur complexit\u00e9 est plus faible.<\/p>\n\n\n\n
    Sur des petits tableaux, la diff\u00e9rence est minime, mais lorsque ceux-ci poss\u00e8dent plusieurs millions d\u2019\u00e9l\u00e9ments, il devient indispensable de choisir un algorithme ayant une complexit\u00e9 minimale. \ud83e\uddd0<\/strong><\/p>\n\n\n\n
    Si tu as bien compris ce sujet, n\u2019h\u00e9site pas \u00e0 feuilleter nos autres articles sur des sujets d\u2019informatique !<\/p>\n\n\n
    \n            \n
    \n    \n
    \n            
    \n            \n\n
    <\/div>\n        <\/div>\n            
    \n            \n\n
    <\/div>\n        <\/div>\n            
    \n            \n\n
    <\/div>\n        <\/div>\n            
    \n            \n\n
    <\/div>\n        <\/div>\n            
    \n            \n\n
    <\/div>\n        <\/div>\n    <\/div>\n    \n
    \n            
    \n            \n\n
    <\/div>\n        <\/div>\n            
    \n            \n\n
    <\/div>\n        <\/div>\n            
    \n            \n\n
    <\/div>\n        <\/div>\n            
    \n            \n\n
    <\/div>\n        <\/div>\n            
    \n            \n\n
    <\/div>\n        <\/div>\n    <\/div>\n<\/div>\n                \n\n
    \n            4.2\/5 - (14 votes)    <\/div>\n    <\/div>\n","protected":false},"excerpt":{"rendered":"
    L\u2019\u00e9tude des algorithmes de tri est un passage oblig\u00e9 pour tous les \u00e9tudiants en informatique. Tu n’as pas (…)<\/p>\n","protected":false},"author":271,"featured_media":167054,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"category":[803,813],"tag":[283],"class_list":["post-190078","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-apprendre-matiere","category-informatique-nsi","tag-tech"],"acf":[],"_links":{"self":[{"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/posts\/190078","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/users\/271"}],"replies":[{"embeddable":true,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/comments?post=190078"}],"version-history":[{"count":0,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/posts\/190078\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/media\/167054"}],"wp:attachment":[{"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/media?parent=190078"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/category?post=190078"},{"taxonomy":"tag","embeddable":true,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/tag?post=190078"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}