[알고리즘] 분할 정복 - 퀵 정렬

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

---

퀵 정렬

개요

　퀵(quick) 정렬은 주요한 연산의 평균 실행 시간을 최적화하는 것을 목표로 삼는 정렬 방법이다. 병렬 정합이 큰 규모의 데이터 세트에 대한 정렬에 초점을 맞춘 것과는 대조적으로, 퀵 정렬은 분할 정복 전략을 통해 입력 배열을 작은 서브 배열로 분해하고, 각각의 서브 배열을 독립적으로 정렬한 다음, 이들을 다시 결합하여 전체적으로 정렬된 배열을 생성하는 방식을 사용한다. 이러한 접근법에서 퀵 정렬의 핵심 연산은 바로 분할이다.

---

본문

　퀵 정렬은 다음과 같은 단계로 수행된다.

1. 분할(Divide): 배열에서 특정 원소를 피벗으로 선택하고, 이를 기준으로 입력 배열을 두 개의 부분 배열로 나눈다.
2. 정복(Conquer): 피벗을 제외한 두 부분을 재귀적으로 퀵 정렬한다.
3. 결합(Combine): 재귀적으로 1단계와 2단계를 반복한다.

 

　예를 들어, {5, 6, 7, 3, 1, 9}라는 원소가 있다면 피벗으로 5를 골라 정렬하면 다음과 같은 과정을 거치게 된다.

 

 

　이러한 퀵 정렬은 평균적으로 O(Nlog(N))의 시간 복잡도를 가진다. 이는 다수의 정렬 알고리즘 중에서 가장 효율적인 시간 복잡도다. 또한 퀵 정렬은 in-place 알고리즘으로, 주어진 배열 내에서 작업을 수행하므로 추가적인 메모리 요구량이 없다. 물론, 최악의 경우 시간 복잡도가 O(N^2)이 된다는 점은 퀵 정렬의 한계다.

 

---

구현

　지금부터 퀵 정렬을 구현해보도록 하겠다. 

 

#include <iostream>
#include <vector>

template <typename T>
auto partition(typename std::vector<T>::iterator begin,
	typename std::vector<T>::iterator end)
{
	auto pivot = *begin;
	auto left = begin + 1;
	auto right = end;

　퀵 정렬의 1단계인 '분할'을 구현할 partition() 함수다. 피벗 원소, 벡터의 시작과 마지막 원소를 초기화한다. 

 

	while (true)
	{
		while (*left <= pivot && std::distance(left, right) > 0)
			left++;

		while (*right > pivot && std::distance(left, right) > 0)
			right--;

		if (left == right)
			break;

		else
			std::iter_swap(left, right);
	}

　첫 번째 while문에서 벡터의 첫 번째 원소부터 시작하여 피벗보다 큰 원소를 찾고, 두 번째 while문에서 벡터의 마지막 원소부터 시작하여 역순으로 피벗보다 작은 원소를 찾는다. 만약 left와 right가 같다면 바꿀 원소가 없다는 의미이므로 반복을 종료하고, 아닌 경우엔 left와 right를 바꾼다(피벗을 기준으로 두 그룹을 분할하기 위해). 

 

	if (pivot > *right)
		std::iter_swap(begin, right);

	return right;
}

　피벗 원소를 최종적으로 올바른 위치로 이동시키는 과정이다. 즉, 주어진 벡터가 분할되어 피벗보다 큰 원소는 오른쪽 부분에 위치하게 되고, 피벗보다 작거나 같은 원소는 왼쪽 부분에 나타나게 하였다.

 

template <typename T>
void quick_sort(typename std::vector<T>::iterator begin,
	typename std::vector<T>::iterator end)
{
	if (std::distance(begin, end) >= 1)
	{
		auto partition_it = partition<T>(begin, end);
		quick_sort<T>(begin, partition_it - 1);
		quick_sort<T>(partition_it, end);
	}
}

　퀵 정렬을 벡터에 하나 이상 원소가 있을 때, 재귀적으로 호출하게 하였다.

 

int main()
{
	std::vector<int> v{ 5, 6, 7, 3, 1,9 };

	std::cout << "정렬 전:";
	for (const auto& val : v)
		std::cout << val << " ";
	std::cout << std::endl;

	std::cout << "정렬 후:";
	quick_sort<int>(v.begin(), v.end() - 1);
	for (const auto& val : v)
		std::cout << val << " ";
	std::cout << std::endl;
}

출력

 

총합본

#include <iostream>
#include <vector>

template <typename T>
auto partition(typename std::vector<T>::iterator begin,
	typename std::vector<T>::iterator end)
{
	auto pivot = *begin;
	auto left = begin + 1;
	auto right = end;

	while (true)
	{
		while (*left <= pivot && std::distance(left, right) > 0)
			left++;

		while (*right > pivot && std::distance(left, right) > 0)
			right--;

		if (left == right)
			break;

		else
			std::iter_swap(left, right);
	}

	if (pivot > *right)
		std::iter_swap(begin, right);

	return right;
}

template <typename T>
void quick_sort(typename std::vector<T>::iterator begin,
	typename std::vector<T>::iterator end)
{
	if (std::distance(begin, end) >= 1)
	{
		auto partition_it = partition<T>(begin, end);
		quick_sort<T>(begin, partition_it - 1);
		quick_sort<T>(partition_it, end);
	}
}

int main()
{
	std::vector<int> v{ 5, 6, 7, 3, 1,9 };

	std::cout << "정렬 전:";
	for (const auto& val : v)
		std::cout << val << " ";
	std::cout << std::endl;

	std::cout << "정렬 후:";
	quick_sort<int>(v.begin(), v.end() - 1);
	for (const auto& val : v)
		std::cout << val << " ";
	std::cout << std::endl;
}

---

요약

퀵 정렬
1. 정의: 분할 정복을 이용하여 정렬을 하는 방식
2. 특징
　a. 평균 시간 복잡도가 O(Nlog(N))으로 매우 빠름 (하지만 최악의 경우 O(N^2)
　b. 분할 / 정복 / 결합의 단계로 이루어짐