[알고리즘] 분할정복법 (Merge sort, Quick sort)

분할정복법

분할정복법이란 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할(Divide)하고, 각각의 문제들을 순환적으로 해결(정복, Conquer)하고, 작은 문제의 해들을 합병(Merge)하여 원래 문제에 대한 해를 구하는 방법이다.

분할정복법에는 합병정렬(merge sort), 퀵정렬(quick sort) 등이 있다.

1. Merge sort (합병 정렬)

---

• 합병 정렬의 작동 원리

1. 데이터가 저장된 배열을 절반으로 분할한다.
2. 순환적으로 배열을 분할 후 정렬한다.
3. 정렬된 두 개의 배열을 합쳐 전체를 정렬한다.

// 정렬되어 있는 두 배열을 합병(merge)하는 함수
void merge(int arr[], int p, int q, int r) {
	int i = p, j = q + 1, k = p;
	int* tmp = (int*)malloc(sizeof(int) * (r - p + 1));

	while (i <= q && j <= r) {
		if (arr[i] <= arr[j])
			tmp[k++] = arr[i++];
		else
			tmp[k++] = arr[j++];
	}
	while (i <= q)
		tmp[k++] = arr[i++];
	while (j <= r)
		tmp[k++] = arr[j++];
	for (int i = p; i <= r; i++)
		arr[i] = tmp[i];
}

// recoursion을 통한 mergesort 함수
void mergeSort(int arr[], int p, int r) {
	if (p < r) {
		int q = (p + r) / 2; // p와 q의 중간지점 계산
		mergeSort(arr, p, q); // 전반부 정렬
		mergeSort(arr, q + 1, r); // 후반부 정렬
		merge(arr, p, q, r); // 합병
	}
}

mergeSort를 순환함수로 구현하기 위해 배열을 합병하는 merge 함수와 mergeSort 함수로 나누어 구현한 코드이다.

합병정렬은 최선, 평균, 최악 모두의 경우에서 $O(n log n)$의 시간 복잡도를 갖는다. 배열을 분할하여 정렬하고 이를 병합하는 것을 반복할 때, 단계의 높이는 $O(log n)$이며 각 단계에서 정렬에 소요되는 시간은 배열의 길이인 $O(n)$이다.

따라서 합병정렬은 어떤 경우에도 $O(nlogn)$의 시간 복잡도를 가지며 이는 단계들의 높이에 비례한다는 것을 알 수 있다.

2. Quick sort (퀵 정렬)

---

• 퀵소트의 작동 원리

1. 배열에서 기준값(pivot)을 고른 후 pivot보다 작은 부분과 큰 부분으로 배열을 분할한다.
2. 분할된 각 부분을 순환적으로 정렬한다.
3. 추가적으로 합병이 필요하지는 않다.

pivot을 정하는 기준은 사용자의 설정에 따라 달라질 수 있다. 랜덤으로 pivot을 고를 수도 있으나 이는 효율성이 떨어지는 방법이다. 일반적으로 사용되는 pivot 선택 방법은 Median of Three Pivot(중간값 피봇)을 선택하는 것이다.

Median of Three Pivot

배열의 첫번째 값, 가운데 값, 마지막 값 중에서 크기의 중간값(median)을 피봇으로 선택한다.

void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      int pivot = arr[(left + right) / 2];
      int temp;
	  
      while (i <= j)
      {
        while (arr[i] < pivot)	i++; // arr[i] ≥ pivot 일 때까지, left에서 오른쪽 방향으로 탐색
        while (arr[j] > pivot)	j--; // arr[j] ≤ pivot 일 때까지, right에서 왼쪽 방향으로 탐색
		
        if (i <= j) // 큰 값이 작은 값보다 왼쪽에 있으면
        {
			// SWAP(arr[i], arr[j])
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
			
            i++;
            j--;
        }
      } 

    /* 재귀(recursion) */
    if (left < j)	quickSort(arr, left, j);
    if (i < right)	quickSort(arr, i, right);
}

소스코드 출처

퀵소트의 평균 시간 복잡도는 $O(n log n)$이다.

배열이 항상 절반으로 분할되는 최선의 경우 시간 복잡도는 $O(nlogn)$이다. 그러나 분할이 항상 한 쪽은 0개, 다른 쪽은 n-1개로 분할되는 최악의 경우 $O(n^2)$의 시간 복잡도를 가질 수도 있다.

참고자료
합병정렬(merge sort) / https://youtu.be/2YvFRAC8UTM
빠른정렬(quick sort) / https://youtu.be/hq4dpyuX4Uw