퀵정렬(QuickSort)

  우리들이 흔히 알고 있는 정렬 알고리즘인 선택 정렬, 버블 정렬, 삽입 정렬 알고리즘은 모두 시간 복잡도 O(N^2)을 가지는 알고리즘이었습니다. 사실 이러한 복잡도를 가지는 알고리즘은 데이터의 갯수가 10만 개만 넘어가도 일반적인 상황에서 사용하기가 매우 어려운 알고리즘입니다. 그렇기 때문에 더욱 빠른 정렬 알고리즘이 사용될 필요가 있습니다. 그 대표적인 빠른 알고리즘이 바로 퀵정렬 알고리즘입니다. 퀵정렬은 대표적인 '분할 정복' 알고리즘으로 평균 속도가 O(N * logN) 입니다. 

 

퀵 정렬은 하나의 큰 문제를 두개의 작은 문제로 분할하는 식으로 빠르게 정렬합니다. 더 쉽게 말하자면 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눕니다. 

 

"특정한 값을 기준으로 큰 숫자와 작은 숫자를 나누면 어떨까?"

예시를 통해서 알아보자.

 

일반적인 퀵 정렬에는 기준이 되는 값이 있습니다. 흔히들 이것을 피봇(pivot)이라고도 하는데, 보통 첫 번째 원소를 피봇 값으로 설정하고 사용합니다. 다음과 같이 3이라는 값이 먼저 피봇 값으로 설정이 되었다고 생각해 봅니다.

3  7  8  1  5  9  6  10  2  4

이 경우 3보다 큰 숫자를 왼쪽 부터 찾고, 3보다 작은 숫자를 오른쪽부터 찾습니다. 이 때 3보다 큰숫자로는 바로 7을 찾을 수 있고,  3보다 작은 숫자는 2를 찾을 수 있습니다. 이 때 작은 값의 인덱스가 큰 값의 인데스보다 크므로 7과 2를 교체해 줍니다.

3  2  8  1  5  9  6  10  7  4

이어서 큰값과 작은 값을 교체하여 다음과 같이 바뀌었습니다.

위의 과정과 똑같이 3보다 큰 숫자를 왼쪽 부터 찾고, 3보다 작은 숫자를 오른쪽부터 찾습니다. 이 때 3보다 큰숫자로는 바로 8을 찾을 수 있고,  3보다 작은 숫자는 1를 찾을 수 있습니다. 이 때 작은 값의 인덱스가 큰 값의 인데스보다 크므로 8과 1를 교체해 줍니다.

3  2  1  8  5  9  6  10  7  4 -- 엇갈리는 경우

이어서 큰값과 작은 값을 교체하여 다음과 같이 바뀌었습니다.

위의 과정과 똑같이 진행하려고 하는데, 1과 8이 엇갈려버린 상황이 나오게 됩니다.

이때 작은 값의 인덱스가 큰 값의 인덱스보다 작으므로 피봇 값과 작은 값의 위치를 바꿉니다. 

즉, 3과 1을 교체해 줍니다.

1  2  3  8  5  9  6  10  7  4

 따라서 위와 같이 구성이 되었고, 3은 정렬이 완료된 상황입니다. 기존의 피봇 값이였던 3을 기준으로 왼쪽과 오른쪽을 나누어 재귀적으로 퀵 정렬을 진행해줍니다. 왼쪽에서 피봇은 1이 되고, 오른쪽에서 피봇의 값은 8이 됩니다.

1  2  3  8  5  9  6  10  7  4

이어서 왼쪽과 오른쪽 각각 피봇을 설정해준 모습입니다.

1  2  3  8  5  9  6  10  7  4

  이 경우 1보다 큰 숫자를 왼쪽부터 찾고, 1보다 작은 숫자를 오른쪽부터 찾습니다. 이 때 1보다 큰 숫자로는 바로 10을 찾을 수 있고, 1보다 작은 숫자는 찾지 못해서 결국 1까지 도달합니다.

1  2  3  8  5  9  6  10  7  4

  1이 정렬이 되고, 피봇 값을 2로 설정해 줍니다. 그리고 위와 같이 반복해주면, 2도 정렬이 완료됩니다.

1  2  3  8  5  4  6  10  7  9

이 경우 8보다 큰 숫자를 왼쪽 부터 찾고, 8보다 작은 숫자를 오른쪽부터 찾습니다. 이 때 8보다 큰숫자로는 바로 10을 찾을 수 있고,  8보다 작은 숫자는 7를 찾을 수 있습니다. 이 때 작은 값의 인덱스가 큰 값의 인데스보다 크므로 10과 7를 교체해 줍니다.

1  2  3  8  5  4  6  7  10  9 -- 엇갈리는 경우

이어서 큰값과 작은 값을 교체하여 다음과 같이 바뀌었습니다.

위의 과정과 똑같이 진행하려고 하는데, 7과 10이 엇갈려버린 상황이 나오게 됩니다.

