[알고리즘] 분할 정복 알고리즘(Divide-and-Conquer) - 퀵 정렬(quick sort)

분할 정복에 대한 설명은 https://cuckoobird.tistory.com/153 을 참고해주세요.

 

퀵 정렬

퀵 정렬은 피봇(pivot)이라 일컫는 배열의 원소(숫자)를 기준으로 피봇보다 작은 숫자들은 왼편으로, 피봇보다 큰 숫자들은 오른편에 위치하도록 분할하고, 피봇을 그 사이에 놓습니다. 퀵 정렬은 분할된 부분문제들에 대해서도 위와 동일한 과정을 순환으로 수행하여 정렬합니다.

피봇은 분할된 왼편이나 오른편 부분에 포함되지 않습니다.

피봇이 60이라면, 60은 [20, 40, 10, 30, 50] 과 [70, 90, 80] 사이에 위치하게 됩니다.

초기 배열이 { 6, 3, 11, 9, 12, 2, 8, 15, 18, 10, 7, 14 } 인 배열을 예시로 설명하겠습니다.

피봇을 중간에 있는 값으로 설정했습니다. (0 + 11) / 2 = 5 이므로 A[5] = 2 가 피봇이 됩니다. (인덱스는 5)

2보다 작은 값이 없으므로 아무 변동없이 다음으로 진행됩니다. 

if(p == left) QuickSort(A, p + 1, right);

피봇이 가장 왼쪽에 있게 될 경우를 대비하여 QuickSort 함수에 넣은 코드입니다. 가장 왼쪽에 있을 경우에 왼쪽 + 1 부터 검사를 합니다.

 

새로운 순환을 떼어내어 다시 봅니다. left + 1 부터 right 까지 피봇인 8보다 작은 수는 왼쪽으로, 큰 수는 오른쪽으로 보내야하기 때문에 8보다 작은 수와 큰 수를 교환합니다.

그리고 피봇은 알맞은 자리에 들어갑니다. 알맞은 자리는 마지막으로 교환된 곳의 사이가 됩니다. high와 low가 엇갈리는 곳인 high에 넣습니다. 결과는 다음과 같습니다.

그리고 이전 피봇인 4 인덱스를 제외한 1~3을 살펴봅니다.

피봇은 (1 + 3) / 2 = 2로 합니다. 그리고 마지막 시행 까지 하면 저렇게 되겠네요

위 알고리즘을 코드로 짰습니다.

package Algorithm.DivideAndConquer;

public class QuickSort {
	public static void main(String[] args) {
		int[] A = { 6, 3, 11, 9, 12, 2, 8, 15, 18, 10, 7, 14 };
		
		QuickSort(A, 0, A.length - 1);
		
		for(int i = 0 ; i < A.length ; i++) {
			System.out.print(A[i] + " ");
		}
	}
	
	static void QuickSort(int[] A, int left, int right) {
		if(left >= right) return;
		
		int p = partition(A, left, right);
		
		if(p == left) {
			QuickSort(A, p + 1, right);
		} else if(p == right) {
			QuickSort(A, left, p - 1);
		} else {
			QuickSort(A, left, p - 1);
			QuickSort(A, p + 1, right);
		}
	}
	
	public static int partition(int A[], int left, int right) {
		int pivot = (left + right) / 2;
		swap(A, left, pivot);
		
		int low = left + 1;
		int high = right;
		
		while(true) {
			while(low <= high && A[low] <= A[left]) low ++;
			while(low <= high && A[high] >= A[left]) high --;
			
			// 피봇보다 큰 인덱스 low값과 작은 인덱스 high값을 바꿈
			if(low < high) {
				swap(A, low, high);
			} else {
				// 피봇을 알맞은 자리에 놓음
				
				// 피봇의 값이 high 값보다도 작을 경우
				if(A[left] <= A[high]) {
					return left;
				// 피봇의 값이 high 값보다 큰 경우
				} else {
					swap(A, left, high);
					return high;
				}
			}
		}
	}
	
	public static void swap(int A[], int x, int y) {
		int tmp = A[x];
		A[x] = A[y];
		A[y] = tmp;
	}
}

 

최악의 경우를 시간 복잡도로 따져보자면,

 { 6, 3, 11, 9, 12, 2, 8, 15, 18, 10, 7, 14 }  이 배열일 경우에, 항상 가장 작은 값 또는 큰 값이 피봇이 될 경우를 보면 됩니다.

pivot = 2 일 때 : [6, 3, 11, 9, 12, 8, 15, 18, 10, 7, 14] 와 각각 1회 비교 - 11회

pivot = 3 일 때 : [6, 11, 9, 12, 8, 15, 10, 7, 14] 와 각각 1회 비교 - 10회

...

