퀵 정렬(Quick Sort)

개념 요약

• 분할 정복을 통해 주어진 배열을 정렬한다.
  • 분할 정복 : 문제를 2개의 문제로 분리하여 각각 해결하고 결과를 모아서 해결하는 전략이다.
• 분리할 때 비 균등하게 분할하여 해결한다.

 

---

정렬 과정

1. 배열 내의 하나의 원소를 고른다.(pivot을 고름)
2. pivot보다 작으면 pivot의 앞으로, pivot보다 크면 pivot의 뒤로 분리한다.
3. 1 -> 2의 과정을 분리된 상태에서 재귀적으로 반복한다.

 

---

코드

void	quick_sort(std::vector<int> &unsorted_array, int left, int right)
{
	//왼쪽값이 오른쪽 값보다 크다면 끝
	if (left >= right)
		return ;
	// 피봇과 왼쪽 인덱스 저장
	int	i = left, j = left, temp = 0;
	int	&pivot = unsorted_array[right];
	// 오른쪽 인덱스까지 루프
	for (; j < right; ++j)
	{
		// 피봇보다 작다면 swap
		if (unsorted_array[j] < pivot)
		{
			temp = unsorted_array[i];
			unsorted_array[i] = unsorted_array[j];
			unsorted_array[j] = temp;
			++i;
		}
	}
	// 피폿 교체
	temp = unsorted_array[i];
	unsorted_array[i] = pivot;
	pivot = temp;
	// 재귀
	quick_sort(unsorted_array, left, i - 1);
	quick_sort(unsorted_array, i + 1, right);
}

 

---

시간 복잡도

• 피봇을 매번 중간값을 잡은 경우(최선의 경우)에 $O(nlog_2n)$이다.
• 배열이 이미 오름차순 또는 내림차순으로 정렬되어있는 경우 $O(n^2)$이다.

 

---

공간 복잡도

• 주어진 배열 내에서 swap으로 정렬하므로 $O(n)$이다.

 

 

---

장단점

• 불필요한 데이터의 이동을 줄이고, 한번 결정된 피벗을 제외하기 때문에 동일 시간 복잡도를 가진 다른 정렬보다 빠르다.
• 불안정 정렬이며 이미 정렬돼있다면 오히려 비효율적이다.