#12. 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

• 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬
• 분할 정복(divide and conquer) 방법을 통해 리스트 정렬
• 시간 복잡도 : O(n log n)    *최악의 경우 : O(n^2)

 

분할 정복(divide and conquer)

• 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
• 분할 정복 방법은 대개 순환 호출을 이용하여 구현

 

장점

• 속도가 빠르다.
• 추가 메모리 공간을 필요로 하지 않는다.

 

단점

• 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행 시간이 더 많이 걸린다.

---

알고리즘

 

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

 

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

---

코드

void quickSort(int arr[], int left, int right) {

	int i = left, j = right;
	int pivot = arr[(left + right) / 2];
	int temp;

	do
	{
		while (arr[i] < pivot)
			i++;
		while (arr[j] > pivot)
			j--;
		if (i <= j)
		{
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i++;
			j--;
		}
	} while (i <= j);

	/* recursion */
	if (left < j)
		quickSort(arr, left, j);

	if (i < right)
		quickSort(arr, i, right);
}

 

---

References

 

ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

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

gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog