[Algorithm] 병합정렬

백준 2751번 문제를 풀다가 시간초과가 나와서, 알고보니 여러 정렬 방법 중 시간 복잡도가 O(nlogn)인 방법을 사용해야 풀 수 있다는 것을 뒤늦게 알게 되었습니다. 그래서 그 중 하나인 병합 정렬에 대해 설명하려 합니다.

 

먼저 2751번의 문제는 다음과 같습니다.

문제 자체는 상당히 간단합니다. 문제 하단에 제시된 힌트도 있었습니다.

 

파이썬을 사용하시는 분들은 이 문제를 라이브러리를 사용해서 아주 간단하게 풀 수 있습니다.

 

N = int(input())

arr=[]

for i in range(N):
    x=int(input())
    arr.append(x)

arr.sort()
for i in arr:
    print(i)

 

이런식으로 손 쉽게 문제를 해결할 수 있습니다. 하지만  저는 내장된 정렬 함수가 아니라 nlogn의 시간 복잡도를 가진 정렬 알고리즘을 구현해서 풀고싶어서 병합 정렬을 사용해보기로 하였습니다.

 

병합 정렬은 분할 정복을 이용한 정렬입니다.

(분할 정복이란 나누고 다시 합친다는 의미입니다.)

먼저 주어진 배열을 더 이상 나눌 수 없을 때까지 나눕니다.
그런 다음에 병합을 하기 시작하는데 병합을 할 때마다 정렬을 동반하며 진행합니다.

 

위의 문제 예시를 그림으로 표현해보면 다음과 같습니다.

앞서 설명했던대로 주어진 배열을 더 이상 나눌 수 없을때가지 나눕니다. 그리고 정렬을 동반하여 병합을 시작합니다.

 

마지막으로 분할된 배열부터 시작하여 정렬과 병합을 수행합니다.

 

그러면 이렇게 정렬 된 배열이 생겨나고 이 작업을 계속 반복해서 병합해줍니다.

 

이렇게 또 병합이 되고

 

결과적으로 그림과 같은 정렬된 배열이 생겨난 모습을 확인 할 수 있습니다.

 

그러면 이런 작업을 어떻게 구현하면 좋을지 코드를 보여드리면서 말씀 드리겠습니다.

 

def merge_list(array):
    if len(array) <= 1:
        return

    mid = len(array) // 2
    left_arr = array[:mid]
    right_arr = array[mid:]

    merge_list(left_arr)
    merge_list(right_arr)

저는 재귀함수를 사용하는 방식으로 구현했기 때문에 제가 작성한 merge_list 함수가 분할된 배열마다 실행 되게끔 구현했습니다.

if문을 사용해서 배열의 크기가 1개이하이면 분할을 멈추도록 하였습니다. 만약 2개 이상이면 나눠줘야 하기때문에 분할을 진행합니다. 슬라이싱을 사용해서 배열의 처음부터 중간까지, 중간에서 마지막까지 두 배열로 나눠줍니다. 그리고 이 나눠진 배열들로 다시 merge_list 함수를 호출하고 이 과정을 반복합니다.

 

    i, j, k = 0, 0, 0

    while j < len(left_arr) and k < len(right_arr):
        if left_arr[j] < right_arr[k]:
            array[i] = left_arr[j]
            j += 1
        else:
            array[i] = right_arr[k]
            k += 1
        i += 1

각각의 크기가 2이상인 배열에서는 다음과 같은 작업을 진행하게됩니다. 먼저 나눠진 왼쪽배열과 오른쪽 배열 중 하나라도 배열의 끝에 도달하면 멈추도록 반복문을 사용합니다. 그리고 if문을 사용해서 배열중 더 작은 값을 array 배열에 넣어줍니다. 이때 주의해야 할 점이 반드시 인덱스값을 지정해서 넣어줘야 한다는 점입니다. 그냥 배열에 값 넣으면 되니까 array함수 사용해되 되겠지?하고 넣었다가 값이 완전 이상해지는 걸  볼 수 있었습니다. 왜냐하면 array함수는 배열의 끝에 값을 추가하기때문에 배열의 처음부터 차례대로 값을 채우는것이 아니고

 

이런식으로 엉뚱하게 값을 추가하게 됩니다. 따라서 반드시 인덱스 값을 지정해서 0번째부터 차례대로 채워줘야합니다. 이제 array 배열에 값을 넣다보면 한쪽 배열의 값이 다 들어가고 반복문이 종료되는 경우가 생길 수 있습니다. 이렇게 되면 남아있는 다른 하나의 배열의 값도 넣어줘야하기 때문에 마지막으로 아래와 같이 코드를 추가해주었습니다.

 

    if j == len(left_arr):
        array[i:] = right_arr[k:]
    else:
        array[i:] = left_arr[j:]

남아있는 다른 하나의 배열의 확인하지 못한 지점에서부터 끝까지를 array배열의 뒷부분에 채워넣습니다. 각각의 배열은 이미 정렬되어있는 상태이기때문에 크게 신경쓰지 않고 그냥 넣어주면됩니다. 이렇게하면 병합정렬 알고리즘이 완성됩니다! 

 

최종코드

N = int(input())

arr = []

for i in range(N):
    x = int(input())
    arr.append(x)


def merge_list(array):
    if len(array) <= 1:
        return

    mid = len(array) // 2
    left_arr = array[:mid]
    right_arr = array[mid:]

    merge_list(left_arr)
    merge_list(right_arr)

    i, j, k = 0, 0, 0

    while j < len(left_arr) and k < len(right_arr):
        if left_arr[j] < right_arr[k]:
            array[i] = left_arr[j]
            j += 1
        else:
            array[i] = right_arr[k]
            k += 1
        i += 1

    if j == len(left_arr):
        array[i:] = right_arr[k:]
    else:
        array[i:] = left_arr[j:]


merge_list(arr)

for i in arr:
    print(i)

 

참고자료

https://velog.io/@supergangho/4-Python-Onlogn-%EC%A0%95%EB%A0%AC%ED%80%B5-%EB%B3%91%ED%95%A9-%ED%9E%99