[C/C++] 퀵 정렬(quick sort) 원리부터 구현까지

퀵 정렬이란?

퀵 정렬(quick sort)은 배열의 요소를 정렬하기 위한 분할 정복 알고리즘의 일종으로, 1959년 토니 호어(Tony Hoare)에 의해 개발되었다. 퀵 정렬은 기준키를 기준으로 작거나 같은 값을 지는 데이터는 앞으로, 큰 값을 지는 데이터는 뒤로 가도록 하여 작은 값을 갖는 데어터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법이다.

 

예를 들어 다음과 같이 1부터 10까지의 수를 무작위로 섞어놓은 배열이 있습니다.

5 6 10 4 3 8 7 1 2 9

 

먼저, 적당한 피봇(pivot, 기준값)을 선택해야 합니다. 일반적으로 데이터의 총 평균값에 근접하는 값을 취하는데 편의상 가장 앞에 있는 값으로 하겠습니다. 그러면 여기서는 피봇이 5입니다.

 

피봇을 두고 왼쪽에서 오른쪽으로 탐색하여 피봇보다 큰 값을 선택합니다. 또한, 오른쪽에서 왼쪽으로 탐색하면서 피봇보다 작은 값을 선택합니다.

 

- - - - - - - - - - - - >      <- - - - - - - - - - - - -

피봇보다 큰 값 찾기       피봇보다 작은 값 찾기

 

 

왼쪽에서 탐색했을 때 피봇보다 큰 값은 6이고 오른쪽에서 탐색했을 때 피봇보다 작은 값은 2입니다. 이제 이 두 값을 교환해 줍니다.

5 6 10 4 3 8 7 1 2 9	//피봇5보다 큰 값 6, 피봇 5보다 작은 값 2 교환

5 2 10 4 3 8 7 1 6 9

 

이제 왼쪽은 10부터, 오른쪽은 1부터, 마찬가지로 피봇보다 큰 값과 작은 값을 각각 찾을 때까지 계속 이동하여 교환해 줍니다. 바로 10과 1은 각각 피봇보다 큰 값과 작은 값이므로 교환합니다.

5 2 10 4 3 8 7 1 6 9	//피봇5보다 큰 값 10, 피봇 5보다 작은 값 1 교환

5 2 1 4 3 8 7 10 6 9

 

왼쪽에서 탐색 인덱스와 오른쪽 탐색 인덱스가 만나거나 엇갈릴 때까지 진행합니다. 피봇보다 큰 값은 8, 피봇 보다 작은 값은 3입니다.

 

오른쪽에서 왼쪽으로 탐색 인덱스를 i라고 하고 왼쪽에서 오른쪽을 탐색 인덱스를 j라고 한다면 현재 i는 8을 j는 3을 가리키게 되는데 두 값은 엇갈렸습니다. 즉, i가 j보다 큰 값을 가지게 됩니다. 이때, j와 피봇을 바꿔주면 됩니다.

 

5 2 1 4 3 8 7 10 6 9	//피봇값 5와, j위치에 해당하는 3 교환

3 2 1 4 5 8 7 10 6 9

 

이제 원래 피봇인 5는 정렬이 끝나게 되고 5를 기준으로 3 2 1 4와 8 7 10 6 9 둘로 나뉘어서 가장 앞의 값인 3과 8을 각각 인덱스로 정해서 앞의 과정을 반복해주면 됩니다.

 

#include <stdio.h>

void qsort(int *arr, int start, int end){
	//분할된 원소가 0개이거나 1개 일때까지 함수 호출 
	if(start>=end){
		return;
	}
	
	int pivot = start;	//피봇은 첫 번째 원소 
	int i = pivot+1;	//i는 피봇 다음원소 
	int j = end;	//j는 마지막 원소 
	int temp;
	
	while(i<=j){
		//피봇 보다 큰 값 만날 때 까지
		while(i<=end && arr[i]<=arr[pivot]){
			++i;
		}
		//피봇 보다 작은 값 만날 때 까지
		while(j>start && arr[j]>=arr[pivot]){
			--j;
		}
		
		//위에서 계산된 i와 j가 만나거나 엇갈리면 종료
		if(i>=j) break;
		
		//두 원소 교환 
		temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	//피봇 정렬 완료 
	temp = arr[j];
	arr[j] = arr[pivot];
	arr[pivot] = temp;
	
	qsort(arr, start, j-1);	//피봇 중심으로 왼쪽부분 분할
	qsort(arr, j+1, end);	//피봇 중심으로 오른쪽부분 분할
	
}

int main(){
	
	int i;
	//1~10 무작위 배열
	int arr[10] = {5, 6, 10, 4, 3, 8, 7, 1, 2, 9};
	
	//배열, [0], [9]
	qsort(arr, 0, 9);
	
	//출력 
	for(i=0;i<10;++i){
		printf("%d ", arr[i]);
	}
	
	return 0;
}

 

결과값:

1 2 3 4 5 6 7 8 9 10

 

퀵 정렬의 원리는 복잡해 보이는데 선택 정렬, 버블 정렬과 비교하여 더 빠르다고 할 수 있습니다. 이유는 10개의 원소를 가진 배열을 정렬한다고 가정했을 때 10^2은 100입니다. 반면, 10을 5와 5로 나누게 되면 5^2 + 5^2 = 50입니다. 이처럼 분할하여 계산하게 되면 더 효율적입니다.

 

따라서 퀵 정렬은 피봇의 선택이 매우 중요합니다. 피봇 선택에 따라 시간 복잡도가 달라집니다.

 

 

퀵 정렬의 평균 시간 복잡도(or 빅오)는 O(N*logN)입니다.

 

 

퀵 정렬의 최악의 경우 시간 복잡도(or 빅오)는 O(N^2)입니다.