[데이터 구조] 합병 정렬(Merge Sort)

대학원이든 회사이든 데이터 구조 문제는 어디에서도 빠지지 않는 질문인 것 같다. 

 

데이터 구조에서 Sorting관련 알고리즘도 많이 묻는 질문 중 하나인데, 지난 번에 퀵소트(Quick Sort)에 대해 알아본 적 있다.

 

https://aistudy9314.tistory.com/2?category=977992

[데이터 구조] 퀵소트(Quick Sort)

 

이번 게시글에서는 퀵소트와 비슷하게 "분할 정복 방식"을 이용하는 합병 정렬(Merge Sort)에 대해 알아보겠다.

---

1. 합병 정렬이란? 

합병 정렬의 과정

출처: https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

 

합병 정렬은 "존 폰 노이만"이라는 사람이 제안한 방법이며 분할(Divide), 정복(Conquer), 결합(Combine) 3단계로 이루어져 있는 정렬 알고리즘이다(정복과 결합은 거의 같이 일어난다고 보아서 실제로는 2단계).

• 분할: 배열을 2개의 부분 배열로 나누는 Section.
• 정복: 나눠진 부분 배열을 정렬하는 Section. 배열이 충분히 작지 않다면(보통 배열 크기가 1이 될 때까지) 재귀 함수를 통해 다시 분할 단계를 거친다.
• 결합: 정렬된 부분 배열들을 하나의 배열로 합쳐주는 Section.

또한 합병 정렬은 비교 기반 정렬 알고리즘이며, 안정 정렬이고, 분할 정복 알고리즘이라는 특징을 가진다. ㅎㅎ...뭔가 수식어가 많다. 하나씩 알아보자!

 

1.1 비교 기반 정렬

먼저 비교 기반 정렬 알고리즘은 말그대로 비교를 통해 Sorting이 이루어진다는 의미이다. 합병 정렬은 먼저 divide과정이 이루어지고, 나중에 합병과 동시에 정렬을 한다. 이 때, divide된 배열 또는 연결리스트끼리 비교를 하면서 정렬을 하기 때문에 비교 기반 정렬 알고리즘이라고 한다.

 

1.2 안정 정렬

안정 정렬이란, 반복(중복?)되는 요소가 있을 때(ex. 값) 입력과 동일한 순서로 정렬이 되는 것을 말한다. 이 말만 들으면 이해가 안 갈 수 있으니 위키에 나와있는 예를 참고해보자!

 

출처: https://ko.wikipedia.org/wiki/%EC%A0%95%EB%A0%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#%EC%A2%85%EB%A5%98

 

위의 예에서는 카드의 값을 기준으로 정렬이 이루어지고 있는데, 같은 값(5)을 가지지만 모양이 다른 두 카드가 있다. 여기서 알고리즘이 안정(Stable)하다면 입력된 요소의 순서(5(♥) 다음 5(♠))를 따라가고, 불안정(Not stable)하다면 입력 순서와 달라질 수 있음을 의미한다. 

 

합병 정렬의 과정을 살펴본다면 왜 안정 정렬인지 이해할 수 있을 것이다. 

 

1.3 분할 정복 알고리즘

분할 정복 알고리즘은 퀵소트에서도 설명한 적이 있다. 

 

하나의 큰 문제를 여러 작은 문제들로 쪼개어 해결한 다음에 그 결과들을 합쳐서 해결한다라는 의미이며 합병정렬 그 자체이다.(Divide 후, Merge)

 

2. 합병 정렬 과정

먼저 간단하게 글로 정렬 과정을 알아보고, 그림을 통해 완전히 합병 정렬을 정복해보자!

 

2.1  글로 알아보는 합병 정렬 알고리즘

1. 입력으로 정렬할 하나의 배열이 들어간다. 
2. 배열을 비슷한 크기의 두 배열로 나눈다.(Divide)
3. 나누어진 배열의 크기가 1이 될 때까지, 부분 배열들에 대해 1번과 2번 과정을 반복한다.
4. 나누어진 부분 배열들을 정렬(conquer)하면서 합쳐(merge)나간다.

 

2.2 그림으로 알아보는 합병 정렬 알고리즘

[분할(Divide)]

 

[정복(Conquer) 및 결합(Combine)]

 