총 비교 횟수는 11 + 10 + .. + 1 = 66 이 됩니다.

 

즉, 퀵 정렬의 최악 경우 시간 복잡도는 n개의 데이터가 있다고 했을 때, (n-1)(n) / 2 = O(n^2)가 됩니다.

 

더 빠르게 할 수 있는 방법은 없을까요? 정답은 피봇에 있습니다. 피봇을 설정하는 방법을 달리함으로써 속도를 향상시킬 수 있습니다. 피봇으로 가장 작은 숫자 또는 가장 큰 숫자가 선택되는 경우에 한 부분으로 치우치는 분할을 야기하게 되기 때문입니다.

 

피봇을 선정하는 방법은 다음과 같습니다.

• 랜덤하게 선정하는 방법
• 3 숫자의 중앙값으로 선정하는 방법(Median-of-Three)
  : 가장 왼쪽 숫자, 중간 숫자, 가장 오른쪽 숫자 중에서 중앙값을 피봇으로 정합니다.
  :  { 6, 3, 11, 9, 12, 2, 8, 15, 18, 10, 7, 14 } 의 경우에, 6, 2, 14 숫자 중에서 중앙 값인 6을 피봇으로 정합니다.
• Median-of-Medians(Tukey's Ninther)
  : 3 등분한 후 각 부분에서 가장 왼쪽 숫자, 중간 숫자, 가장 오른쪽 숫자 중에서 중앙값을 찾은 후, 세 중앙값들 중에서 중앙값을 피봇으로 정합니다.
  :  { 6, 3, 11, 9, 12, 2, 8, 15, 18, 10, 7, 14 }  의 경우에, {  6, 3, 11, 9 }, { 12, 2, 8, 15 }, { 18, 10, 7, 14 } 세 등분으로 나눈다면, {  6, 3, 11, 9 } 에서는 6, 11, 9 의 중앙값인 9, { 12, 2, 8, 15 } 에서는 12, 8, 15의 중앙값인 12, { 18, 10, 7, 14 }에서는 18, 7, 14 의 중앙값인 14를 추출하고, 9, 12, 14 의 중앙값인 12를 추출하여 피봇으로 정합니다.
  이는 실제 중앙값인 9 혹은 10에 아주 근접합니다.

하지만 피봇 선정 자체에 시간을 많이 쏟지 않도록 주의해야합니다.

 

위에 설명한 방법 중 두번째 방법인 3 숫자의 중앙값으로 선정하는 방법(Median-of-Three) 을 사용하여 다시 코드를 짜보았습니다.

package Algorithm.DivideAndConquer;

public class QuickSort {
	public static void main(String[] args) {
		int[] A = { 6, 3, 11, 9, 12, 2, 8, 15, 18, 10, 7, 14 };
		
		QuickSort(A, 0, A.length - 1);
		
		for(int i = 0 ; i < A.length ; i++) {
			System.out.print(A[i] + " ");
		}
	}
	
	static void QuickSort(int[] A, int left, int right) {
		if(left >= right) return;
		
		int p = partition(A, left, right);
		
		if(p == left) {
			QuickSort(A, p + 1, right);
		} else if(p == right) {
			QuickSort(A, left, p - 1);
		} else {
			QuickSort(A, left, p - 1);
			QuickSort(A, p + 1, right);
		}
	}
	
	public static int partition(int A[], int left, int right) {
		int pivot = medianOfThree(A, left, right);
		swap(A, left, pivot);
		
		int low = left + 1;
		int high = right;
		
		while(true) {
			while(low <= high && A[low] <= A[left]) low ++;
			while(low <= high && A[high] >= A[left]) high --;
			
			// 피봇보다 큰 인덱스 low값과 작은 인덱스 high값을 바꿈
			if(low < high) {
				swap(A, low, high);
			} else {
				// 피봇을 알맞은 자리에 놓음
				
				// 피봇의 값이 high 값보다도 작을 경우
				if(A[left] <= A[high]) {
					return left;
				// 피봇의 값이 high 값보다 큰 경우
				} else {
					swap(A, left, high);
					return high;
				}
			}
		}
	}
	
	public static void swap(int A[], int x, int y) {
		int tmp = A[x];
		A[x] = A[y];
		A[y] = tmp;
	}
	
    // 3 숫자의 중앙값으로 선정하는 방법(Median-of-Three)
	public static int medianOfThree(int[] A, int left, int right) {
		int mid = (left + right) / 2;
		
		if((A[left] >= A[mid] && A[left] <= A[right]) || (A[left] <= A[mid] && A[left] >= A[right])) return left;
		else if((A[mid] >= A[left] && A[mid] <= A[right]) || (A[mid] <= A[left] && A[mid] >= A[right])) return mid;
		else return right;
	}
}