Divide and Conquer: 분할 정복 - 퀵 정렬

 

개념

배열을 둘로 분할하고 분할한 배열을 재귀 호출로 정렬하여 하나의 배열로 만든다는 점이 합병정렬과 비슷하지만, 좌/우를 균등분할하는 것이 아니다. pivot(기준 원소)을 선정하여 pivot보다 작은 원소는 모두 왼쪽 배열로, 크거나 같은 원소는 모두 오른쪽 배열로 가도록 분할한다.

출처: commons.wikimedia.org

* 위의 이미지에서 검은색 배경의 숫자가 pivot

 

특징

▪ 불안정 정렬

▪ 비교 정렬(값 비교에 기반한 정렬 알고리즘)

▪ 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 위치가 결정되기 때문에 반드시 끝나는 알고리즘이라는 것을 보장 가능

 

흐름

① pivot 선정

② [분할] pivot보다 작은 원소들이 앞에 오고, 뒤에는 값이 크거나 같은 모든 원소들이 오도록 배열을 둘로 분할

③ [정복] 부분 배열을 정렬(배열의 크기가 충분히 작지 않을 경우 순환 호출로 다시 분할 정복 적용)

④ [병합] 정렬된 부분 배열들을 하나의 배열로 합치기

 

재귀로 구현한 퀵 정렬(C언어)

#include <stdio.h>

void quickSort(int* data, int left, int right) {
	
	// 원소가 1개인 경우
	if (left >= right) {  
		return; 
	} 
	
	int pivot = left; 
	int i = pivot + 1;	// 왼쪽 시작 지점 
	int j = right;		// 오른쪽 시작 지점 
	
	int temp; 
	
	// 분할 과정
	while(i <= j) { 
		while(i <= right && data[i] <= data[pivot]) { 
			i++; 
		} 
		
		while(j > left && data[j] >= data[pivot]) {
			j--; 
		} 
		
		// 바꾸는 와중에 i가 j보다 커진 경우
		if(i > j) { 
			temp = data[j]; 
			data[j] = data[pivot];	// j번째 원소와 pivot 교체
			data[pivot] = temp; 
		}
		else { 
			// i번째, j번째 위치 바꾸기 
			temp = data[i]; 
			data[i] = data[j]; 
			data[j] = temp; 
		} 
		printf("\n");
	} 
	
	quickSort(data, left, j - 1);	// 왼쪽 배열에 대해 퀵 정렬 다시 적용
	quickSort(data, j + 1, right);	// 오른쪽 배열에 대해 퀵 정렬 다시 적용
} 

int main() { 
	int input[8] = { 15, 22, 13, 27, 12, 10, 20, 25 };
	
	printf("정렬 전 배열: ");

	for (int i = 0; i < 8; i++) {
		printf("%d ", input[i]);
	}

	quickSort(input, 0, 7);

	printf("\n정렬 후 배열: ");

	for(int i=0; i<8; i++) { 
		printf("%d ", input[i]); 
	} 
}

 

🔎 참고 블로그

▪ ehpub.co.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-c%EC%96%B8%EC%96%B4-3-3-2-%ED%80%B5-%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84/

▪ prosto.tistory.com/177