이 글에서는 정렬된 두 배열 합치기 연산으로 정렬을 해 봅시다. merge sort는 divide and conquer 알고리즘으로 작동하는데요. 머지 소트가 conquer 과정에서 수행하는 로직입니다.
정렬된 두 배열에서 제일 작은 수 찾기
무작위로 섞어진 배열에서 가장 작은 수를 찾는 것은 쉽지 않습니다. 하지만 오름차순으로 정렬된 배열에서 가장 작은 것을 찾는 것은 쉽습니다. 정렬된 두 배열에서는요? 어렵지 않게 해결할 수 있습니다. 예를 들어, 오름차순으로 정렬된 두 배열이 있다고 해 보겠습니다.
A와 B는 오름차순으로 정렬되었으므로 아래가 성립합니다.
- 1은 연노란색으로 칠한 영역보다는 작거나 같습니다.
- 3은 연파란색으로 칠한 영역보다는 작거나 같습니다.
그런데, 1은 3보다 작습니다. 그렇다면 1은 연파란색으로 칠한 영역보다는 작거나 같을 겁니다. 따라서, 배열 A와 B에서 가장 작은 수는 1입니다. 1이 아니라면, 두 배열이 오름차순으로 정렬되었다는 전제에 맞지 않습니다. 즉, 오름차순으로 정렬된 배열 A, B에 있는 수들 중 가장 작은 수는 A의 1번째 수와 B의 1번째 수 중 작은 것입니다.
이 사실을 이용하면, 정렬된 두 배열 합치기 알고리즘을 설계할 수 있습니다.
저는 정렬된 두 배열을 합쳐서, 오름차순으로 정렬된 결과를 만들 거에요. 배열 A와 배열 B의 길이는 3입니다. p1과 p2는 각 배열의 1번째 원소를 가리키고 있습니다. p1은 A의 1번째 원소를 가리키고 있습니다. p2는 B의 1번째 원소를 가리키고 있습니다. p1이 가리키고 있는 수 1은 p2가 가리키고 있는 수 0보다 큽니다. 따라서, B에서 뽑아 옵니다.
R의 1번째 원소에 0이 들어갑니다. 이는, 제일 작은 원소가 0이였기 때문입니다. 그 다음에 어떤 일이 일어날까요? 저는 배열 B에서 원소 하나를 뽑았습니다. 따라서, p2를 하나 증가시켜서, 다음 원소를 보게 합니다.
p1이 1입니다. p2는 하나 증가해서 2입니다. p1은 A의 1번째 원소를, p2는 B의 2번째 원소를 가리키고 있는 셈입니다. 노란색으로 표시한 원소 1이 파란색으로 표시한 2보다 작습니다. 따라서, 이번에는 B가 아니라 A에서 원소를 뽑아옵니다.
따라서, R의 2번째 원소는 1이 됩니다. 여기까지 로직을 정리해 봅시다.
오름차순으로 정렬된 두 배열 A와 B, 결과 배열 R에 오름차순으로 합쳐야 한다고 해 봅시다.
- p1은 A의 1번째 원소를 p2는 B의 1번째 원소를 가리킵니다.
- p1이 가리키는 수가 p2가 가리키는 수보다 작다면
- p1이 가리키는 원소를 R에 넣습니다.
- p1을 하나 증가시켜서 A의 다음 원소를 가리키게 합니다.
- 그렇지 않으면
- p2가 가리키는 원소를 R에 넣습니다.
- p2를 하나 증가시켜서 B의 다음 원소를 가리키게 합니다.
이 로직으로 수행되게 됩니다. 그런데, A의 끝에 도달하거나, B의 끝에 도달하면 어떻게 될까요?
남은 원소 처리하기
그러면 설명한 로직이 끝났을 때, 둘 중 한 배열에 아직 R에 넣지 않은 수가 항상 존재할까요? 그럴 수 밖에 없습니다. 가장 마지막에 넣어진 원소가 항상 있기 때문입니다.
x > y인 경우를 봅시다. 이 경우, x가 선택되기 전에 y가 선택될 겁니다. A에 아직 추가 안 한 원소가 있는 셈입니다.
그게 아니라면, x가 y보다 작거나 같은 경우입니다. 이 경우, B에 아직 결과 배열에 추가 안 한 원소가 있습니다. 이런 건 어떻게 처리해야 할까요? 로직 1을 돈 다음에, A에 있는 원소들을 다 추가했는지, 그렇지 않았는지 while loop를 돌면서 검사하면 됩니다.
위의 경우, 0, 1, 2, 3, 3 순으로 결과 배열에 추가되었습니다. B에 아직 추가가 안 된 원소가 남아 있습니다. p2는 B의 3번째 원소를 가리키고 있습니다. B의 끝을 가리키고 있지 않기 때문에, R의 마지막에 7을 넣습니다.
이 부분은 이 글에 있는 memcpy 등으로 처리하면 편합니다. 특정 배열의 영역을 다른 배열의 영역으로 한꺼번에 복사하는 것이기 때문입니다.
코드
이제 간략한 코드를 보도록 하겠습니다.
예제 1번 프로그램입니다. 길이가 10인 배열 A와 B가 있습니다. 그리고, 결과 배열 R이 있네요. merge는 배열 A와 배열 A의 길이, 배열 B와 배열 B의 길이, 결과 배열을 넘깁니다.
이제, merge 함수를 보겠습니다. while 구문이 3개 있는데요. 1번째 while loop는 로직 1을 의미합니다. 2번째와 3번째 loop는 배열 tar1과 tar2에서 아직 R에 넣지 않은 수들을 보면서 결과 배열 ret에 넣습니다.
시간 복잡도는 tar1의 배열 길이가 n이고, tar2의 배열 길이가 m이라면 O(n+m)이 됩니다.