알고리즘 4장 - 합병 정렬 -

알고리즘 4장

- 정렬 문제 : 합병 정렬 -

 

정렬 문제는 n개의 숫자들의 배열을 입력으로 받게 되면 입력된 숫자의 배열이 특정 조건을 만족하도록 다시 나열한 결과를 출력으로 나타내는 문제이다. 이번 장에서는 정렬 문제 중에서 합병 정렬에 대해서 학습할 것이다.

합병 정렬은 합병을 이용한 정렬 알고리즘이다. 합병은 두 개의 내용을 합치는 것을 의미한다. 두 개의 정렬된 배열이 주어졌을 때, 정렬된 하나의 배열로 합병을 하는 방법이다. 예를 들어서 <1, 5, 6, 8> 과 <2, 4, 7, 9>라는 두 개의 배열이 있다고 가정하자. 각각의 배열들은 오름차순으로 배열이 정렬되어 있다. 이 두 배열을 사용하여 하나의 배열인 <1, 2, 4, 5, 6, 7, 8, 9>으로 정렬을 하는 방법이 합병 정렬이 된다. 여기서 중요한 점은 두 개의 배열이 우선적으로 정렬이 되어 있기 때문에 가장 작은 수가 왼쪽에 존재한다는 것이다. 따라서 모든 수를 비교하는 것이 아니라 왼쪽에서 오른쪽으로 두 개의 배열을 비교하면서 하나의 배열을 만들면 된다.

위의 예시를 조금 더 상세히 살펴보자. 두 배열은 오름차순으로 이미 정렬되어 있다. 따라서 앞에서 말했듯 왼쪽에서부터 비교를 해 나갈 것이다. 먼저 왼쪽 배열의 가장 왼쪽 값인 1과 오른쪽 배열의 왼쪽 값인 2를 비교한다. 이 때 1이 더 작은 수이므로 1을 새로 만들 배열의 맨 왼쪽에 정렬하게 된다. 이 후 2와 5를 비교하게 된다. 5는 왼쪽 배열에서 두 번째로 작은 수이기 때문이다. 이 때 2가 더 작은 수 이므로 새로운 배열에 2가 1 다음의 위치에 정렬된다. 이 후 5와 4의 값을 비교한다. 이 때 4가 더 작은 값이므로 4를 새로운 배열에 넣고 다시 5와 7을 비교한다. 이렇게 계속 비교를 하면서 작은 값은 새로운 배열에 넣고 그 다음의 숫자와 비교를 하는 과정을 거친다. 이러면 새로운 배열은 두 배열을 합친 오름차순의 배열로 만들어지게 된다.

합병 정렬의 수행시간을 살펴보게 되면 두 개의 정렬된 배열의 길이로 나타낼 수 있다. 두 개의 정렬된 배열의 길이가 각각 n1, n2 라고 한다면 각 배열의 모든 값이 한 번씩은 통과되어 새로운 배열에 들어가야 하므로 (n1 + n2)의 수행시간이 발생하게 된다.

합병 정렬은 크기가 커서 풀기 어려운 하나의 문제를 크기가 작아서 풀기 쉬운 여러 개의 문제로 바꾸어서 푸는 방법이라고 할 수 있다. 이런 방법을 divide-and-conquer approach라고 한다. n개의 크기의 배열을 쪼갠 후 작은 배열로 만들어 정렬을 수행한 후 합병 정렬을 통해 하나의 정렬된 배열로 합쳐주는 과정을 말할 수 있다. 이를 Pseudo Code로 표현하면 다음과 같다. A는 n개의 숫자가 들어 있는 배열이고, p는 첫 번째 index 값, r은 마지막의 index 값을 의미한다. p<r 인 경우는 배열의 숫자가 하나 이상이면 참이 되게 된다. q는 전체 배열에서 반이 되는 지점을 의미하게 된다. 이를 계속 반복하여 배열 안에 값이 하나만 될 때까지 처음 A의 배열을 쪼개게 된다.