#들어가기
이번 포스팅에서는 합병 정렬(merge sort)
에 대해 알아보겠습니다.
#합병 정렬(merge sort)
합병 정렬(merge sort)
은 분할 정복법을 활용한 sort 방법입니다.
분할 정복법은 익히 들어본바와 같이 다음과 같습니다.
- 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
- 정복 : 각각의 작은 문제를 순환적으로 해결
- 합병 : 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함
그렇다면 이 분할정복법을 어떻게 활용해서 합병 정렬(merge sort)
을 할수 있을까요?
- 데이터가 저장된 배열을 절반으로 나눔
- 각각을 순환적으로 정렬
- 정렬된 분할된 리스트를 전체 배열로 합침
문자로 표현하니 조금 난해한 느낌이 있어 다시 그림으로 보겠습니다.
맨 밑에 있는 숫자들이 정렬을 해야하는 숫자들 입니다. 즉, 5-2-4-7-1-3-2-6이 있는 배열을 최대한 작게 나눈 다음 다시 합치는 과정을 그림에서 확인할 수 있습니다.
이제 수도 코드로 간단하게 표현해보겠습니다.
mergeSort(A[], p, r) { // A[p...r]을 정렬 if(p < r) then { q <- (p+r)/2 // 중간 지점을 찾음 mergeSort(A, p, q); // 앞 부분 정렬 mergeSort(A, q+1, r); // 뒷 부분 정렬 merge(A, p, q, r) // 합병 } } void merge(int data[], int p, int q, int r) { int i = p, j = q+1, k=p; int tmp[data.length()]; while(i <= q && j <= r) { if(data[i] <= data[j]) tmp[k++] = data[i++]; else tmp[k++] = data[j++]; } while(i <= q) tmp[k++] = data[i++]; while(j <= r) tmp[k++] = data[j++]; for(int i = p; i <= r; i ++) data[i] = tmp[i]; }
보시는 것과 같이 합병 정렬(merge sort)
은 추가적인 배열(tmp)이 필요합니다.
합병 정렬(merge sort)
의 시간 복잡도를 확인해본다면 O(nlogn) 입니다. 이는 합병 정렬(merge sort)
가 어떻게 동작하는가를 생각해본다면 쉽게 나올수 있습니다.
즉, 길이가 N인 배열을 계속 반으로 나누는 작업을 진행(O(logn))하면서 합병(O(N))을 수행하기 때문 시간 복잡도는 O(nlogn) 입니다.
#마치며
이로써 합병 정렬(merge sort)
의 정리를 마치겠습니다.