정렬 알고리즘 : 병합 정렬

1. 병합 정렬 : 이해와 구현

 

병합 정렬이란 분할 정복 이라는 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법입니다. 분할 정복이란, 말 그대로 복잡한 문제를 복잡하지 않은 문제로 분할하여 정복하는 방법을 뜻합니다. 단 분할해서 정복했으니 정복한 후에는 결합의 과정을 거쳐야 합니다.

이러한 방법을 근거로 기본 원리를 설명하면 다음과 같습니다.

8개의 정렬되지 않은 데이터가 있다고 가정했을 때, 동시에 정렬하는 것 보다 이를 둘로 나눠서 4개의 데이터를 정렬하는 것이 쉽고, 또 이들 각각을 다시 한번 둘로 나눠서 2개의 데이터를 정렬하는 것이 더 쉽습니다.

 

 

병합 정렬의 전체적인 과정은 다음과 같습니다.

출처 : 위키디피아

---

쉽죠? 병합정렬은 아마 이해하기 쉬울껍니다.

위 과정을 오름차순 정렬을 기준으로 설명하고 있습니다.

 

이번엔 쫌 더 자세히 알아보겠습니다.

 

병합 정렬은 크게 분할의 과정과 병합의 과정으로 나뉘어져 있습니다.

1.1 분할의 과정

위 그림은 분할과 병합의 전체적 과정입니다.

시작해 볼까요?

정렬되지 않은 8개의 데이터가 있습니다.

절반으로 나뉩니다. 

각각을 또 절반으로 나눕니다.

또 각각을 절반으로 나눕니다. 나누는 과정은 더 이상 정렬 할 필요가 없을 때 까지 나눠야 합니다. 이로서 분할의 과정이 끝났습니다. 이제 병합의 과정을 거쳐야 합니다.

8과 2를 비교했을 때 8이 더 크므로 순서를 바꿔 줍니다. 이렇게 3과7, 1과5, 4와6 모두 처리를 해줍니다.

이제 좌측 4개의 값과 우측 4개의 값을 정렬하면서 병합을 해야 합니다. 아까 [2,8] [3,7] 이렇게 있던 두 쌍의 값을 4개로 병합을 해야 합니다.

1.  2와 3을 비교합니다. 2가 더 작으므로 2를 맨 좌측에 넣습니다.

2.  그럼 [ 8] [3,7] 이렇게 남습니다. 다시 3과 8을 비교합니다. 3이 더 크므로 3을을 넣습니다.

3.  그럼 [ 8] [ ,7] 이렇게 남고 현재 배열에 [2,3] 이렇게 저장되어 있습니다.

4.  다시 8과 7을 비교합니다. 7이 더 작으므로 7을 배열에 넣습니다. 그러면 배열에는 2,3,7 이렇게 저장됩니다.

5.  마지막 남은 8을 배열에 저장하면 좌측 2쌍의 값은 2,3,7,8 이렇게 합쳐집니다.

이렇게 좌측 2쌍의 병합의 과정이 끝났습니다. 우측도 이와 같은 방법으로 병합의 과정을 거치면 1,4,5,6, 이렇게 합쳐집니다.

마지막으로 2쌍의 4개 값 들을 하나로 합쳐줘야 합니다.

1.  2와 1을 비교합니다. 1이 더 작으므로 1을 배열에 저장합니다.

2.  그럼 [2,3,7,8] [ 4,5,6] 이렇게 값이 남습니다. 다시 2와 4를 비교합니다. 2가 더 작으므로 2를 배열에 저장합니다.

3.  그럼 [ 3,7,8] [ 4,5,6] 이렇게 됩니다. 다시 4와 3을 비교합니다. 3이 더 작으므로 3을 배열에 저장합니다.

4.  그럼 [ 7,8] [ 4,5,6] 이렇게 됩니다. 다시 4와 7을 비교합니다. 4가 더 작으므로 4를 배열에 저장합니다.

5 . 그럼 [ 7,8] [ 5,6] 이렇게 됩니다. 다시 7과 5를 비교합니다. 5가 더 작으므로 5를 배열에 저장합니다.

6.  그럼 [ 7,8] [ 6] 이렇게 됩니다. 다시 7과 6을 비교합니다. 6이 더 작으므로 6을 배열에 저장합니다.

7.  그럼 [ 7,8] [ ] 이렇게 됩니다. 7과 8을 비교합니다. 7이 더 작으므로 7을 배열에 넣습니다.

8.  마지막으로 남은 8을 배열에 저장합니다.

 

그럼 1 2 3 4 5 6 7 8 이렇게 정렬된 값이 나옵니다.

---

위의 과정을 코드로 살펴보겠습니다.

정렬되지 않은 배열이 있습니다. MergeSort 함수는 배열의 주소 값, 맨 좌우측 값을 매개변수로 받습니다. 

1. 병합 정렬은 재귀의 형태를 띄고 있습니다. 처음에 정렬되지 않은 배열을 가지고 MergeSort 함수가 호출이 됩니다.

 

2. 아까 설명한대로 중간지점을 기준으로 나뉜 후 나뉜 두 뭉탱이를 또다시 재귀적으로 분리합니다.

 

3. left < right 조건을 만족하지 않을 때 까지 재귀적으로 계속 MergeSort 함수를 호출합니다. 이 뜻은 더 이상 분리 할 수 없을 때 까지 분리한다는 뜻입니다.

 

4. 이러한 과정은 재귀적 호출이기 때문에 재귀호출 과정이 진행되는 사이 MergeTwoArea 함수는 계속 쌓이게 됩니다. 뭔 말이냐면

이런식으로 사각형 안에 사각형이 호출되고 또 그 안에 사각형이 호출되는 재귀적 과정 중

