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

 

 

퀵 정렬

  퀵 정렬은 기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해서 정렬하는 알고리즘이다. 평균 시간 복잡도는 O(nlogn)이며 최악의 경우 O(n^2)의 시간 복잡도를 가진다. 

 

  퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 또한 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 이러한 이유로 퀵소트(빠른정렬)라는 이름의 기원이 되었다. 그리고 퀵 정렬은 정렬을 위해 평균적으로 O(log n)만큼의 memory를 필요로한다. 이는 재귀적 호출로 발생하는 것이며, 최악의 경우 O(n)의 공간복잡도를 보인다. (위키백과 발췌)

 

 

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

 

 

 

 

기준점(Pivot) - 첫 번째 원소 채택

  pivot을 첫 번째 원소로 둘 경우의 코드이다. left는 pivot의 다음 원소부터 체크를 시작하고, right는 가장 끝의 원소부터 체크를 시작한다. 가르키는 원소 값이 pivot의 값보다 작거나 클 경우 멈추고, left와 right 위치를 비교하여 Swap을 진행한다. 그러고 pivot과 피벗보다 작은 값을 Swap한다. 이후 start 위치와 end 위치를 조정하면서 이 과정을 반복하면 된다.

 

void QuickSort_start(vector<int>& arr, int start, int end)
{
	if (start >= end)
		return;
	int pivot = start;
	int left = start + 1, right = end;
	while (left <= right)
	{
		while (left <= end && arr[left] <= arr[pivot]) left++;
		while (right > start && arr[right] >= arr[pivot]) right--;
		if (left <= right)
			Swap(arr, left, right);
	}
	Swap(arr, pivot, right);
	QuickSort_start(arr, start, right - 1);
	QuickSort_start(arr, right + 1, end);
}

 

 

 

 

 

 

기준점(Pivot) - 가운데 원소 채택

  pivot을 가운데 원소로 둘 경우의 코드이다. left는 start고, right는 end와 같다. left와 right를 pivot과 비교하여 위치를 옮겨주고, left가 right보다 작다면(교차되지 않았다면) 둘을 Swap한다. 이후 left와 right의 범위를 확인하며 퀵 정렬을 반복하면 된다. 

void QuickSort_middle(vector<int> &arr, int start, int end)
{
	if (start >= end)
		return;
	int pivot = (start + end) / 2;
	int left = start, right = end;
	while (left <= right)
	{
		while (arr[left] < arr[pivot]) left++;
		while (arr[right] > arr[pivot]) right--;
		if (left <= right)
		{
			Swap(arr, left, right);
			left++, right--;
		}
	}
	if (left < end)
		QuickSort_middle(arr, start, left);
	if (right > start)
		QuickSort_middle(arr, right, end);
}

 

 

 

 

 

 

main의 코드

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	srand(time(NULL));

	vector<int> nums = { 6, 8, 9, 4, 2, 1, 0, 5, 7, 3 };
	//random_shuffle(nums.begin(), nums.end());

	for (auto a : nums)
		cout << a << " ";

	QuickSort_middle(nums, 0, nums.size() - 1);

	cout << endl;
	for (auto a : nums)
		cout << a << " ";
}

 

 

 

 

 

 

참고

퀵 정렬 - 위키백과, 우리 모두의 백과사전