[C++] 퀵 정렬 (Quick Sort)

이번 시간에는 퀵 정렬에 대해 알아보도록 하겠다.

 

 

 

 

저번 시간까지 배웠던 선택 정렬, 버블 정렬, 삽입 정렬 모두 시간 복잡도가 O(n ^ 2)였다.

이러한 복잡도를 가지는 알고리즘은 데이터의 갯수가 10만개만 넘어가도 일반적인 상황에서 사용하기가 매우 어려운

알고리즘이다. 그렇기 때문에 더욱 빠른 정렬 알고리즘이 필요하고, 대표적인 빠른 알고리즘이 퀵 정렬로,

O(N * logN)의 시간 복잡도를 가진다.

 

 

 

 

 

 

퀵 정렬(Quick Sort)는 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬한다.

특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다.

 

 

 

 

일반적으로 퀵 정렬에서는 기준값이 있고, 이를 피벗(pivot)이라고 하는데, 보통 첫 번째 원소를 피벗 값으로 설정하고 사용한다.

 

 

 

 

3 7 8 1 5 9 6 10 2 4

예를 들어 다음과 같은 배열이 있다고 하자.

 

 

 

3 7 8 1 5 9 6 10 2 4

피봇을 맨 앞의 3으로 잡고, 그 뒤로 쭉 왼쪽부터는 pivot보다 큰 것, 맨 오른쪽부터는 pivot보다 작은 것을 고른다.

이 경우에는 왼쪽에서는 7, 오른쪽에서는 2가 골라질 것이고, 그 둘을 바꾼다.

 

 

3 2 8 1 5 9 6 10 7 4

 

 

그 뒤로부터 다시 진행하면 왼쪽에서는 8, 오른쪽에서는 1이 선택될 것이고, 이제 이 둘을 바꾼다.

 

3 2 1 8 5 9 6 10 7 4

 

다시 진행해보면 3보다 큰 값은 8, 3보다 작은 값은 1인데 이제 이 둘은 서로 엇갈린 것을 볼 수 있다.

8이 1보다 왼쪽에 있지 않다.

 

 

이렇게 인덱스가 엇갈린 경우에는 가장 작은 값인 1과 pivot을 바꾼다.

 

1 2 3 8 5 9 6 10 7 4

 

 

이렇게 한 뒤에는 기준값이었던 3보다 왼쪽에 있는 것들은 다 3보다 작고, 3보다 오른쪽에 있는 것들은 다 3보다 크다.

즉, 3을 기준으로 왼쪽, 오른쪽 부분 집합으로 분할했다고 볼 수 있다.

 

 

이제는 3을 기준으로 왼쪽 집합인 1 2 와 오른쪽 집합인 8 5 9 6 10 7 4에 대해 다시 퀵정렬을 수행한다.

 

 

1 2 3 8 5 9 6 10 7 4

먼저, 왼쪽 집합의 경우에서 보면 역시나 맨 앞의 원소인 1을 피봇으로 두고,

이제 기준인 1부터 오른쪽을 보면서 자기보다 큰 값인 2를 선택하고, 자기보다 작은 것이 없으므로 자기 자신을

선택하게 된다. 이 상태에서는 또 엇갈린 것이기 때문에 1과 자기 자신을 바꾸므로 원래와 같다.

그 후 큰 값인 2를 피봇으로 또 수행하는데 그 결과도 1 2로 같다.

 

 

이제 3보다 작은 왼쪽 1 2는 정렬되었고, 피봇인 3까지 포함해서 1 2 3은 정렬이 완성된 것이고, 정렬이 완성된 부분은

보라색으로 표시하겠다.

 

 

1 2 3 8 5 9 6 10 7 4

다음으로, 오른쪽 집합의 경우에는 맨 앞의 원소인 8이 피봇이 된다.

왼쪽부터 8보다 큰 값인 9, 오른쪽부터 8보다 작은 값인 4를 선택하고, 바꾼다.

 

 

 

1 2 3 8 5 4 6 10 7 9

이제 다시 왼쪽부터 8보다 큰 값인 10, 오른쪽부터 8보다 작은 값인 7을 선택하고, 바꾼다.

 

 

 

1 2 3 8 5 4 6 7 10 9

이제 8보다 큰 값인 10과 8보다 작은 값인 7이 엇갈렸으므로 작은 값과 피봇인 8을 바꾼다.

 

 

 

1 2 3 7 5 4 6 8 10 9

이제 8을 기준으로 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 위치하게 되었다.

 

 

 

 

1 2 3 7 5 4 6 8 10 9

다시 피봇을 맨 앞의 숫자인 7로 두고 수행해나가자. 이제부터는 앞에서 진행했던 것과 똑같은 과정이므로 별다른 설명을 쓰지 않겠다. 

 

 

 

 

1 2 3 7 5 4 6 8 10 9 → 8의 왼쪽 집합인 7 5 4 6에서 피봇인 7보다 큰 건 없고, 작은 건 6

1 2 3 6 5 4 7 8 10 9  → 7 왼쪽으로 7보다 작은 값들, 오른쪽으로 7보다 큰 값들

 

이런 식으로 계속 진행하다보면 1 2 3 4 5 6 7 8 9 10으로 제대로 정렬된 배열을 볼 수 있을 것이다.

 

 

 

 

 

 

 

퀵 정렬은 이렇게 왼쪽과 오른쪽으로 나뉜다는 성질 때문에 기존의 정렬들보다 속도가 O(N * logN)으로 빠른 것이다.

직관적으로 보자면 1 2 3 4 5 6 7 8 9 10을 선택, 삽입, 버블 정렬로 보자면 N * N이었으니까 10 * 10 = 100이 걸리는데,

퀵 정렬은 1 2 3 4 5와 6 7 8 9 10으로 두 개로 나누므로 5 * 5 = 25와 5 * 5 = 25가 더해져서 50이 걸리는 것이다.

 

 

 

 

 

 

 

코드로 구현해보자면 아래와 같다.

#include <stdio.h>

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

void show() {
	for (int i = 0; i < number; i++)
		printf("%d ", array[i]);
}

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

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

	while (i <= j) { // 엇갈릴 때까지 반복
		while (i <= end && (array[i] <= array[pivot])) { // 피봇보다 큰 값을 찾을 때까지
			i++;
		}
		while (j > start && (array[j] >= array[pivot])) { // 피봇보다 작은 값을 찾을 때까지
			j--;
		}

		if (i > j) { // 엇갈린 상태. 피봇보다 작은 값과 피봇과 교체
			temp = array[j];
			array[j] = array[pivot];
			array[pivot] = temp;
		}
		else { // 엇갈리지 않았다면 i와 j를 교체
			temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}
	}

	QuickSort(array, start, j - 1);
	QuickSort(array, j + 1, end);
}

int main() {
	QuickSort(array, 0, number - 1);
	show();

	return 0;
}

 

 

 

 

 

퀵 정렬의 치명적인 단점은 피봇을 어떻게 설정하느냐에 따라 성능이 확 달라진다는 것이다.

최악 시간 복잡도는 O(N * N)이 되버리고, 그 예는 이미 정렬이 되어있는 경우가 있다.

 

 

그래서 알고리즘 대회에서 시간 복잡도를 O(N * logN)을 요구하는 경우 퀵 정렬을 사용하면 틀리는 경우가 있다고 한다.