MergeTwoArea 함수가 사용되지는 않고 계속 쌓이고 있다는 소리입니다. 맨 안쪽 사각형이 값을 반환할 때 비로소 하나씩 껍질이 벗겨지듯이 MergeTwoArea 함수가 호출됩니다.

이번에는 MergeTwoArea 함수를 살펴보겠습니다. 전체적인 이 함수의 흐름은 다음과 같습니다.

 

1. 정렬 대상을 임시저장하기 위한 변수를 동적 할당합니다.

2.  분할을 하면서 left(fIdx), mid rIdx, right를 다음과 같이 선언해줍니다.

3. fldx가 mid보다 작고 rldx가 right보다 작을 동안 데이터를 비교하면서 배열인 sortArr에 담습니다. 

4.  만약 배열의 앞 부분이 모두 정렬되어 sorrArr로 이동되면 fldx는 mid값을 넘어가게 됩니다. 그럼 if 문 조건안으로 들어가 뒷 부분에 남은 데이터를 sorrArr로 이동시킵니다.

5. 그렇지 않고 만약 배열의 뒷 부분이 먼저 sorrArr로 이동되면 rldx값이 right를 넘어가게 됩니다. 그럼 else 부분으로 들어와 앞부분에 남은 데이터를 모두 sorrArr로 이동합니다.

6. 그럼 마지막으로 sortArr배열의 값을 원래의 배열에 다시 옮겨준 뒤 sortArr배열을 해제합니다.

참고로 이그림은 fldx mid rldx right 관계를 보여주기 위해 4개 4개 영역을 8개로 합치기 직전의 상태입니다.

처음으로 실행되는 MergeTwoArea 함수는 letf, mid가 인덱스 0을 가리키고 right는 1을 가리키게 됩니다. 이해 되셨죠?

이 부분이 그 코드입니다. 

이 부분이 아까 4,5,6 번의 설명 부분입니다.

---

1.2 병합정렬 : 성능평가

병합 정렬의 성능평가를 위해서 비교연산의 횟수와 이동연산의 횟수를 계산해 보겠습니다. 

병합정렬의 성능은 MergeSort 함수가 아닌, MergeTwoArea 함수를 이준으로 계산해야 합니다. 

코드를 보시면 알겠지만 실제 비교연산과 이동연산이 실제 정렬을 진행하는 MergeTwoArea 함수를 중심으로 진행되기 때문이죠!.

데이터 8개가 분할을 통해 각각 하나로 떨어져 있습니다. 하나가 두 개가 되고 두 개가 4개가되고 4개가 8개가 되는 3번의 병합의 과정을 거칩니다.

 

데이터 8개 -> 병합 3번

데이터 4개 -> 병합 2번

 

어디서 많이 보지 않았나요? 맞습니다. 데이터의 수와 병합과정이 log(2)n 번을 거쳐서 진행됩니다.

 

이번엔 비교횟수를 봅시다. 병합 1단계에서 8과 2가 2,8로 병합되는 과정은 실제 그림을 봤을 땐 1회로 보이지만 코드 레벨에서 보면 한번 비교를 해서 2를 앞에 넣고 다시 8을 비교하여 2옆에 넣는 2번의 비교과정을 거치게 해놨습니다. 

사실 빅오에서는 이러한 세세한 1회를 추가하여 비교연산을 계산하는 거는 결과에 큰 차이가 없습니다. 2단계에서도 마찬가지입니다. 1과 4의 비교, 4와 5의 비교 5와 6의 비교인 총 3번의 비교와 마지막 6을 비교하여 넣는 1회의 과정을 추가하여 총 4번으로 맞춘 것입니다.

 

그럼 1단계에서는 8과 2 3과 7, 1과 5, 4와 6 총 2개의 쌍 4개가 2번의 비교연산이 이뤄지고 총 8회의 연산이 일어납니다.

 

2단계에서도 2,8 과 3,7 의 비교연산 4회 + 1,5와 4,6의 비교연산 4회를 거쳐 총 8회의 비교연산이 일어납니다. 

3단계에서도 8회의 비교연산이 일어납니다.

정리를 해보면 정렬의 대상인 데이터의 수가 n개 일 때, 각 병합의 단계마다 최대 n번의 비교연산이 진행됩니다. 따라서 데이터의 수가 n개일 때 병합 정렬에서 진행되는 최대 비교연산의 횟수는 다음과 같습니다.

nlog(2)n

 

이번에는 이동연산에 대해서 살펴보겠습니다.

 

데이터의 이동이 발생하는 이유는 두 가지입니다.

1.임시 배열에 데이터를 병합하는 과정

2. 임시 배열에 저장된 데이터 전부를 원위치로 옮기는 과정

 

따라서 8과 2를 두 개로 병합하는 과정은 2를 임시 배열에 넣고 그다음 8을 임시배열에 넣고 다시 2를 원래 배열에 넣고 마지막을 8을 원래 배열에 넣는 총 4회의 이동연산이 일어납니다. 그럼 병합 1단계에서는 4*4=16회의 이동연산이 일어나게 되고 2단계에서도 8*2=16 회의 이동연산이 일어나게 됩니다. 3단계도 16회의 이동이 일어납니다.

 

따라서 병합 정려의 이동연산 횟수는 최악,최선의 경우에 상과없이 다음과 같습니다.

2nlog(2)n

데이터의 개수의 2배만큼 병합과정에서 이동연산이 일어납니다.

하지만 빅오에서 숫자 2는 무시할 수 있으므로 병합 정렬에서 이동연산에 대한 빅-오는 O(log(n)2) 이고 따라서 비교연산과 이동연산의 빅오는

O(log(n)2)

로 정리할 수 있습니다.