분할 정복법 - Merge Sort, Quick Sort

알고리즘 ) 분할 정복법

알고리즘의 해결전략 Divide and Conquer를 분할 정복법이라고 합니다.

분할 정복법은 주어진 문제를 작은 사례로 나누어(Divide) 각각의 작은 문제들을 해결(Conquer)하는 방법입니다.

 

프랑스의 황제 나폴레옹이 전투에서 사용했던 훌륭한 전략에서 이름을 따왔다고 하네요.

나누어라, 그리고 정복하라.. 멋있는 말입니다...

 

Merge Sort

Best Case 시간복잡도 : O(n log n)

Worst Case 시간복잡도 : O(n log n)

분할 단계

array를 두 개의 subarrays로 나눕니다.

 

정복 단계

각각의 subarray가 충분히 작다면 바로 정렬 합니다.

그렇지 않다면 재귀를 통해 각각을 정렬합니다.

 

결합 단계

정렬된두 개의 subarray를 하나의 통합버전으로 만듭니다.

 

 

 

MergeSort 예시

 

 

 

 

Basic Operation

U라는 subarray와 V라는 subarray를 비교하는 연산

 

Best Case

U에 있는 모든 값들이 V에 있는 모든 값들 보다 작은 경우

 

 

 

 

Worst Case

subarray의 모든 값이 비교 연산을 해야지만 정렬된 배열 S에 값들이 할당되는 경우

 

MergeSort의 Worst Case 시간 복잡도 : θ (n log n)

 

 

QuickSort

Best Case 시간 복잡도 : O (n log n)

Worst Case 시간 복잡도 : O (n^2)

주어진 리스트에서 하나의 원소를 고르고, pivot item (피벗) 이라고 정합니다.

 

피벗 앞에는 피벗보다 값이 작은 값들이 오도록 하고,

피벗 뒤에는 피벗보다 값이 큰 값들이 오도록 피벗을 기준으로 리스트를 둘로 나눕니다.

 

나눈 두개의 리스트에 대해 재귀적으로 이 과정을 반복합니다.

리스트의 크기가 0이나 1이 될 때 까지 이 과정을 반복합니다.

 

(이미지 출처 : 위키백과)

 

 

 

 

 

 

 

 

피벗 아이템으로 정한 값이 나눈 리스트의 계속해서 맨 앞에 있거나 맨 뒤에 있는 경우

(최대값이나 최솟값으로 피벗을 계속해서 잡는 경우) Worst Case가 됩니다.

피벗을 기준으로 값이 한쪽으로 치우쳐지게 되는 현상이 발생해서 연산이 여러번 수행되게 됩니다.

 

즉 이미 정렬된 리스트에서 Quick Sort를 사용하면 최악의 경우가 발생하겠죠.

 

분할 정복법을 쓰면 안 되는 경우

1. 어떤 문제를 2개 이상으로 Divide 했는데, 각각의 크기가 원래 문제의 크기와 비슷할 때

 

2. 어떤 문제를 Divide 했는데, 그 문제의 크기만큼 작은 문제들로 나누어질 때