그림을 보면 합병정렬이 대략 어떤 식으로 동작하는지 완벽히 이해했으리라 믿지만 간략하게 설명을 붙여보자면.

 

먼저 분할(Divide) 과정을 통해 배열을 작은 부분 배열들로 계속 나눈다. 

그리고 분할 과정이 끝나게 되면 나누어진 부분 배열들을 다시 결합해주는데 이 때 정렬도 같이 진행된다.

 

2.3 합병 과정

합병 과정은 결합과 정렬이 동시에 이루어진다 하였는데 어떻게 동작하는지 좀 더 자세히 알아보자.

 

분할 과정을 모두 마쳤다면 두 개씩 pair를 이루고 있을 것이다(또는 혼자 남아 있거나).

 

이 두 pair의 배열의 값들을 순차적으로 비교하여 작은 값을 새로운 배열(new)에 옮기게 되며, 둘 중에 한 배열이 더 이상 참조할 인덱스가 없다면 다른 배열의 남은 값들을 new배열에 모두 복사한다. 

 

그림으로 좀 더 쉽게 보자면,

 

 

Pair인 배열 1 [7, 9]와 배열 2 [4, 5]를 결합(Combine)하는 과정이다.

1. 배열 1의 첫 원소 7과 배열 2의 첫 원소 4를 비교, 7 > 4이므로 4를 새로운 배열에 저장.
2. 배열 1의 첫 원소 7과 배열 2의 다음 원소 5를 비교, 7 > 5이므로 5를 새로운 배열에 저장.
3. 배열 2가 더이상 참조할 수 있는 값이 없으므로 비교가 종료되고, 배열 1의 모든 값들을 새로운 배열에 저장.

 

3. 합병 정렬의 장단점

합병 정렬은 정렬 알고리즘 중에서 빠르고 성능이 좋은 방법 중에 하나로 퀵소트와 함께 실제 프로그램에 많이 사용되지만, 단점 또한 존재한다.

 

장점

합병 정렬의 가장 큰 장점은 안정 정렬 알고리즘이란 점이다. 입력 배열에 따른 결과가 항상 똑같기 때문에 프로그램의 안정성 면에서 우수하다 할 수 있다. 

 

단점

정렬과 결합 과정을 보면 알아차리겠지만, Sorting된 값을 넣을 임시 배열이 하나 필요하다. 이런 이유로 레코드가 매우 큰 경우에 메모리 소모도 심하고, 임시 배열로 이동하는 횟수도 많아져 시간적으로도 비효율적이다.

 

해결법

위의 단점을 해결하는 방법은 배열이 아닌 연결 리스트(Linked List)를 사용하는 것이다. node가 가르키는 구조체의 주소가 바뀌는 과정만 반복되므로 메모리 소모도 없으며 데이터의 이동도 무시할 수준이 된다.

 

4. 시간 복잡도

시간 복잡도는 다음과 같이 계산될 수 있다. 

 

먼저 분할(Divide)과정에서는 데이터의 이동과 비교 연산이 없기 때문에 계산에서 제외된다.

 

결합과 정렬 과정에서 비교 및 원소 이동 연산을 계산해야 하는데 글로 풀어쓰면 복잡하니 그림으로 알아보자.

 

먼저 divide이 끝나면 위와 같이 tree같은 구조가 형성이 되는데 각 depth에서 비교와 이동 연산이 일어난다. 배열의 크기는  n -> n/2 -> n/4 -> .... 로 최종적으로는 1의 배열들로 쪼개지는데, 이 과정의 횟수(depth)가 log(n)이 된다(예제에서는 $log_2(2^3)$이므로 3).

 

그 다음에는 각 depth당 비교 및 이동 연산이 이루어지며 위 그림을 참조하면 n번 연산이 이루어지는 것을 알 수 있다. 

 

따라서 최종 시간복잡도는 $n*(logn)$이 나오게 된다.

 

---

오늘은 퀵소트 친구, 머지소트(합병정렬)에 대해 알아보았다. 상대적으로 퀵소트보다 개념이 쉬웠다고 생각한다. ㅎㅎ 

 

요즘 데이터 구조를 다시 공부하고 있는데 차례 차례 정리해 나갈 예정이다.