Sep 18, 2019 โ€ข3 min read โ˜•

๐Ÿ’ป Merge Sort, ํ•ฉ๋ณ‘ ์ •๋ ฌ์ด๋ž€?

Merge Sort(ํ•ฉ๋ณ‘์ •๋ ฌ)๋Š” Divide and Conquer(๋ถ„ํ•  ์ •๋ณต) ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ข…๋ฅ˜์ค‘ ํ•˜๋‚˜์ด๋‹ค. ๋ถ„ํ• ์ •๋ณต์ด๋ž€ ์ฃผ์–ด์ง„ ๋ฌธ์ œ๋ฅผ ์—ฌ๋Ÿฌ sub ๋ฌธ์ œ๋“ค๋กœ ๋‚˜๋ˆˆ ๋‹ค์Œ์— ๊ทธ ๋ฌธ์ œ๋“ค์„ ํ•ด๊ฒฐํ•œ ๋‹ค์Œ์— ํ•ฉ์น˜๋Š” ๊ฒƒ์„ ์˜๋ฏธํ•œ๋‹ค.

Pseudo-code ์„ค๋ช…

Merge-sort์™€ Merge parameter์—์„œ A๋Š” ์ •๋ ฌ์ด ํ•„์š”ํ•œ list์ด๋‹ค. p๋Š” list์˜ ๊ฐ€์žฅ ์•ž index, q๋Š” list์˜ ์ค‘๊ฐ„ index, r์€ list์˜ ๋งˆ์ง€๋ง‰ index๋ฅผ ์˜๋ฏธํ•œ๋‹ค.

Merge Sort

: ์ด ํ•จ์ˆ˜๋Š” ์ •๋ ฌ๋˜์ง€ ์•Š์€ list๋ฅผ ๋ถ„ํ• ํ•˜๋Š” ์—ญํ• ์„ ํ•œ๋‹ค

  • p<r ์ด๋ฉด, ์•„์ง ์ •๋ ฌ์ด ์™„์„ฑ๋˜์ง€ ์•Š์€ ์ƒํƒœ๋ผ๊ณ  ๊ฐ„์ฃผํ•ด์„œ, p์™€ r์˜ ์ค‘๊ฐ„์ธ q๋ฅผ ๊ตฌํ•œ๋‹ค
  • (p~q), (q+1~r) ๋กœ list๋ฅผ ๋ถ„ํ• ํ•˜๊ณ  merge ํ•จ์ˆ˜์— ๋ณด๋‚ธ๋‹ค.

Merge

: ์ด ํ•จ์ˆ˜๋Š” ๋ถ„ํ• ๋œ list๋ฅผ ํ•ฉ๋ณ‘ํ•˜๋Š” ์—ญํ• ์„ ํ•œ๋‹ค.

  • 1~2๋ผ์ธ: n1์€ ๋ถ„ํ• ๋œ ์™ผ์ชฝ list์˜ ๊ธธ์ด์ด๊ณ  n2๋Š” ๋ถ„ํ• ๋œ ์˜ค๋ฅธ์ชฝ list์˜ ๊ธธ์ด์ด๋‹ค.
  • 3~7๋ผ์ธ: ๊ทธ ๋‹ค์Œ์— L๊ณผ R์„ ๊ธธ์ด๋งŒํผ ์„ ์–ธํ•ด์ค€ ๋‹ค์Œ์— ์ •๋ ฌ๋˜์ง€ ์•Š๋Š” list์—์„œ ํ•ด๋‹น index๋ฅผ ๋ฐ›์•„์™€์„œ L๊ณผ R์„ ์ฑ„์›Œ์ค€๋‹ค.
  • 8~11๋ผ์ธ: pseudo-code์—์„œ๋Š” 1์ด ๊ฐ€์žฅ ์ฒซ index๋ฅผ ์˜๋ฏธํ•˜๊ธฐ ๋•Œ๋ฌธ์— i,j = 1๋กœ ์„ค์ •๋˜์—ˆ๋‹ค.
  • 12~17๋ผ์ธ: L๊ณผ R์˜ item๋“ค์„ ๋น„๊ตํ•˜๊ณ  ๋” ์ž‘์€ ๊ฐ’์„ ๊ธฐ์กด list์˜ ์™ผ์ชฝ์—, ๋” ํฐ ๊ฐ’์„ list์˜ ์˜ค๋ฅธ์ชฝ์— ๋ฐฐ์น˜๋ฅผ ํ•œ๋‹ค.

