머지와 D.C의 만남

병합정렬 구현

이번 시간에는 merge와 Division Control 개념을 복합하여 병합정렬에 대해 알아
보자.

머지는 2개의 정렬된 배열이 있을 때 2배열을 한배열에 정렬해서 하나의 배열을 리턴
해준다.

분할정복인 D.C는 머지에 들어가기전 길이가 2이상인 배열이 길이가 하나인 배열이 될
때까지 잘라주는 역할을 한다.

우선 머지부터 살펴보기로 하자.

머지

머지함수는 정렬된 두배열이 있을 때 각각의 배열의 원소를 서로 비교해서 크기가 작은
원소가 새로운 배열에 들어가는 형식이다. 따라서 고려해야 할 사항으로 각 배열의 인
덱스변수가 필요하고 특정 배열의 원소가 새로운 배열에 들어가지 못했을 경우 남아있는
배열이 어떤 배열인지 확인하는 작업을 거친 후에 남은 원소들을 새로운 배열에 넣어주어
야 하는 작업이 필요하다.

그 코드가 아래와 같다.

def merge(array_a, array_b):
    index_a = 0 #배열 a의 index를 담당할 index_a
    index_b = 0 #배열 b의 index를 담당할 index_b
    na = len(array_a) # 2개의 배열 중 특정 배열이 먼저 새로운 배열에 들어
    nb = len(array_b) # 갔음을 확인하기위해 필요한 변수 na, nb
    new_arr = [] # 정렬된 새로운 배열을 리턴할 new_arr
    
    # 두 배열의 원소간 서로 대소 비교를 한 후에 새로운 배열에 원소를 넣는다.
    while index_a != na and index_b != nb:
        if array_a[index_a] < array_b[index_b]:
            new_arr.append((array_a[index_a]))
            index_a += 1
        else:
            new_arr.append(array_b[index_b])
            index_b += 1

    # 아직 들어가지 못한 원소의 배열이 있다면 해당 배열을 가려내어 안에 있는 원
    # 소를 새로운 배열에 넣어 새로운 배열을 반환한다.
    while index_a != na or index_b != nb:
        if index_a == na:
            new_arr.append(array_b[index_b])
            index_b += 1
        else:
            new_arr.append((array_a[index_a]))
            index_a += 1

    return new_arr    

D.C (Division Control)

분할정복의 역할은 두개의 배열을 새로운 배열에 담아 정렬해서 반환하는 과정에 들어가기에
앞서 배열의 원소의 길이가 하나가 될때까지 계속해서 쪼개주는 역할을 한다.

def merge_sort(array):
    if len(array) == 1:
        return array
    mid = len(array) // 2
    left_array = array[:mid]
    right_array = array[mid:]
    return merge(merge_sort(left_array), merge_sort(right_array))
    
기저 조건은 배열의 원소가 하나일 때 분할정복이 종료된다. 여기서는 병합정렬 안에 분할 
정복과 머지가 들어가 있어 함수이름을 merge_sort로 명명하였다.

분할 정복의 역할은 해당 함수 안에 들어있는 코드 자체로 간주하면 된다. 우선 매개변수로 
받은 배열을 반으로 쪼갠다. 그리고 재귀로 자기자신을 호출한다. 그렇게 되면 [1,2,3,4]
라는 배열이 인수로 들어간다고 했을 때 [1,2,3,4] -> left_array = [1,2]가 right_ar
ray = [3,4]가 들어가게 된다.

그런다음 merge(merge_sort([1,2]), merge_sort([3,4])) 가 실행되게 되는데 실행 순
서의 경우 merge_sort([1,2]) -> merge_sort([3,4]) -> merge(A, B) 순이 된다.

따라서 merge_sort([1,2])의 부분이 수행되어지게 되고 [1,2] -> left_array = [1]
, right_array = [2]가 되고 return merge(merge_sort([1]), merge_sort([2]))가 수
행되어 merge([1], [2])가 되어 [1,2]가 반환되게된다.

해당 배열은 merge([1,2], merge_sort([3,4])로 들어가게 돼서 다시 merge_sort([3,4])
를 수행하는 형식이 되는 것이다.

정리

머지와 분할정복을 콜라보한 머지정렬에대해서 알아보았다.

머지정렬은 NlogN의 시간복잡도를 가진다. merge 함수에서 반환하는 배열의 길이가 N일 때
총 N번의 비교를 수행하게 되고 merge_sort에선 길이가 N인 배열에 대해 밑이 2인 logN번
의 연산을 수행하게된다.

따라서 merge_sort(some_array)에 들어갈 때 N번의 연산을 수행하므로 NlonN의 시간 복
잡도를 가진다.