{"id":681,"date":"2014-12-31T23:11:42","date_gmt":"2014-12-31T22:11:42","guid":{"rendered":"http:\/\/www.valcon.it\/pascal\/?p=681"},"modified":"2015-07-03T14:09:50","modified_gmt":"2015-07-03T12:09:50","slug":"merge-sort","status":"publish","type":"post","link":"https:\/\/www.valcon.it\/pascal\/merge-sort\/","title":{"rendered":"Merge Sort"},"content":{"rendered":"<p>Algoritmo intuitivo e ottimo.<br \/>\nUtilizza l&#8217;algoritmo di <a class=\"\" title=\"Fusione di sequenze\" href=\"http:\/\/www.valcon.it\/pascal\/fusione-di-sequenze\/\">fusione di sottosequenze ordinate<\/a>.<\/p>\n<pre class=\"\">Procedure MERGESORT(Var V: Vettore; Inf, Sup: Integer);\r\nVar\r\n \u00a0 Medio: Integer;\r\nBegin\r\n \u00a0 If(Inf < Sup) Then\r\n\u00a0 \u00a0 \u00a0 Begin\r\n \u00a0 \u00a0 \u00a0 \u00a0 Medio:=(Inf+Sup) Div 2;\r\n \u00a0 \u00a0 \u00a0 \u00a0 MERGESORT(V, Inf \u00a0 \u00a0, Medio);\r\n \u00a0 \u00a0 \u00a0 \u00a0 MERGESORT(V, Medio+1, Sup \u00a0);\r\n \u00a0 \u00a0 \u00a0 \u00a0 Merge(V, Inf, Medio, Sup);\r\n\u00a0 \u00a0 \u00a0 End;\r\nEnd;\r\n...\r\nMERGESORT(V, 1, N);\r\n...<\/pre>\n<p>La chiamata chiede di ordinare l'array dal primo, <strong>1<\/strong>, all'ultimo, <strong>N<\/strong>, elemento.<br \/>\nA ogni chiamata, dopo aver calcolato <strong>Medio<\/strong>, si effettuano due chiamate ricorsive, da <strong>Inf<\/strong> a <strong>Medio<\/strong> e da <strong>Medio+1<\/strong> a <strong>Sup<\/strong>.<\/p>\n<p>In pratica le chiamate ricorsive scendono fino al livello di array con un solo elemento.<br \/>\nAl ritorno di ogni coppia di chiamate si effettua la fusione, merge, delle due parti ordinate (l'array con un solo elemento \u00e8 gi\u00e0 ordinato...).<\/p>\n<h3><img loading=\"lazy\" decoding=\"async\" class=\"alignright wp-image-685 size-full\" src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms1.png\" alt=\"ms1\" width=\"250\" height=\"322\" srcset=\"https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms1.png 250w, https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms1-116x150.png 116w, https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms1-233x300.png 233w\" sizes=\"(max-width: 250px) 100vw, 250px\" \/>Esempio 1<\/h3>\n<p>Sia <tt>v={1, 3, 7, 4, 15, 0, 9, 10}<\/tt><\/p>\n<p>Le chiamate ricorsive sugli indici da <strong>1<\/strong> a <strong>8<\/strong> e con i valori medi successivi<\/p>\n<ul>\n<li>(1+8)\/2 = 4<\/li>\n<li>(1+4)\/2 = 2<\/li>\n<li>(5+8)\/2 = 6<\/li>\n<li>(1+2)\/2 = 1<\/li>\n<li>(3+4)\/2 = 3<\/li>\n<li>(5+6)\/2 = 5<\/li>\n<li>(7+8)\/2 = 7<\/li>\n<\/ul>\n<p>hanno l'effetto di raggiungere i singoli elementi.<\/p>\n<p>Con i valori effettivi, l'array dopo le chiamate ricorsive diventa una sequenza di 8 array con un elemento<\/p>\n<p style=\"padding-left: 30px;\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-687 size-full\" src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms11.png\" alt=\"ms11\" width=\"250\" height=\"322\" srcset=\"https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms11.png 250w, https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms11-116x150.png 116w, https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms11-233x300.png 233w\" sizes=\"(max-width: 250px) 100vw, 250px\" \/><\/p>\n<p>Al ritorno di ogni due chiamate ricorsive avviene la fusione di due array ordinati...<\/p>\n<p style=\"padding-left: 30px;\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-688 size-full\" src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms12.png\" alt=\"ms12\" width=\"462\" height=\"322\" srcset=\"https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms12.png 462w, https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms12-150x105.png 150w, https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms12-300x209.png 300w\" sizes=\"(max-width: 462px) 100vw, 462px\" \/><\/p>\n<h3><img loading=\"lazy\" decoding=\"async\" class=\"alignright wp-image-686 size-full\" src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms2.png\" alt=\"ms2\" width=\"322\" height=\"403\" srcset=\"https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms2.png 322w, https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms2-120x150.png 120w, https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms2-240x300.png 240w\" sizes=\"(max-width: 322px) 100vw, 322px\" \/>Esempio 2<\/h3>\n<p>Sia <tt>v={1, 3, 7, 4, 15, 0, 9, 10, 8, 2}<\/tt><\/p>\n<p>Le chiamate ricorsive sugli indici da <strong>1<\/strong> a <strong>10<\/strong> raggiungono i singoli elementi con 2 passaggi in pi\u00f9...<\/p>\n<ul>\n<li>(1+10)\/2 = 5<\/li>\n<li>(1+5)\/2 = 3<\/li>\n<li>(6+10)\/2 = 8<\/li>\n<li>(1+3)\/2 = 2<\/li>\n<li>(4+5)\/2 = 4<\/li>\n<li>(6+8)\/2 = 7<\/li>\n<li>(9+10)\/2 = 9<\/li>\n<li><strong>(1+2)\/2 = 1<\/strong><\/li>\n<li><strong>(6+7)\/2 = 6<\/strong>.<\/li>\n<\/ul>\n<div class=\"clear\">Considerando i valori effettivi dell'array e l'esecuzione di tutti i passi...<\/div>\n<div class=\"clear\" style=\"padding-left: 30px;\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-689 size-full\" src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms22.png\" alt=\"ms22\" width=\"602\" height=\"403\" srcset=\"https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms22.png 602w, https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms22-150x100.png 150w, https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/ms22-300x201.png 300w\" sizes=\"(max-width: 602px) 100vw, 602px\" \/><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Algoritmo intuitivo e ottimo. Utilizza l&#8217;algoritmo di fusione di sottosequenze ordinate. Procedure MERGESORT(Var V: Vettore; Inf, Sup: Integer); Var \u00a0 Medio: Integer; Begin \u00a0 If(Inf < Sup) Then \u00a0 \u00a0 \u00a0 Begin \u00a0 \u00a0 \u00a0 \u00a0 Medio:=(Inf+Sup) Div 2; \u00a0 \u00a0 \u00a0 \u00a0 MERGESORT(V, Inf \u00a0 \u00a0, Medio); \u00a0 \u00a0 \u00a0 \u00a0 MERGESORT(V, Medio+1, Sup ... <a title=\"Merge Sort\" class=\"read-more\" href=\"https:\/\/www.valcon.it\/pascal\/merge-sort\/\" aria-label=\"Leggi di pi\u00f9 su Merge Sort\">Leggi tutto<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[],"_links":{"self":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts\/681"}],"collection":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/comments?post=681"}],"version-history":[{"count":8,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts\/681\/revisions"}],"predecessor-version":[{"id":5664,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts\/681\/revisions\/5664"}],"wp:attachment":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/media?parent=681"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/categories?post=681"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/tags?post=681"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}