{"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\/pt\/2019\/12\/30\/insertion-sort-merge-sort\/","title":{"rendered":"Classifica\u00e7\u00e3o por inser\u00e7\u00e3o, classifica\u00e7\u00e3o por mesclagem"},"content":{"rendered":"

Classifica\u00e7\u00e3o por inser\u00e7\u00e3o<\/h3>\n

Classifica\u00e7\u00e3o por inser\u00e7\u00e3o – cada elemento<\/strong> \u00e9 comparado com os anteriores<\/strong> da lista e o elemento<\/strong> \u00e9 trocado pelo maior, se houver, caso contr\u00e1rio, o loop de compara\u00e7\u00e3o interno para. Como os elementos s\u00e3o classificados do primeiro ao \u00faltimo, cada elemento \u00e9 comparado a uma lista j\u00e1 classificada, o que *possivelmente* reduz o tempo geral de execu\u00e7\u00e3o. A complexidade de tempo do algoritmo \u00e9 O(n^2), ou seja, id\u00eantica \u00e0 variedade da bolha.<\/p>\n

Mesclar classifica\u00e7\u00e3o<\/h3>\n

Mesclar classifica\u00e7\u00e3o – a lista \u00e9 dividida em grupos de um elemento, ent\u00e3o os grupos s\u00e3o \u201cmesclados\u201d em pares com compara\u00e7\u00e3o simult\u00e2nea. Na minha implementa\u00e7\u00e3o, ao mesclar pares, os elementos \u00e0 esquerda s\u00e3o comparados com os elementos \u00e0 direita e, em seguida, movidos para a lista resultante; se os elementos \u00e0 esquerda desaparecerem, todos os elementos \u00e0 direita ser\u00e3o adicionados ao resultado; lista (sua compara\u00e7\u00e3o adicional \u00e9 desnecess\u00e1ria, pois todos os elementos dos grupos passam por itera\u00e7\u00f5es de classifica\u00e7\u00e3o)< br \/>O trabalho deste algoritmo \u00e9 muito f\u00e1cil de paralelizar; a etapa de fus\u00e3o de pares pode ser realizada em threads, aguardando o t\u00e9rmino das itera\u00e7\u00f5es no despachante.
Sa\u00edda do algoritmo para execu\u00e7\u00e3o de thread \u00fanico:<\/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
Sa\u00edda do algoritmo para execu\u00e7\u00e3o multithread:<\/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
A complexidade de tempo do algoritmo \u00e9 O(n*log(n)), que \u00e9 um pouco melhor que O(n^2)<\/p>\n
Fontes<\/h3>\n
https:\/\/en.wikipedia.org\/wiki\/Insertion_sort<\/a >
https:\/\/en.wikipedia.org\/wiki\/Merge_sort<\/a><\/p>\n
C\u00f3digo fonte<\/h3>\n
https:\/\/gitlab.com\/demensdeum \/algoritmos\/-\/\u00e1rvore\/master\/sortAlgoritmos\/inser\u00e7\u00e3oSort<\/a>
https:\/\/gitlab.com\/demensdeum\/algorithms\/-\/tree\/master\/sortAlgorithms\/mergeSort<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
Classifica\u00e7\u00e3o por inser\u00e7\u00e3o Classifica\u00e7\u00e3o por inser\u00e7\u00e3o – cada elemento \u00e9 comparado com os anteriores da lista e o elemento \u00e9 trocado pelo maior, se houver, caso contr\u00e1rio, o loop de compara\u00e7\u00e3o interno para. Como os elementos s\u00e3o classificados do primeiro ao \u00faltimo, cada elemento \u00e9 comparado a uma lista j\u00e1 classificada, o que *possivelmente* reduzContinue reading “Classifica\u00e7\u00e3o por inser\u00e7\u00e3o, classifica\u00e7\u00e3o por mesclagem”<\/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":"pt","enabled_languages":["en","ru","zh","de","fr","ja","pt"],"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}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/2457","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/comments?post=2457"}],"version-history":[{"count":19,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/2457\/revisions"}],"predecessor-version":[{"id":3927,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/2457\/revisions\/3927"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/media?parent=2457"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/categories?post=2457"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/tags?post=2457"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}