[정렬 알고리즘] 퀵 소트(Quick Sort)

퀵 소트는 이름 그대로 빠른 성능을 제공하는 정렬 알고리즘입니다.

평균적으로 O(n log n)으로, 최악의 경우 O(n²)의 시간 복잡도를 보입니다.

기본적인 방식은 아래와 같습니다.

1. 리스트에서 원소를 한 개 선택하는데 이 원소를 피벗(Pivot)이라고 부릅니다.
   
2. 피벗이 선정되면 피벗보다 작은 값들은 피벗의 좌측에, 큰 값들은 우측에 위치시킵니다.
3. 피벗은 자신의 자리를 찾았으므로 고정되며 좌우의 작은 값들과 큰 값들을 다시 재귀로 반복합니다.

이런 식으로 피벗의 위치를 전부 찾아주게 되면 결과적으로 정렬된 리스트가 됩니다.

피벗은 다양한 방법으로 선택이 가능한데 보통 가장 앞의 원소나 가장 뒤의 원소를 선택해서 진행합니다.

다음 코드는 가장 뒤의 원소를 피벗으로 선택하는 퀵 소트 코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;

template <typename T>
size_t partition(T arr[], size_t low, size_t high)
{
	int pivot = arr[high];
	size_t i = low;

	for (size_t j = low; j < high; ++j)
	{
		if (arr[j] < pivot)
		{
			swap(arr[i++], arr[j]);
		}
	}
	swap(arr[i], arr[high]);
	return i;
}

template <typename T>
void quickSort(T arr[], size_t low, size_t high)
{
	if (low < high)
	{
		size_t pi = partition(arr, low, high);

		quickSort(arr, low, pi - 1);
		quickSort(arr, pi + 1, high);
	}
}

int main(void)
{
	int arr[] = { 13, 1, 5, 15, 9, 10, 12, 7, 6, 11, 4, 3, 2, 14, 8 };

	int n = sizeof(arr) / sizeof(arr[0]);
	quickSort(arr, 0, n - 1);
	for (int i : arr)
	{
		cout << i << " ";
	}
	cout << endl;

	return 0;
}

partition() 함수에서 피벗을 선택하고 피벗을 기준으로 작은 값들과 큰 값들을 좌우로 나눕니다.

partition() 함수가 리턴하는 값이 피벗의 위치입니다.

리턴을 하기 전의 swap(arr[i], arr[high]); 부분이 값들을 나누고 피벗이 정확한 위치를 찾는 부분입니다.

quickSort() 함수에서는 정렬이 된 피벗의 위치를 제외하고 좌측과 우측에 대해서 다시 quickSort()를 호출합니다.

모든 원소들이 위치를 찾으면 정렬이 완료됩니다.

퀵 정렬은 분할 정복(Divide and conquer) 방식으로 소팅을 진행합니다.

다른 정렬에 비해 성능 상의 이점이 많은 퀵 소트의 정렬 방식을 알아두는 것을 추천합니다.