{"id":16466,"date":"2022-08-18T18:03:24","date_gmt":"2022-08-18T17:03:24","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=16466"},"modified":"2024-02-11T15:59:01","modified_gmt":"2024-02-11T14:59:01","slug":"exercices-algorithmes-de-tris","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/algorithmic\/exercises-corrected-sorting-algorithms\/","title":{"rendered":"6 Corrected exercises sorting algorithms"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"16466\" class=\"elementor elementor-16466\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-58ddab7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"58ddab7\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-0119e2d\" data-id=\"0119e2d\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a74431f elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"a74431f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/algorithmique\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Algorithmique<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-d580580\" data-id=\"d580580\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-01b71b5 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"01b71b5\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Page d'accueil<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-792d783\" data-id=\"792d783\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a48bd3b elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"a48bd3b\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Algorithm\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e42fcdf elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e42fcdf\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b8018fc\" data-id=\"b8018fc\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-cf98219 elementor-widget elementor-widget-heading\" data-id=\"cf98219\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenus<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/exercises-corrected-sorting-algorithms\/#Exercices-corriges-sur-les-algorithmes-de-tri\" >Exercices corrig\u00e9s sur les algorithmes de tri<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/exercises-corrected-sorting-algorithms\/#Les-tris-iteratifs-tri-par-selection\" >Les tris it\u00e9ratifs : tri par s\u00e9lection<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/exercises-corrected-sorting-algorithms\/#Les-tris-iteratifs-tri-par-insertion\" >Les tris it\u00e9ratifs : tri par insertion<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/exercises-corrected-sorting-algorithms\/#Les-tris-iteratifs-tri-a-bulles\" >Les tris it\u00e9ratifs : tri \u00e0 bulles<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/exercises-corrected-sorting-algorithms\/#Les-tris-iteratifs-tri-cocktail\" >Les tris it\u00e9ratifs : tri cocktail<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/exercises-corrected-sorting-algorithms\/#Les-tris-recursifs-tri-rapide\" >Les tris r\u00e9cursifs : tri rapide<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/exercises-corrected-sorting-algorithms\/#Les-tris-recursifs-tri-fusion\" >Les tris r\u00e9cursifs : tri fusion<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercices-corriges-sur-les-algorithmes-de-tri\"><\/span>Exercices corrig\u00e9s sur les algorithmes de tri<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6524a90 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6524a90\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-281f6ac\" data-id=\"281f6ac\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-48465c7 elementor-widget elementor-widget-text-editor\" data-id=\"48465c7\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Les exercices corrig\u00e9s suivants concernent les algorithmes de tri : Tri par s\u00e9lection, tri par insertion, tri \u00e0 bulles, tri cocktail, tri rapide et tri fusion.<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-11096 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/cropped-Capture.png\" alt=\"algorithmes de tri\" width=\"97\" height=\"97\" title=\"\"><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-92b0452 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"92b0452\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0115a5f\" data-id=\"0115a5f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5912535 elementor-widget elementor-widget-heading\" data-id=\"5912535\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Les-tris-iteratifs-tri-par-selection\"><\/span>Les tris it\u00e9ratifs : tri par s\u00e9lection<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e72c9dd elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e72c9dd\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-57c53bc\" data-id=\"57c53bc\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ecbe7f9 elementor-widget elementor-widget-text-editor\" data-id=\"ecbe7f9\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Sur un tableau de n \u00e9l\u00e9ments (num\u00e9rot\u00e9s de 0 \u00e0 n-1), le principe du tri par s\u00e9lection est le suivant :<\/p><ul><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">rechercher le plus petit \u00e9l\u00e9ment du tableau, et l&rsquo;\u00e9changer avec l&rsquo;\u00e9l\u00e9ment d&rsquo;indice 0 ;<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">rechercher le second plus petit \u00e9l\u00e9ment du tableau, et l&rsquo;\u00e9changer avec l&rsquo;\u00e9l\u00e9ment d&rsquo;indice 1 ;<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">continuer de cette fa\u00e7on jusqu&rsquo;\u00e0 ce que le tableau soit enti\u00e8rement tri\u00e9.<\/span><\/li><\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-fd28bb8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"fd28bb8\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-e1ecdf9\" data-id=\"e1ecdf9\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-6dfcdc6 elementor-widget elementor-widget-toggle\" data-id=\"6dfcdc6\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1151\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1151\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1151\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1151\"><p><span style=\"font-weight: 400;\">En pseudo-code, l&rsquo;algorithme s&rsquo;\u00e9crit ainsi :<\/span><\/p><p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone size-medium wp-image-16477\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo22-247x300.png\" alt=\"\" width=\"247\" height=\"300\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo22-247x300.png 247w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo22-10x12.png 10w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo22.png 302w\" sizes=\"(max-width: 247px) 100vw, 247px\" \/><\/p><p><span style=\"font-weight: 400;\">Dans tous les cas, pour trier <\/span><i><span style=\"font-weight: 400;\">n<\/span><\/i><span style=\"font-weight: 400;\"> \u00e9l\u00e9ments, le tri par s\u00e9lection effectue n(n-1)\/2 comparaisons donc en O(n\u00b2).<\/span><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-82293b5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"82293b5\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-bcd22d5\" data-id=\"bcd22d5\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ab45d5c elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"ab45d5c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-0961813 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0961813\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-4b59c73\" data-id=\"4b59c73\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ba339be elementor-widget elementor-widget-heading\" data-id=\"ba339be\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Les-tris-iteratifs-tri-par-insertion\"><\/span>Les tris it\u00e9ratifs : tri par insertion<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f4ee8d5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f4ee8d5\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b0d6756\" data-id=\"b0d6756\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5961737 elementor-widget elementor-widget-text-editor\" data-id=\"5961737\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Le tri par insertion est un <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithme<\/a> de tri classique. La plupart des personnes l&rsquo;utilisent naturellement pour trier des cartes \u00e0 jouer.<\/p><p>Le tri par insertion consid\u00e8re chaque \u00e9l\u00e9ment du tableau et l&rsquo;ins\u00e8re \u00e0 la bonne place parmi les \u00e9l\u00e9ments d\u00e9j\u00e0 tri\u00e9s. Ainsi, au moment o\u00f9 on consid\u00e8re un \u00e9l\u00e9ment, les \u00e9l\u00e9ments qui le pr\u00e9c\u00e8dent sont d\u00e9j\u00e0 tri\u00e9s, tandis que les \u00e9l\u00e9ments qui le suivent ne sont pas encore tri\u00e9s.<\/p><p>Pour trouver la place o\u00f9 ins\u00e9rer un \u00e9l\u00e9ment parmi les pr\u00e9c\u00e9dents, il faut le comparer \u00e0 ces derniers, et les d\u00e9caler afin de lib\u00e9rer une place o\u00f9 effectuer l&rsquo;insertion. Le d\u00e9calage occupe la place laiss\u00e9e libre par l&rsquo;\u00e9l\u00e9ment consid\u00e9r\u00e9. En pratique, ces deux actions s&rsquo;effectuent en une passe, qui consiste \u00e0 faire \u00ab remonter \u00bb l&rsquo;\u00e9l\u00e9ment au fur et \u00e0 mesure jusqu&rsquo;\u00e0 rencontrer un \u00e9l\u00e9ment plus petit.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4fa9505 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4fa9505\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-16521cc\" data-id=\"16521cc\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a8bd276 elementor-widget elementor-widget-toggle\" data-id=\"a8bd276\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1761\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1761\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1761\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1761\"><p><span style=\"font-weight: 400;\">Voici un exemple pour mieux comprendre le principe sur le tableau [6, 5, 3, 1, 8, 7, 2, 4].<\/span><\/p><p><img decoding=\"async\" class=\"alignnone wp-image-16478 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo23.png\" alt=\"algorithme tri par insertion\" width=\"597\" height=\"294\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo23.png 597w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo23-300x148.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo23-18x9.png 18w\" sizes=\"(max-width: 597px) 100vw, 597px\" \/><\/p><p><span style=\"font-weight: 400;\">Voici son pseudo-code :<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16479 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo24.png\" alt=\"algorithme tri par insertion\" width=\"726\" height=\"395\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo24.png 726w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo24-300x163.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo24-18x10.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo24-600x326.png 600w\" sizes=\"(max-width: 726px) 100vw, 726px\" \/><\/p><p><span style=\"font-weight: 400;\">La complexit\u00e9 du tri par insertion est O(n\u00b2) dans le pire cas et lin\u00e9aire dans le meilleur cas. Dans le pire cas, atteint lorsque le tableau est tri\u00e9 \u00e0 l&rsquo;envers, l&rsquo;algorithme effectue de l&rsquo;ordre de n\u00b2\/2 affectations et comparaisons ; Si le tableau est d\u00e9j\u00e0 tri\u00e9, il y a n-1 comparaisons et au plus n affectations.<\/span><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2c57326 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2c57326\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-cbf2de6\" data-id=\"cbf2de6\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-529f1c6 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"529f1c6\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7d3f0db elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7d3f0db\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-fd14393\" data-id=\"fd14393\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c358bd4 elementor-widget elementor-widget-heading\" data-id=\"c358bd4\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Les-tris-iteratifs-tri-a-bulles\"><\/span>Les tris it\u00e9ratifs : tri \u00e0 bulles<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-62802de elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"62802de\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-af9d9be\" data-id=\"af9d9be\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-05f2e69 elementor-widget elementor-widget-text-editor\" data-id=\"05f2e69\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Le tri \u00e0 bulles ou tri par propagation est un algorithme de tri. Il consiste \u00e0 comparer r\u00e9p\u00e9titivement les \u00e9l\u00e9ments cons\u00e9cutifs d&rsquo;un tableau, et \u00e0 les permuter lorsqu&rsquo;ils sont mal tri\u00e9s. Il doit son nom au fait qu&rsquo;il d\u00e9place rapidement les plus grands \u00e9l\u00e9ments en fin de tableau, comme des bulles d&rsquo;air qui remonteraient rapidement \u00e0 la surface d&rsquo;un liquide.<\/p><p><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">L&rsquo;algorithme parcourt le tableau et compare les \u00e9l\u00e9ments cons\u00e9cutifs. Lorsque deux \u00e9l\u00e9ments cons\u00e9cutifs ne sont pas dans l&rsquo;ordre, ils sont permut\u00e9s.<\/span><\/p><p><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">Apr\u00e8s un premier parcours complet du tableau, le plus grand \u00e9l\u00e9ment est forc\u00e9ment en fin de tableau, \u00e0 sa position d\u00e9finitive. En effet, aussit\u00f4t que le plus grand \u00e9l\u00e9ment est rencontr\u00e9 durant le parcours, il est mal tri\u00e9 par rapport \u00e0 tous les \u00e9l\u00e9ments suivants, donc permut\u00e9 avec le suivant jusqu&rsquo;\u00e0 arriver \u00e0 la fin du parcours.<\/span><\/p><p><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">Apr\u00e8s le premier parcours, le plus grand \u00e9l\u00e9ment \u00e9tant \u00e0 sa position d\u00e9finitive, il n&rsquo;a plus \u00e0 \u00eatre trait\u00e9. Le reste du tableau est en revanche encore en d\u00e9sordre. Il faut donc le parcourir \u00e0 nouveau, en s&rsquo;arr\u00eatant \u00e0 l&rsquo;avant-dernier \u00e9l\u00e9ment. Apr\u00e8s ce deuxi\u00e8me parcours, les deux plus grands \u00e9l\u00e9ments sont \u00e0 leur position d\u00e9finitive. Il faut donc r\u00e9p\u00e9ter les parcours du tableau, jusqu&rsquo;\u00e0 ce que les deux plus petits \u00e9l\u00e9ments soient plac\u00e9s \u00e0 leur position d\u00e9finitive.<\/span><\/p><p>Une optimisation courante de ce tri consiste \u00e0 l&rsquo;interrompre d\u00e8s qu&rsquo;un parcours des \u00e9l\u00e9ments possiblement encore en d\u00e9sordre (boucle interne) est effectu\u00e9 sans permutation. En effet, cela signifie que tout le tableau est tri\u00e9. Cette optimisation n\u00e9cessite une variable suppl\u00e9mentaire.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-82b91c8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"82b91c8\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-ad3937d\" data-id=\"ad3937d\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f445cae elementor-widget elementor-widget-toggle\" data-id=\"f445cae\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2561\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2561\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2561\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2561\"><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16480 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo25.png\" alt=\"algorithme tri \u00e0 bulles\" width=\"364\" height=\"300\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo25.png 364w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo25-300x247.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo25-15x12.png 15w\" sizes=\"(max-width: 364px) 100vw, 364px\" \/><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16481 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo26.png\" alt=\"algorithme tri \u00e0 bulles\" width=\"375\" height=\"433\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo26.png 375w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo26-260x300.png 260w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo26-10x12.png 10w\" sizes=\"(max-width: 375px) 100vw, 375px\" \/><\/p><p><span style=\"font-weight: 400;\">Il est possible de mettre un Tant que \u00e0 la place du premier Pour. Dans ce cas il faut incr\u00e9ment\u00e9 i dans l\u2019int\u00e9rieur de la boucle et plus besoin du break..<\/span><\/p><p><span style=\"font-weight: 400;\">Pour le tri non optimis\u00e9, la complexit\u00e9 en temps est de O(n\u00b2), avec n la taille du tableau.<\/span><\/p><p><span style=\"font-weight: 400;\">Pour le tri optimis\u00e9, le nombre d&rsquo;it\u00e9rations de la boucle externe est compris entre 1 et n. En effet, on peut d\u00e9montrer qu&rsquo;apr\u00e8s la i-\u00e8me \u00e9tape, les i derniers \u00e9l\u00e9ments du tableau sont \u00e0 leur place. \u00c0 chaque it\u00e9ration, il y a exactement n-1 comparaisons et au plus n-1 permutations.<\/span><\/p><p><span style=\"font-weight: 400;\">Le pire cas (n it\u00e9rations) est atteint lorsque le plus petit \u00e9l\u00e9ment est \u00e0 la fin du tableau. La complexit\u00e9 est alors O(n\u00b2). Le meilleur cas (une seule it\u00e9ration) est atteint quand le tableau est d\u00e9j\u00e0 tri\u00e9. Dans ce cas, la complexit\u00e9 est lin\u00e9aire.<\/span><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7c78b15 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7c78b15\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-24e5c37\" data-id=\"24e5c37\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1c640e3 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"1c640e3\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b50d94e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b50d94e\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7c443e2\" data-id=\"7c443e2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-05fc108 elementor-widget elementor-widget-heading\" data-id=\"05fc108\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Les-tris-iteratifs-tri-cocktail\"><\/span>Les tris it\u00e9ratifs : tri cocktail<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6f78d23 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6f78d23\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b91fd34\" data-id=\"b91fd34\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a453b21 elementor-widget elementor-widget-text-editor\" data-id=\"a453b21\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Le tri cocktail ou tri shaker ou tri \u00e0 bulles bidirectionnel est une variante du tri \u00e0 bulles1 qui est \u00e0 la fois un algorithme de tri et un tri par comparaison. La diff\u00e9rence entre cet algorithme et le tri \u00e0 bulles est qu&rsquo;il ex\u00e9cute un tri dans chaque direction \u00e0 chaque passe le long de la liste \u00e0 trier.<\/p><p>Cet algorithme de tri n&rsquo;est que l\u00e9g\u00e8rement plus difficile \u00e0 comprendre et \u00e0 mettre en \u0153uvre que le tri \u00e0 bulles, et il r\u00e9sout en partie le probl\u00e8me des tortues du tri \u00e0 bulles (les tortues sont les petits \u00e9l\u00e9ments situ\u00e9s pr\u00e8s de la fin de la liste d&rsquo;origine, qui ne remontent que tr\u00e8s lentement, un emplacement par it\u00e9ration, vers leur emplacement d\u00e9finitif).<\/p><p>Lors de la premi\u00e8re passe, le premier parcours vers la droite d\u00e9place des \u00e9l\u00e9ments plus grands que leur voisin imm\u00e9diat vers la droite, et, en particulier, va d\u00e9placer de proche en proche le plus grand \u00e9l\u00e9ment de la liste \u00e0 son emplacement d\u00e9finitif en fin de liste. Ensuite, le second parcours vers la gauche va d\u00e9placer les \u00e9l\u00e9ments plus petits que leur voisin imm\u00e9diat vers la gauche, et, en particulier, d\u00e9placera l&rsquo;\u00e9l\u00e9ment le plus petit de la liste \u00e0 son emplacement d\u00e9finitif en t\u00eate de liste. vers la gauche. De m\u00eame, lors de la seconde passe, le second \u00e9l\u00e9ment le plus grand et le second \u00e9l\u00e9ment le plus petit rejoindront \u00e0 leur tour leur emplacement d\u00e9finitif, et ainsi de suite.<\/p><p>Apr\u00e8s i passes, les i premiers \u00e9l\u00e9ments et les i derniers \u00e9l\u00e9ments sont \u00e0 leur emplacement d\u00e9finitif. Ils n&rsquo;ont donc plus besoin d&rsquo;\u00eatre v\u00e9rifi\u00e9s. Il est donc possible d&rsquo;optimiser cet algorithme en ne v\u00e9rifiant \u00e0 chaque passe que la partie centrale de la liste non encore tri\u00e9e d\u00e9finitivement. Ceci permet de r\u00e9duire de moiti\u00e9 le nombre de comparaisons \u00e0 effectuer.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4c58539 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4c58539\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-bdf6ffa\" data-id=\"bdf6ffa\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-12e10af elementor-widget elementor-widget-toggle\" data-id=\"12e10af\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1971\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1971\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1971\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1971\"><p><span style=\"font-weight: 400;\">Un d\u00e9riv\u00e9 du tri \u00e0 bulles est le tri cocktail ou tri shaker. Cette m\u00e9thode de tri est bas\u00e9e sur l&rsquo;observation suivante : dans le tri \u00e0 bulles, les \u00e9l\u00e9ments peuvent avancer rapidement vers la fin du tableau, mais ne sont d\u00e9plac\u00e9s vers le d\u00e9but du tableau que d&rsquo;une position \u00e0 la fois.<\/span><\/p><p><span style=\"font-weight: 400;\">L&rsquo;id\u00e9e du tri cocktail consiste \u00e0 alterner le sens du parcours. On obtient un tri un peu plus rapide, d&rsquo;une part parce qu&rsquo;il n\u00e9cessite moins de comparaisons, d&rsquo;autre part parce qu&rsquo;il relit les donn\u00e9es les plus r\u00e9centes lors du changement de sens (elles sont donc encore dans la m\u00e9moire cache). Cependant, le nombre de permutations \u00e0 effectuer est identique. Ainsi, le temps d&rsquo;ex\u00e9cution est toujours proportionnel \u00e0 n\u00b2 donc m\u00e9diocre.<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16482 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo27.png\" alt=\"algorithme tri cocktail\" width=\"427\" height=\"564\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo27.png 427w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo27-227x300.png 227w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo27-9x12.png 9w\" sizes=\"(max-width: 427px) 100vw, 427px\" \/><\/p><p><span style=\"font-weight: 400;\">La complexit\u00e9 au pire et au mieux en O(.) est la m\u00eame que le tri \u00e0 bulle.<\/span><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6a5b981 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6a5b981\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-edca764\" data-id=\"edca764\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-83fdaad elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"83fdaad\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6889a9d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6889a9d\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-072448d\" data-id=\"072448d\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-06a4531 elementor-widget elementor-widget-heading\" data-id=\"06a4531\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Les-tris-recursifs-tri-rapide\"><\/span>Les tris r\u00e9cursifs : tri rapide<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-891edd8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"891edd8\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-45d5790\" data-id=\"45d5790\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1bfa438 elementor-widget elementor-widget-text-editor\" data-id=\"1bfa438\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">Le tri rapide (quicksort en anglais) est un algorithme de tri par comparaison, son fonctionnement est plut\u00f4t simple \u00e0 comprendre et il est tr\u00e8s utilis\u00e9 sur de grandes entr\u00e9es. En effet, il a pour complexit\u00e9 moyenne O(NlogN) et O(N\u00b2) dans le pire des cas.\u00a0<\/span><\/p><p><span style=\"font-weight: 400;\">Le tri rapide utilise le principe de diviser pour r\u00e9gner, c\u2019est-\u00e0-dire que l\u2019on va choisir un \u00e9l\u00e9ment du tableau (qu\u2019on appelle pivot), puis l\u2019on r\u00e9organise le tableau initial en deux sous tableaux :<\/span><\/p><ul><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">L\u2019un contenant les \u00e9l\u00e9ments inf\u00e9rieurs au pivot.<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">L\u2019autre contenant les \u00e9l\u00e9ments sup\u00e9rieurs au pivot.<\/span><\/li><\/ul><p><span style=\"font-weight: 400;\">On continue ce proc\u00e9d\u00e9 (qu&rsquo;on appelle partitionnement, c&rsquo;est-\u00e0-dire choisir un pivot et r\u00e9organiser le tableau) jusqu\u2019\u00e0 se retrouver avec un tableau d\u00e9coup\u00e9 en N sous tableaux (N \u00e9tant la taille du tableau), qui est donc tri\u00e9.<\/span><\/p><p><span style=\"font-weight: 400;\">Prenons 5, 9, 7, 3, 8 comme suite de nombres, et trions la dans l&rsquo;ordre croissant avec l&rsquo;algorithme du tri rapide :<\/span><\/p><p><span style=\"font-weight: 400;\">5, 9, <\/span><b>7<\/b><span style=\"font-weight: 400;\">, 3, 8 -&gt; on choisit le pivot, dans notre cas je choisis l&rsquo;\u00e9l\u00e9ment du milieu, 7.<\/span><\/p><p><span style=\"font-weight: 400;\">5, 3 | <\/span><b>7<\/b><span style=\"font-weight: 400;\"> | 9, 8 -&gt; on d\u00e9coupe le tableau en trois parties, une partie avec des \u00e9l\u00e9ments inf\u00e9rieurs au pivot (5 et 3), la partie contenant le pivot (7), et une partie avec les \u00e9l\u00e9ments sup\u00e9rieurs au pivot (9 et 8). On peut d\u00e9j\u00e0 dire qu&rsquo;on a plac\u00e9 le pivot \u00e0 sa place d\u00e9finitive dans le tableau, puisque les autres \u00e9l\u00e9ments sont soit sup\u00e9rieurs soit inf\u00e9rieurs \u00e0 lui.<\/span><\/p><p><b>5<\/b><span style=\"font-weight: 400;\">, 3 | 7 | <\/span><b>9<\/b><span style=\"font-weight: 400;\">, 8 -&gt; on recommence en choisissant de nouveau un pivot pour chaque sous tableaux cr\u00e9\u00e9s.<\/span><\/p><p><span style=\"font-weight: 400;\">3 | <\/span><b>5<\/b><span style=\"font-weight: 400;\"> | 7 | 8 | <\/span><b>9<\/b><span style=\"font-weight: 400;\"> -&gt; derni\u00e8re \u00e9tape du partitionnement, d\u00e9sormais aucuns sous tableaux ne contient plus d&rsquo;un \u00e9l\u00e9ment, le tri est donc termin\u00e9.<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16474 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo19.png\" alt=\"algorithme tri rapide\" width=\"197\" height=\"267\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo19.png 197w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo19-9x12.png 9w\" sizes=\"(max-width: 197px) 100vw, 197px\" \/><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-c3c4d0d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c3c4d0d\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-db51435\" data-id=\"db51435\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-839a229 elementor-widget elementor-widget-toggle\" data-id=\"839a229\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1371\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1371\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1371\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1371\"><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-18332 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/quicksort.png\" alt=\"quicksort\" width=\"710\" height=\"477\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/quicksort.png 710w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/quicksort-300x202.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/quicksort-18x12.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/quicksort-600x403.png 600w\" sizes=\"(max-width: 710px) 100vw, 710px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-497d896 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"497d896\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d8d8abe\" data-id=\"d8d8abe\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-066cd40 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"066cd40\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-58e6ff4 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"58e6ff4\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-3212632\" data-id=\"3212632\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2e06005 elementor-widget elementor-widget-heading\" data-id=\"2e06005\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Les-tris-recursifs-tri-fusion\"><\/span>Les tris r\u00e9cursifs : tri fusion<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-0ad6faa elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0ad6faa\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-ba8d598\" data-id=\"ba8d598\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-3904174 elementor-widget elementor-widget-text-editor\" data-id=\"3904174\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">Le tri par fusion est l&rsquo;un des algorithmes de tri les plus populaires et les plus efficaces. Et il est bas\u00e9 sur le paradigme Diviser pour r\u00e9gner.<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16475 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo20.png\" alt=\"algorithme tri fusion\" width=\"763\" height=\"462\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo20.png 763w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo20-300x182.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo20-18x12.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo20-600x363.png 600w\" sizes=\"(max-width: 763px) 100vw, 763px\" \/><\/p><p><span style=\"font-weight: 400;\">Supposons que nous devions trier un tableau T. Un sous-probl\u00e8me serait de trier une sous-section (sous-tableau) de ce tableau commen\u00e7ant \u00e0 l&rsquo;indice debut et se terminant \u00e0 l&rsquo;indice fin, not\u00e9e T[debut..fin].<\/span><\/p><p><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-size: 1.125rem;\">Si milieu est le point milieu entre debut et fin, alors nous pouvons diviser le sous-tableau T[debut..fin] en deux tableaux T[debut..milieu] et T[milieu + 1, fin]. Dans l&rsquo;\u00e9tape R\u00e9gner, nous essayons de trier les sous-r\u00e9seaux T[debut..milieu] et T[milieu + 1, fin]. Si nous n&rsquo;avons pas encore atteint le cas de base (le sous-tableau contient un seul \u00e9l\u00e9ment), nous divisons \u00e0 nouveau ces deux sous-r\u00e9seaux et essayons de les trier.<\/span><\/p><p><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-size: 1.125rem;\">Lorsque l&rsquo;\u00e9tape de conqu\u00eate atteint l&rsquo;\u00e9tape de base et que nous obtenons deux sous-tableaux tri\u00e9s T[debut..milieu] et T[milieu + 1, fin] pour le tableau T[debut..milieu], nous combinons les r\u00e9sultats en cr\u00e9ant un tableau tri\u00e9 T[debut..milieu] \u00e0 partir de deux sous-r\u00e9seaux tri\u00e9s T[debut..milieu] et T[milieu + 1, fin].<\/span><\/p><p><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-size: 1.125rem;\">La fonction triFusion divise \u00e0 plusieurs reprises le tableau en deux moiti\u00e9s (deux sous-tableaux) jusqu&rsquo;\u00e0 ce que nous atteignions un stade o\u00f9 nous essayons d&rsquo;effectuer triFusion sur un sous-tableau de taille 1, c&rsquo;est-\u00e0-dire debut == fin.<\/span><\/p><p><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-size: 1.125rem;\">Apr\u00e8s cela, la fonction de fusion entre en jeu et combine les tableaux tri\u00e9s dans un tableau plus grand jusqu&rsquo;\u00e0 ce que l&rsquo;ensemble du tableau soit fusionn\u00e9. Apr\u00e8s cela, la fonction de fusion r\u00e9cup\u00e8re les sous-tableaux tri\u00e9s et les fusionne pour trier progressivement l&rsquo;ensemble du tableau.<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16476 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo21.png\" alt=\"algorithme tri fusion\" width=\"747\" height=\"492\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo21.png 747w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo21-300x198.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo21-18x12.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo21-600x395.png 600w\" sizes=\"(max-width: 747px) 100vw, 747px\" \/><\/p><p><span style=\"font-weight: 400;\">La complexit\u00e9 temporelle du tri par fusion est O(nLogn) dans les 3 cas (pire, moyen et meilleur) car le tri par fusion divise toujours le tableau en deux moiti\u00e9s et prend un temps lin\u00e9aire pour fusionner deux moiti\u00e9s.<\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f4efd40 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f4efd40\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0e7e1e6\" data-id=\"0e7e1e6\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0aad07a elementor-widget elementor-widget-toggle\" data-id=\"0aad07a\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1111\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1111\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1111\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1111\"><p><span style=\"font-weight: 400;\">Ce pseudo-code est tr\u00e8s simplifi\u00e9 :<\/span><\/p><ul><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">Dans la fonction triFusion, on utilise la r\u00e9cursivit\u00e9 pour d\u00e9couper puis fusionner notre tableau, et on arr\u00eate les appels r\u00e9cursifs lorsque le sous tableau que l&rsquo;on traite n&rsquo;a plus qu&rsquo;un seul \u00e9l\u00e9ment.<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">La fonction fusionner est assez explicite, elle nous permet de cr\u00e9er \u00e0 partir de deux sous tableaux tri\u00e9s, un tableau lui aussi tri\u00e9 en temps lin\u00e9aire.<\/span><\/li><\/ul><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16485 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo30.png\" alt=\"algorithme tri fusion\" width=\"374\" height=\"629\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo30.png 374w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo30-178x300.png 178w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo30-7x12.png 7w\" sizes=\"(max-width: 374px) 100vw, 374px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Algorithmics Wiki home page Corrected exercises on sorting algorithms The following corrected exercises relate to sorting algorithms: Sort by selection, sort \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":1062,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-16466","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/16466","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=16466"}],"version-history":[{"count":9,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/16466\/revisions"}],"predecessor-version":[{"id":20246,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/16466\/revisions\/20246"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1062"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=16466"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}