퀵 정렬(Quick sort)

이번에는 평균적으로 매우 빠른 수행 속도를 보장하는 정렬 방법인 퀵 정렬에 대해 알아보겠다.

 

퀵 정렬(quick sort)?

퀵 정렬은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 이 정렬 방법은 분할-정복법(divide and conquer)을 사용하고, 합병 정렬과 달리 리스트를 균등하지 않게 분할한다. 여기서 분할-정복법이란 문제를 작은 문제들로 분리하여 각각 해결하고  결과를 모아서 문제를 해결하는 전략이다. 그리고 분할-정복법은 대게 순환 호출을 이용하여 구현한다.

 

이제 퀵 정렬이 어떻게 이뤄지는지 살펴보자. 먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다. 여기서는 리스트의 첫 번째 요소를 피벗으로 하자. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮기고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮긴다. 결과적으로 피벗을 중심으로 왼쪽은 피벗보다 작은 요소들로 구성되고, 오른쪽은 피벗보다 큰 요소들로 구성된다. 이 상태에서 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬된다.

 

퀵 정렬이 피벗을 기준으로 두 개의 리스트로 나누는 과정

그러면 퀵 정렬은 어떻게 피벗을 기준으로 나누어진 왼쪽 부분 리스트와 오른쪽 부분 리스트를 정렬할까? 여기서 순활이 사용된다. 부분 리스트에서 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정이 되풀이 된다. 이 과정은 부분 리스트를 더 이상 분할할 수 없을 때까지 반복된다.

 

퀵 정렬 알고리즘 개념

퀵 정렬은 다음의 단계들로 이루어진다.

• 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
• 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정봅 방법을 적용한다.
• 결함(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
• 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)은 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시끝난다는 것을 보장할 수 있다.

퀵 정렬 알고리즘 예제

배열에 5, 3, 8, 4, 9, 1, 6, 2, 7이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

퀵 정렬 알고리즘 예제

퀵 정렬 알고리즘 구현

#include <iostream>

using namespace std;


void printArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
		cout << a[i] << " ";
	cout << endl;
}


void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int partition(int* a, int left, int right)
{
	int low = left;
	int high = right+1;
	int pivot = a[left]; // 피벗 설정

	do {	// 왼쪽 리스트에서 피벗보다 큰 레코드 선택
		do {
			low++;
		} while (low <= right && a[low] < pivot);
		do {	// 오른쪽 리스트에서 피벗보다 작은 레코드 선택
			high--;
		} while (high >= left && a[high] > pivot);

		if (low < high)	// 선택된 두 레코드 교환
			swap(a[low], a[high]);
	} while (low < high);	// 인덱스 low와 high가 엇갈리지 않는한 반복 

	swap(a[left], a[high]);	// 인덱스 high가 가리키는 레코드와 피벗값을 교환
	return high;
}

// 퀵정렬 알고리즘을 이용해 배열의 left ~ right 항복들을 오름차순으로 정렬하는 함수
void quickSort(int* a, int left, int right)
{
	if (left < right) // 정렬 범위가 2개 이상인 경우
	{
		int q = partition(a, left, right); // 좌우로 분할
		quickSort(a, left, q - 1); // 왼쪽 부분리스트를 퀵 정렬
		quickSort(a, q + 1, right); // 오른쪽 부분리스트를 퀵 정렬
	}
}

int main()
{
	int a[] = { 7,33,35,9,44,23 };
	int len = sizeof(a) / sizeof(int); 

	printArray(a, len);
	quickSort(a, 0, len-1);
	printArray(a, len);

	return 0;
}

 

퀵 정렬의 복잡도 분석

레코드의 개수 n이 2의 거듭제곱이라고 가정하고 퀵 정렬에서의 리스트 분할이 항상 리스트의 가운데에서 이루어진다고 가정하면 합병 정렬의 복잡도 분석과 마찬가지로 n개의 레코드를 가지는 리스트는 n/2, n/4, n/8,...,n/2^k의 크기로 나누어질 것이다. 크기가 1이될 때까지 나누어지므로 n/2^k=1일 때까지 나누어질 것이고 따라서 k=log_2⁡n개의 패스가 필요하게 된다. 각각의 패스에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어지므로 퀵 정렬은 비교 연산을 총 nlog_2⁡n번 실행해야 하여 O(nlog_2⁡n) 알고리즘이 된다.

퀵 정렬에서의 최선의 경우

최악의 경우는 리스트가 계속 불균형하게 나누어지는 것이다. 이미 정렬된 리스트에 대하여 퀵 정렬을 실행하는 경우를 생각해보자. 이 경우 리스트의 첫 번째 레코드를 피벗으로 설정하면, 왼편 리스트가 텅 비게 되는 불균형 분할이 연속해서 이루어진다.

퀵 정렬에서의 최악의 경우

이 경우 레코드의 수만큼 총 n번의 패스가 실행되고, 각 패스에서 n번의 비교가 이루어지게 되므로 비교 연산을 n^2번 실행하게 된다. 따라서 최악의 경우 퀵 정렬은 O(n^2)의 시간 복잡도를 가지게 된다.

정리

퀵 정렬의 평균적인 경으의 시간 복잡도는 O(nlog_2n)으로 나타난다. 특히 다른 O(nlog_2n)의 정렬 알고리즘과 비교하였을 때도 가장 빠른 것으로 나타났다. 이는 퀵 정렬이 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐 아니라, 한번 결정된 피벗들이 추후 연산에서 제외되는 특성들 때문이다.

퀵 정렬은 속도가 빠르고 추가 메모리 공간을 필요로 하지 않는 등의 장점이 있는 반면에 정렬된 리스트에 대해서는 오히려 수행 시간이 더 많이 걸리는 등의 단점도 가진다. 이러한 불균형 분할을 방지하기 위하여 피벗을 선택할 때 크기 순의 중간 값을 선택하는 방법이 많이 사용된다.