가장 빠르다고 알려진 실제론 다른거 쓴답니다 퀵 정렬Quick Sort에 대해 다뤄봅니다.

퀵 정렬

기준 원소pivot을 정해서, pivot보다 작은 것은 좌측으로, 큰 것은 우측으로 정렬시키는 방식을 전개합니다(내림차순으로 간다면 반대로 수행해야겠죠?).

1. pivot 원소를 지정
2. 좌측 원소가 pivot보다 작거나 같을 때까지 left 인덱스 증가, 우측 원소가 pivot보다 클 때까지 right 인덱스를 감소시키고, left와 right 번째 원소 위치를 바꿔줍니다.
3. left < right 할때까지 1~2를 반복합니다.
4. 마지막에 pivot과 right 번째 원소를 바꿔주고 0 ~ right - 1과 right + 1 ~ end로 나눠서 해당 로직을 전개합니다.

4번으로 진입하고 나눠서 전개하기 직전 원소를 보면 right 인덱스를 기준으로 좌측은 항상 right 번째 원소보다 작고, 우측은 항상 right 원소보다 큰 것을 알 수 있어요.

즉, 해당 로직을 계속 나눠서 수행하다보면 결국 완전한 정렬을 수행하게 된다는 것을 알 수 있어요!

그림

특징

시간복잡도는 결론부터 말씀드리자면, 최선 및 평균은 $O(nlogn)$입니다.

배열의 개수가 n개라 가정하고 이를 $n^{k}$로 표현한다면, $n=2^{3}$일 경우, $n=2^{3}$ -> $n=2^{2}$ -> $n=2^{1} ...$ 순으로 줄어듭니다.

이를 일반화하게 되면 $n=2^{k}$일 경우 k=$logn$인 것을 알 수 있어요.

퀵 정렬은 이런 방식을 약 n회를 수행하기 때문에 평균 시간복잡도가 $O(nlogn)$가 되는겁니다.

하지만!

만약 주어진 배열이 정렬이 된 경우에 $O(n^{2})$이 되요. 그림으로 보면 아래와 같아요.

위 그림처럼, left 또는 right 인덱스가 치우쳐져서 n번의 비교를 거치고, 이를 n번 수행하게 되는거죠.

퀵 정렬Quick Sort은 따로 배열을 추가하지 않아 In-place하고, Unstable한 정렬입니다.

소스

#include <vector>

template<typename T>
class QuickSort
{
public:
	static void sort(vector<T>& arr)
	{
		quickSort(arr, 0, arr.size() - 1);
	}
private:
	static void quickSort(vector<T>& arr, int start, int end)
	{
		if(start >= end)
			return;

		int pivot = start;
		int left = start + 1;
		int right = end;
		while(left <= right)
		{
			while(left < end && arr[pivot] >= arr[left]) ++left;
			while(start <= right && arr[pivot] < arr[right]) --right;

			if(left < right)
				swap(arr[left], arr[right]);
			else
				swap(arr[pivot], arr[right]);
		}

		quickSort(arr, start, right - 1);
		quickSort(arr, right + 1, end);
	}
};

참고

Gyoogle님의 기술 블로그