[C++] 퀵 정렬 (Quick Sort)

원리

퀵 정렬 (Quick Sort) 정렬 원리는 다음과 같다.

 

 

퀵 정렬은 Divide and Conquer 방식을 사용한다.

따라서 재귀 함수를 사용하며, 종료 구문이 필요하다.

시간 복잡도는 O(n * Log n)에 해당한다.

효율적인 정렬 방법으로, 현재 가장 많이 사용하는 방식이다.

 

동일 메모리 값이 실시간으로 처리되는 점에서

Unstable Sort 기법으로 분류된다.

 

C++ algorithm 헤더 파일의 sort 함수가 퀵 정렬을 사용한다.

 

 

 

코드

#include <iostream>
#include <vector>

using namespace std;

void swap(int& a, int& b)
{
	int temp = a;
	a = b;
	b = temp;
}

void quick_sort(vector<int>& arr, int s, int e)
{
	if (s >= e)
		return;

	int pivot = s;
	int l = s + 1;
	int r = e;

	while (l <= r)
	{
		if (l <= e && arr[l] <= arr[pivot]) l++;
		if (r > s && arr[r] >= arr[pivot]) r--;

		if (l > r) 
			swap(arr[pivot], arr[r]);
		else
			swap(arr[l], arr[r]);
	}

	quick_sort(arr, s, r - 1);
	quick_sort(arr, r + 1, e);
}

int main()
{
	vector<int> arr = { 10, 1, 2, 3, 4, 5 };

	quick_sort(arr, 0, arr.size() - 1);

	for (auto n : arr)
		cout << n << '\n';

	return 0;
}