파이썬 머지병합 and 머지정렬

머지병합.. 근데 머지가 병합아닌가?

족발 같은건가??ㅋㅋ

 

머지병합은 [1,2,5,6] [3,4,7,8] 이런식으로 정렬이 되어 있는 두 개의 리스트를 정렬된 하나의 리스트로 합치는 것을 말한다. [1,2,3,4,5,6,7,8] 이렇게 ~!

 

array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]


def merge(array1, array2):
    a_idx = 0
    b_idx = 0
    array3 = []
    while True:
        if array1[a_idx] > array2[b_idx]:
            array3.append(array2[b_idx])
            b_idx += 1
        else:
            array3.append(array1[a_idx])
            a_idx += 1
        if not (len(array1) > a_idx and len(array2) > b_idx):
            break
    if a_idx < len(array1):
        while a_idx < len(array1):
            array3.append(array1[a_idx])
            a_idx += 1

    if b_idx < len(array2):
        while b_idx < len(array2):
            array3.append(array2[b_idx])
            b_idx += 1


    return  array3


print(merge(array_a, array_b))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!

코드로 구현해보았다. 먼저 

↓

[1, 2, 3, 5]

↓

[4, 6, 7, 8]  이렇게 시작을 해서 두 개중 작은 요소를 새로운 배열에 집어 넣고 index를 하나 올린다.

new_arr [1]

 

     ↓

[1, 2, 3, 5]

↓

[4, 6, 7, 8] 

new_arr [1, 2]

 

          ↓

[1, 2, 3, 5]

↓

[4, 6, 7, 8] 

 

new_arr [1, 2, 3]

 

              ↓

[1, 2, 3, 5]

↓

[4, 6, 7, 8] 

 

new_arr [1, 2, 3, 4]

이런식으로 간다. 한 배열이 마지막 인덱스에 다다르면  다른 나머지 배열에 있는 요소를 새로운 배열에 다 집어 넣으면 된다.

 

이렇게 하면 [1,2,3,4,5,6,7,8]이 잘 출력이 된다.

 

이번엔 머지정렬을 배워볼 것인데

divide and conquer 디바이드 앤 콩퀄 ~ 분할 정복이다. 처음에 이게 될까? 라고 생각을 했는데 신기하다 ㅋㅋ

 

[5,6,1,2,8,9,4,3] 과 같은 배열이 있다고 가정해보자. 이걸 분할해보자, 먼저 반으로~

[5,6,1,2] [8,9,4,3] 아까 우리는 정렬이 되어 있어야 머지병합이 가능하다고 했다. 다시 반으로 ~

[5,6] [1,2] [8,9] [4,3] 다시 반으로 ~

[5] [6] [1] [2] [8] [9] [4] [3] 요소가 각 각 하나의 배열에 존재하는 것을 볼 수 있다.

지금 이 상태는 정렬이 되어 있는 건가?? 그렇다고 안되어 있다고 하기도 그렇다.

반에 나 혼자 존재한다면 내가 키가 제일 큰 사람, 키가 제일 작은 사람 이기도 하다. 따라서 하나만 있어도 어쨌든 정렬이 되어있다고 말할 수 있다.

 

그럼 이제 머지병합으로 거꾸로 올라가보자

[5,6] [1,2] [8,9] [3,4]

[1,2,5,6] [3,4,8,9]

[1,2,3,4,5,6,8,9] 신기하게도 이렇게 접근하니 정렬이 되었다. 100만개 짜리 배열을 일일이 반으로 나누면 얼마나 힘이 들까?? 우리는 하나!! 의 각 배열요소에 접근하면 되니까 계속 반으로 나눌 수 있는 재귀함수를 사용하면 좀 더 편할 것 같다. 탈출조건으로는 len(array) == 1: return array하면 된다.

 

 

def merge_sort(array):
    if len(array) == 1:
        return array
    middle = len(array) // 2
    left_array =  merge_sort(array[:middle])
    right_array =  merge_sort(array[middle:])
    return merge(left_array,right_array)

먼저 middle이라는 변수를 만들고 배열의 길이의 반절을 넣는다.

그리고 받아온 배열의 반절을 left_array에 넣고 나머지 반절을 right_array에 넣는다. 그리고 merge_sort를 다시 재귀함수 안에 넣고 돌린다. 이렇게 돌리다가 ~~ 언젠간 하나가 되는 때가 올 것이다. 그때 하나의 배열을 return하고 다시 호출된 함수로 돌아와서 머지 병합을 한다.