source: merge-sort

๊ทธ๋ฆผ์„ ๋ณด๋ฉฐ step๋“ค์„ ํ•˜๋‚˜์”ฉ ๋”ฐ๋ผ๊ฐ€๋ณด์ž

step1 - ์ „์ฒด list๋ฅผ ๋ถ„ํ• ํ•œ๋‹ค.

step2 - p<r์ด๊ธฐ ๋•Œ๋ฌธ์— ์™ผ์ชฝ list ๋‹ค์‹œ ๋ถ„ํ• ํ•œ๋‹ค

step3 - p<r์ด๊ธฐ ๋•Œ๋ฌธ์— ์™ผ์ชฝ list ๋‹ค์‹œ ๋ถ„ํ• ํ•œ๋‹ค

step4~6 - ๋ถ„ํ• ๋œ list๋ฅผ ๋ณ‘ํ•ฉํ•œ๋‹ค. ๋‘˜์„ ๋น„๊ตํ•˜๊ณ  ๋” ์ž‘์€ ๊ฐ’์„ ์™ผ์ชฝ์— ์œ„์น˜ ์‹œํ‚จ๋‹ค.

step 7 - ์ด์ „ merge๊ฐ€ ๋๋‚ฌ์œผ๋‹ˆ ์ƒ์œ„ recursion์œผ๋กœ ๋Œ์•„๊ฐ€์„œ ์˜ค๋ฅธ์ชฝ list๋ฅผ ๋ถ„ํ• ํ•œ๋‹ค.

step8~10 - ๋ถ„ํ• ๋œ list๋ฅผ ํ•ฉ๋ณ‘ํ•œ๋‹ค. ๋‘˜์„ ๋น„๊ตํ•˜๊ณ  ๋” ์ž‘์€ ๊ฐ’์„ ์™ผ์ชฝ์— ์œ„์น˜ ์‹œํ‚จ๋‹ค.

step 11 - ์ด ๋ถ€๋ถ„์„ ์ดํ•ดํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ์ฝ”๋“œ๋กœ ์‚ดํŽด๋ณด์ž.

while i < len(L) and j < len(R): 
    if L[i] < R[j]: 
        num[k] = L[i] 
        i+=1
    else: 
        num[k] = R[j] 
        j+=1
    k+=1

[27,38] [3,43] ์„ ๋ณ‘ํ•ฉํ•˜๋Š” ๊ณผ์ •์„ ์‚ดํŽด๋ณด๋ฉด, ๊ฐ๊ฐ list์˜ ์ฒซ์ธ์ž๋ฅผ ๋ณด๊ณ  ๋น„๊ต๋ฅผ ํ•œ๋‹ค.

  • 3์ด ๋” ์ž‘์œผ๋‹ˆ [3] ์ด ๋จผ์ € ๋“ค์–ด๊ฐ€๊ฒŒ ๋œ๋‹ค.
  • ๊ทธ ๋‹ค์Œ์— 27๊ณผ 43์„ ๋น„๊ตํ•˜๊ณ  27์ด ๋” ์ž‘์€๋‹ˆ [3,27]์ด ๋œ๋‹ค.
  • ๊ทธ ๋‹ค์Œ์—๋Š” 38๊ณผ 43์„ ๋น„๊ตํ•˜๊ณ  38์ด ๋” ์ž‘์€๋‹ˆ [3, 27, 38] ์ด ๋œ๋‹ค.
  • ํ•˜์ง€๋งŒ ์ด์ œ i๊ฐ€ 2๊ฐ€ ๋˜์–ด์„œ len(L)๊ณผ ๊ฐ™์•„์กŒ๊ธฐ ๋•Œ๋ฌธ์— while๋ฌธ์„ ๋น ์ ธ ๋‚˜์˜ค๊ฒŒ ๋œ๋‹ค.

์ด๋•Œ ๋‚˜๋จธ์ง€ 43์„ ๋ง๋ถ™ํžˆ๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋ฐ‘์— ์ฝ”๋“œ๋“ค์ด ํ•„์š”ํ•˜๋‹ค. ์ˆซ์ž๊ฐ€ ๋‚จ์•˜๋‹ค๋Š” ๊ฒƒ์€ ๋‹ค๋ฅธ ์ˆซ์ž๋“ค ๋ณด๋‹ค ๊ฐ’์ด ์ปธ๋‹ค๋Š” ์˜๋ฏธ์ด๋‹ค. ๊ทธ๋ž˜์„œ ๋‚จ์€ ๊ธธ์ด๋งŒํผ ๊ธฐ์กด list์— ๋ถ™ํ˜€์„œ [3, 27, 38, 43] ์ด ๋˜๋Š” ๊ฒƒ์ด๋‹ค.

