{"id":2457,"date":"2019-12-30T10:29:17","date_gmt":"2019-12-30T07:29:17","guid":{"rendered":"http:\/\/demensdeum.com\/blog\/?p=2457"},"modified":"2024-12-16T22:32:31","modified_gmt":"2024-12-16T19:32:31","slug":"insertion-sort-merge-sort","status":"publish","type":"post","link":"https:\/\/demensdeum.com\/blog\/fr\/2019\/12\/30\/insertion-sort-merge-sort\/","title":{"rendered":"Tri par insertion, tri par fusion"},"content":{"rendered":"

Tri par insertion<\/h3>\n

Tri par insertion – chaque \u00e9l\u00e9ment<\/strong> est compar\u00e9 aux pr\u00e9c\u00e9dents<\/strong> de la liste et l’\u00e9l\u00e9ment<\/strong> est \u00e9chang\u00e9 avec le plus grand, le cas \u00e9ch\u00e9ant, sinon la boucle de comparaison interne s’arr\u00eate. \u00c9tant donn\u00e9 que les \u00e9l\u00e9ments sont tri\u00e9s du premier au dernier, chaque \u00e9l\u00e9ment est compar\u00e9 \u00e0 une liste d\u00e9j\u00e0 tri\u00e9e, ce qui *\u00e9ventuellement* r\u00e9duit le temps d’ex\u00e9cution global. La complexit\u00e9 temporelle de l’algorithme est O(n^2), c’est-\u00e0-dire identique \u00e0 la vari\u00e9t\u00e9 des bulles.<\/p>\n

Fusionner le tri<\/h3>\n

Tri par fusion – la liste est divis\u00e9e en groupes d’un \u00e9l\u00e9ment, puis les groupes sont \u00ab fusionn\u00e9s \u00bb par paires avec comparaison simultan\u00e9e. Dans mon impl\u00e9mentation, lors de la fusion de paires, les \u00e9l\u00e9ments de gauche sont compar\u00e9s aux \u00e9l\u00e9ments de droite, puis d\u00e9plac\u00e9s vers la liste r\u00e9sultante si les \u00e9l\u00e9ments de gauche ont disparu, alors tous les \u00e9l\u00e9ments de droite sont ajout\u00e9s \u00e0 la liste r\u00e9sultante\u00a0; liste (leur comparaison suppl\u00e9mentaire est inutile, puisque tous les \u00e9l\u00e9ments des groupes passent par des it\u00e9rations de tri)< br \/>Le travail de cet algorithme est tr\u00e8s simple \u00e0 parall\u00e9liser ; l’\u00e9tape de fusion des paires peut \u00eatre effectu\u00e9e en threads, en attendant la fin des it\u00e9rations dans le r\u00e9partiteur.
R\u00e9sultat de l’algorithme pour l’ex\u00e9cution monothread\u00a0:<\/p>\n

\n
[\"John\", \"Alice\", \"Mike\", \"#1\", \"\u0410\u0440\u0442\u0435\u043c\", \"20\", \"60\", \"60\", \"DoubleTrouble\"]\n[[\"John\"], [\"Alice\"], [\"Mike\"], [\"#1\"], [\"\u0410\u0440\u0442\u0435\u043c\"], [\"20\"], [\"60\"], [\"60\"], [\"DoubleTrouble\"]]\n[[\"Alice\", \"John\"], [\"#1\", \"Mike\"], [\"20\", \"\u0410\u0440\u0442\u0435\u043c\"], [\"60\", \"60\"], [\"DoubleTrouble\"]]\n[[\"#1\", \"Alice\", \"John\", \"Mike\"], [\"20\", \"60\", \"60\", \"\u0410\u0440\u0442\u0435\u043c\"], [\"DoubleTrouble\"]]\n[[\"#1\", \"20\", \"60\", \"60\", \"Alice\", \"John\", \"Mike\", \"\u0410\u0440\u0442\u0435\u043c\"], [\"DoubleTrouble\"]]\n[\"#1\", \"20\", \"60\", \"60\", \"Alice\", \"DoubleTrouble\", \"John\", \"Mike\", \"\u0410\u0440\u0442\u0435\u043c\"]\n\n<\/code><\/pre>\n<\/div>\n
Sortie de l’algorithme pour l’ex\u00e9cution multithread\u00a0:<\/p>\n
\n
[\"John\", \"Alice\", \"Mike\", \"#1\", \"\u0410\u0440\u0442\u0435\u043c\", \"20\", \"60\", \"60\", \"DoubleTrouble\"]\n[[\"John\"], [\"Alice\"], [\"Mike\"], [\"#1\"], [\"\u0410\u0440\u0442\u0435\u043c\"], [\"20\"], [\"60\"], [\"60\"], [\"DoubleTrouble\"]]\n[[\"20\", \"\u0410\u0440\u0442\u0435\u043c\"], [\"Alice\", \"John\"], [\"60\", \"60\"], [\"#1\", \"Mike\"], [\"DoubleTrouble\"]]\n[[\"#1\", \"60\", \"60\", \"Mike\"], [\"20\", \"Alice\", \"John\", \"\u0410\u0440\u0442\u0435\u043c\"], [\"DoubleTrouble\"]]\n[[\"DoubleTrouble\"], [\"#1\", \"20\", \"60\", \"60\", \"Alice\", \"John\", \"Mike\", \"\u0410\u0440\u0442\u0435\u043c\"]]\n[\"#1\", \"20\", \"60\", \"60\", \"Alice\", \"DoubleTrouble\", \"John\", \"Mike\", \"\u0410\u0440\u0442\u0435\u043c\"]\n\n<\/code><\/pre>\n<\/div>\n
La complexit\u00e9 temporelle de l’algorithme est O(n*log(n)), ce qui est l\u00e9g\u00e8rement meilleur que O(n^2)<\/p>\n
Sources<\/h3>\n
https:\/\/en.wikipedia.org\/wiki\/Insertion_sort<\/a >
https:\/\/en.wikipedia.org\/wiki\/Merge_sort<\/a><\/p>\n
Code source<\/h3>\n
https:\/\/gitlab.com\/demensdeum \/algorithms\/-\/tree\/master\/sortAlgorithms\/insertionSort<\/a>
https:\/\/gitlab.com\/demensdeum\/algorithms\/-\/tree\/master\/sortAlgorithms\/mergeSort<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
Tri par insertion Tri par insertion – chaque \u00e9l\u00e9ment est compar\u00e9 aux pr\u00e9c\u00e9dents de la liste et l’\u00e9l\u00e9ment est \u00e9chang\u00e9 avec le plus grand, le cas \u00e9ch\u00e9ant, sinon la boucle de comparaison interne s’arr\u00eate. \u00c9tant donn\u00e9 que les \u00e9l\u00e9ments sont tri\u00e9s du premier au dernier, chaque \u00e9l\u00e9ment est compar\u00e9 \u00e0 une liste d\u00e9j\u00e0 tri\u00e9e, ceContinue reading “Tri par insertion, tri par fusion”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[61,52],"tags":[131,138,139,190],"class_list":["post-2457","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-algorithms","tag-insertion-sort","tag-merge-sort","tag-sorting","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"fr","enabled_languages":["en","ru","zh","de","fr","ja","pt","hi"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false},"hi":{"title":false,"content":false,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/2457","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/comments?post=2457"}],"version-history":[{"count":19,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/2457\/revisions"}],"predecessor-version":[{"id":3927,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/2457\/revisions\/3927"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/media?parent=2457"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/categories?post=2457"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/tags?post=2457"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}