퀵 정렬(Quick Sort)

분할 정복 알고리즘의 대표적인 예시이며 피봇을 기준으로 정렬해 나가는 정렬 방법이다.

분할과정과 정복과정으로 나누어져 있으며, 피봇을 정한 뒤 피봇을 기준으로 작거나 큰것으로 나눠간다.
퀵소트의 피봇 선정 방식은 여러가지가 존재한다.

#include <iostream>
using namespace std;

int arr[10] = {10,5,4,6,2,3,7,9,1,8};
int num = 10;
void quickSort(int *arr, int start, int end) {
	if(start >= end) {
		return;
	}
	int key = start;
	int i = start + 1;
	int j = end;
	int tmp;
	while(i <= j) {
		while(arr[i] <= arr[key]) {
			i++;
		}
		while(arr[j] >= arr[key] && j > start) {
			j--;
		}
		if(i > j) {
			tmp = arr[j];
			arr[j] = arr[key];
			arr[key] = tmp;
		} else {
			tmp = arr[j];
			arr[j] = arr[i];
			arr[i] = tmp;
		}
	}
	quickSort(arr, start, j - 1);
	quickSort(arr, j + 1, end);
}

int main() {
	quickSort(arr, 0, num - 1);
	for(int i = 0; i < 10; i++)
		cout << arr[i] << " ";
}

위의 코드는 피봇을 왼쪽의 요소로 잡는 알고리즘이다.


퀵소트는 이름에서 알 수 있드시 매우 빠른 정렬 알고리즘에 속한다.
하지만 최악의 경우 n^2으로 작동할 여지가 있다.
아이러니하게도 최악의 경우는 배열이 이미 정렬 되어있을 때 발생한다.


이 문제를 해결하기 위해 피봇을 랜덤으로 선정하거나 중위법을 이용하는 방법, 작은 분할 범위의 정렬은 삽입정렬을 이용하는 방법등이 있다.

여담으로 C++ STL #include <algorithm> 라이브러리의 sort() 함수는 퀵소트를 기반으로 작성되었다.
(모든 경우에서 O(n log n)을 보장한다.)

algorithm	average	worst	best	space
quick	O(NlogN)	O(N^2)	O(NlogN)	O(logN)