{"id":525,"date":"2018-03-29T13:00:37","date_gmt":"2018-03-29T04:00:37","guid":{"rendered":"https:\/\/dong1lkim.oboki.net\/?p=525"},"modified":"2019-09-01T22:21:42","modified_gmt":"2019-09-01T13:21:42","slug":"algorithm-merge-sort","status":"publish","type":"post","link":"https:\/\/oboki.net\/workspace\/python\/algorithm-merge-sort\/","title":{"rendered":"[Algorithm] Merge Sort"},"content":{"rendered":"<h1>Python\uc73c\ub85c \uad6c\ud604\ud55c Merge Sort<\/h1>\n<blockquote><p>\n  \ubd84\ud560\uc815\ubcf5 (Divide &amp; Conquer) \uae30\ubc95\uc744 \uc774\uc6a9\ud558\uc5ec \uc815\ub82c\ud55c\ub2e4.\n<\/p><\/blockquote>\n<p>\uc8fc\uc5b4\uc9c4 \ub9ac\uc2a4\ud2b8\ub97c \uc6d0\uc18c\uc758 \uac2f\uc218\uac00 1\uc778 \ub9ac\uc2a4\ud2b8\uac00 \ub420 \ub54c\uae4c\uc9c0 \ubd84\ud560\ud55c \ub4a4 \uadf8 \ub9ac\uc2a4\ud2b8\ub4e4\uc744 \ub2e4\uc2dc \ud569\uce58\ub294 \uacfc\uc815\uc5d0\uc11c \uc6d0\uc18c\ub97c \ube44\uad50\ud558\uc5ec \uc815\ub82c\uc744 \uc218\ud589\ud55c\ub2e4.<\/p>\n<h2>\uc18c\uc2a4\ucf54\ub4dc<\/h2>\n<p><code>vi sort.py<\/code><\/p>\n<pre><code class=\"py\"># Merge Sort\ndef sort_merge(arr):\n\n    if len(arr)&lt;=1: return arr ## Exception\n\n    ## Divide\n    left    = sort_merge(arr[:len(arr)\/\/2])\n    right   = sort_merge(arr[len(arr)\/\/2:])\n\n    ## Conquer\n    i,j,k = 0,0,0\n    while i&lt;len(left) and j&lt;len(right):\n        if left[i]&lt;=right[j]:   arr[k],i = left[i],i+1\n        else:                   arr[k],j = right[j],j+1\n        k += 1\n    while k&lt;len(arr):\n        if i==len(left):    arr[k],j = right[j],j+1\n        elif j==len(right): arr[k],i = left[i],i+1\n        k += 1\n\n    return arr \n<\/code><\/pre>\n<h2>\ud14c\uc2a4\ud2b8 \ucf54\ub4dc<\/h2>\n<p><code>vi test_sort.py<\/code><\/p>\n<pre><code class=\"py\">#!\/bin\/python\n\ndef main():\n    import random\n    import sort\n    A=[random.randint(1,100) for _ in range(10)]\n    print(A)\n    print(sort.sort_merge(A))\n\nif __name__ == '__main__':\n    main()\n<\/code><\/pre>\n<h2>\uc218\ud589 \uacb0\uacfc<\/h2>\n<pre><code class=\"bash\">$ python test_sort.py \n[68, 70, 54, 30, 26, 96, 52, 90, 88, 11]\n[11, 26, 30, 52, 54, 68, 70, 88, 90, 96]\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Python\uc73c\ub85c \uad6c\ud604\ud55c Merge Sort \ubd84\ud560\uc815\ubcf5 (Divide &amp; Conquer) \uae30\ubc95\uc744 \uc774\uc6a9\ud558\uc5ec \uc815\ub82c\ud55c\ub2e4. \uc8fc\uc5b4\uc9c4 \ub9ac\uc2a4\ud2b8\ub97c \uc6d0\uc18c\uc758 \uac2f\uc218\uac00 1\uc778 \ub9ac\uc2a4\ud2b8\uac00 \ub420 \ub54c\uae4c\uc9c0 \ubd84\ud560\ud55c \ub4a4 \uadf8 \ub9ac\uc2a4\ud2b8\ub4e4\uc744 \ub2e4\uc2dc \ud569\uce58\ub294 \uacfc\uc815\uc5d0\uc11c \uc6d0\uc18c\ub97c \ube44\uad50\ud558\uc5ec \uc815\ub82c\uc744 \uc218\ud589\ud55c\ub2e4. \uc18c\uc2a4\ucf54\ub4dc vi sort.py # Merge Sort def sort_merge(arr): if len(arr)&lt;=1: return arr ## Exception ## Divide left = sort_merge(arr[:len(arr)\/\/2]) right = sort_merge(arr[len(arr)\/\/2:]) ## Conquer i,j,k [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[17,10],"tags":[150,34,151],"class_list":["post-525","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-python","tag-algorithm","tag-python","tag-sort"],"_links":{"self":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/525","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/comments?post=525"}],"version-history":[{"count":3,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/525\/revisions"}],"predecessor-version":[{"id":1282,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/525\/revisions\/1282"}],"wp:attachment":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/media?parent=525"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/categories?post=525"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/tags?post=525"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}