퀵정렬

#include <iostream>
#include <vector>

using namespace std;

vector<int> quickSort(vector<int> v)
{
	if (v.size() <= 1)
		return v;

	auto pivot = v.begin();
	vector<int> left;
	vector<int> right;

	for (auto it = ++v.begin(); it != v.end(); ++it)
	{
		if (*pivot > *it)	
			left.push_back(*it);

		else
			right.push_back(*it);
	}
	
	// 재귀!
	left = quickSort(left);
	right = quickSort(right);

	// 합치기!
	left.push_back(*pivot);
	left.insert(left.end(), right.begin(), right.end());

	return left;

}

최선 - Ω(nlogn) 

평균 - Θ(nlogn)

최악 - O(n^2)

 

퀵정렬

정렬하려는 수들 중 하나를 랜덤하게 고름( pivot )

pivot을 기준으로 작은 수와 크거나 같은 수를 나눔 (left, right)

 

나뉜 두 수들의 배열에서 다시 한번 pivot을 정하고

또 나눔 또또 나눔.. 

 

나누려는 배열의 크기가 1이 됐을때 

left, pivot, right 순으로 합침

 

나뉘었던 것들이 다시 합쳐지면서 정렬이됨