이때 작은 값의 인덱스가 큰 값의 인덱스보다 작으므로 피봇 값과 작은 값의 위치를 바꿉니다. 

즉, 8과 7을 교체해 줍니다.

1  2  3  7  5  4  6  8  10  9

이어서 피봇값과 작은 값을 교체하여 다음과 같이 바뀌었습니다.

1  2  3  7  5  4  6  8  10  9

따라서 위와 같이 구성이 되었고, 8은 정렬이 완료된 상황입니다. 기존의 피봇 값이였던 8을 기준으로 왼쪽과 오른쪽을 나누어 재귀적으로 퀵 정렬을 진행해줍니다. 왼쪽에서 피봇은 7이 되고, 오른쪽에서 피봇의 값은 10이 됩니다.

 

위와 같이퀵 정렬은 순환적으로 수행하면서 반으로 쪼개 들어가면서 분할 정복식으로 정렬이 완료됩니다.

 

"전체과정을 소스코드로 표현하면 다음과 같습니다."

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int number = 10;
int data[] = { 1,10,5,8,7,6,4,3,2,9 };

void quicksort(int *data, int start, int end) {
	if (start >= end) {//원소가 1개인 경우 그대로 두기
		return;
	}

	int pivot = start;//피봇은 첫번째 원소
	int i = start + 1;
	int j = end;
	int temp;

	while (i <= j) {//엇갈릴 떄까지 반복
		while (i <= end && data[i] <= data[pivot]) {
			//피봇보다 큰값을 만날 때까지
			i++;
		}
		while (j > start && data[j] >= data[pivot]) {
			//피봇보다 작은 값을 만날 떄까지
			j--;
		}
		if (i > j) {//현재 엇갈린 상태면 피봇과 교체
			temp = data[j];
			data[j] = data[pivot];
			data[pivot] = temp;
		}
		else {//엇갈리지 않았다면 i와 j를 교체
			temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}
	
	quicksort(data, start, j - 1);
	quicksort(data, j + 1, end);
}

int main() {
	quicksort(data, 0, number - 1);
	for (int i = 0; i < number; i++) {
		printf("%d ", data[i]);
	}
	return 0;
}

 

start는 정렬하는 부분 집합의 첫번째가 되고, end는 마지막이 됩니다.
그래서 start가 end보다 크거나 같다는 소리는 기본적으로 원소가 한개인 경우라고 할 수 있습니다. 이 경우에는 바로 return 해주면 됩니다.

이제 피봇값을 잡아주면 됩니다. 피봇이라는 변수로 선언해줍니다.피봇은 첫번째 원소로 설정해줍니다.

i는 start + 1로 설정해둔다. 피봇 보다 하나 큰값으로 설정해서 하나씩 이동하며 피봇 보다 큰값을 찾는 역할을 수해하기 때문에 start+1로 설정해둡니다.

j는 마지막부터 하나씩 작은 값을 찾아야 하기 떄문에 end값을 넣어줍니다.

while(i<=j)
i가j보다 작거나 같을 때만 수행하는 반복문이고, 엇갈리지 않았을 때까지만반복을 수행하고, 엇갈리는 경우에 반복문을 빠져 나오게됩니다.

while(data[i] <= data[key] && i <= end){
    i++;
}
i가 key값보다 작다면 오른쪽으로 한칸씩 이동해줍니다.
다시 말해, 피봇값보다 큰값을 만날 떄까지 이동시켜준다는 의미입니다. 

while(data[j] >= data[key] && j > start){
     j--;
}
마찬가지로, 피봇값보다 작은 값을 만날때 까지 j를 줄여줍니다.
 j>start 부분은 j가 9부터 출발을 하는데 1보다 작은 값이 없기 떄문에 더 넘어가면 안되니깐 범위를 정해줍니다. 

if(i>j)
엇갈린경우에는 외쪽에 있는 값과 피봇값과 교체를 하는데 스왑으로 간단하게 바꿔 줄 수 있습니다.

엇갈리지 않았다면, 큰값과 작은값 두개의 값만 바꿔 주면 됩니다. j와 i를 바꿔 주면 됩니다.

결과적으로 데이터가 엇갈려서 바깥으로 바껴나오는 경우에는 그 피봇값을 기준으로 왼쪽과 오른쪽을 나눠서 각각 퀵정렬을 수행해 주는겁니다.

재귀적함수를 이용한 방식으로 구현할 수 있다.

약점 하나가 있는데 퀵정렬은 피봇값을 설정하는 것에 따라 최악의 경우 시간 복잡도가 On^2 나올수 있다. 이미 정렬되어 있는 경우에 발생합니다.

왜냐하면, 피봇을 잡았을 때 작은 값을 찾지 못해 정렬이 하나밖에 안됩니다. 
분할 정복의 이점을 상용하지 못하고, 10번 9번.. 반복한다는 점에서 n^2 이 나오게 됩니다. 

그럼에도 불구하고, 대부분의 경우에는 가장 빠릅니다. c언어 정렬 라이브러리 함수도 퀵정렬 기반입니다.