while i < len(L): 
    num[k] = L[i] 
    i+=1
    k+=1

while j < len(R): 
    num[k] = R[j] 
    j+=1
    k+=1

๊ทธ ์ดํ›„๋กœ ๋‹ค์‹œ ์ƒ์œ„ recursion์œผ๋กœ ๋Œ์•„๊ฐ€์„œ ๋˜‘๊ฐ™์€ ์ž‘์—…์„ ์ง„ํ–‰ํ•œ๋‹ค.

Python Code

์œ„์— pseudo-code์™€๋Š” ๋‹ค๋ฅด๊ฒŒ ๊ตฌ์„ฑ์„ ํ–ˆ๋‹ค. ์ด์ „์—๋Š” ํ•จ์ˆ˜ 2๊ฐœ๋ฅผ ๋งŒ๋“ค์–ด์„œ recursion์œผ๋กœ ํ–ˆ์ง€๋งŒ, ํ•˜๋‚˜์˜ ํ•จ์ˆ˜๋กœ ๊ฐ™์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ตฌํ˜„ํ–ˆ๋‹ค.

import random

def merge_sort(num): 
    if len(num) >1: 
        mid = len(num)//2 # list์˜ ์ค‘๊ฐ„์„ ์ฐพ๋Š”๋‹ค
        L = num[:mid] # list์˜ ์™ผ์ชฝ์„ ๋ถ„ํ• ํ•œ๋‹ค
        R = num[mid:] # list์˜ ์˜ค๋ฅธ์ชฝ์„ ๋ถ„ํ• ํ•œ๋‹ค
    
        merge_sort(L) # ์™ผ์ชฝ list๋ฅผ ์ •๋ ฌํ•œ๋‹ค
        merge_sort(R) # ์˜ค๋ฅธ์ชฝ list๋ฅผ ์ •๋ ฌํ•œ๋‹ค
    
        i = j = k = 0
            
        # ์ผ์‹œ์ ์œผ๋กœ ๋งŒ๋“  L๊ณผ R์„ ๋น„๊ตํ•œ๋‹ค
        while i < len(L) and j < len(R): 
            if L[i] < R[j]: # ์™ผ์ชฝ list์— ์žˆ๋˜ item์ด ๋” ์ž‘์œผ๋ฉด L[i]๋ฅผ list ์™ผ์ชฝ์— ์œ„์น˜ํ•˜๊ฒŒ ํ•œ๋‹ค
                num[k] = L[i] 
                i+=1
            else: # ์˜ค๋ฅธ์ชฝ list์— ์žˆ๋˜ item์ด ๋” ์ž‘์œผ๋ฉด R[j]๋ฅผ list ์™ผ์ชฝ์— ์œ„์น˜ํ•˜๊ฒŒ ํ•œ๋‹ค
                num[k] = R[j] 
                j+=1
            k+=1
            
        # ์œ„์— len(L) and len(R)์ด์—ˆ๊ธฐ ๋•Œ๋ฌธ์—, ๋” ๊ธด list์˜ ์ˆซ์ž๊ฐ€ ๋‚จ์•˜์„ ๊ฒƒ์ด๋‹ค,
        # ๊ทธ ์ˆซ์ž๋“ค์„ ์ด์–ด ๋ถ™ํžŒ๋‹ค.
        # ๋‚จ์€ ์ˆซ์ž๋“ค์€ ํฌ๊ธฐ ๋•Œ๋ฌธ์— ๋‚จ์€ ๊ฒƒ์ด๊ธฐ์— ์˜ค๋ฅธ์ชฝ์— ๋ถ™ํ˜€์ง„๋‹ค
        while i < len(L): 
            num[k] = L[i] 
            i+=1
            k+=1
            
        while j < len(R): 
            num[k] = R[j] 
            j+=1
            k+=1

            

number = [i for i in range(10)]
random.shuffle(number)
print(number)
merge = merge_sort(number)
print(number)
ยฉ 2021 Dojin Kim, Built with Gatsby