퀵정렬(Quick sort)

참고 블로그 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

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

퀵 정렬은 분할 정복 알고리즘의 하나로서, 평균적으로 매우 빠른 수행 속도를 가지는 정렬 방법

퀵 정렬 알고리즘 특징
- 합병 정렬(merge sort)과 달리 리스트를 비 균등하게 분할
- 분할 정복 알고리즘
    - 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
    - 분할 정복 방법은 재귀 함수를 이용하여 구현

퀵정렬 과정
1. 리스트에서 한 요소(index)를 선택한다. 이렇게 선택한 원소를 피벗(pivot)이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들을 모두 피벗의 왼쪽으로 옮겨지고, 피벗보다 큰 요소들은 피벗의 오른쪽으로 옮겨진다.
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
3-1. 분할된 부분 리스트에 대하여 재귀 함수를 이용하여 정렬을 반복한다.
3-2. 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
4. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
4-1. 리스트의 크기가 0이나 1이 될 때까지 반복한다.

퀵 정렬 단계
- 분할 : 입력 배열을 피벗을 기준으로 비 균등하게 2개의 부분 배열로 분할 ( 퀵 정렬 과정 2번 참조 )
- 정복 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 재귀 함수를 이용하여 다시 분할 정복 방법을 적용
- 결합 : 정렬된 부분 배열들을 하나의 배열에 합병
- 순환 호출이 한 번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장한다.

퀵 정렬 장점
- 평균적으로 속도가 빠르다.
--> 시간 복잡도가 평균적으로 O(nLog2 n)을 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
- 병합 정렬과 다르게 추가 메모리 공간을 필요로 하지 않는다.
--> 퀵정렬은 O(logn)만큼의 메모리를 필요로 한다.

퀵 정렬 단점
- 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행 시간이 더 소요된다.

퀵 정렬 코드

#include <iostream>

#define MAX_SIZE	9
#define SWAP(x,y,temp) ((temp) =(x), (x)= (y), (y)=(temp))

using namespace std;

int partition(int list[], int left, int right)
{
	int pivot, temp;
	int low, high;

	low = left;
	high = right + 1;
	pivot = list[left];

	do {
		do {
			low++;
		} while (low <= right && list[low] < pivot);

		do {
			high--;
		} while (high >= left && list[high] > pivot);

		if (low < high)
		{
			SWAP(list[low], list[high], temp);
		}
	} while (low < high);

	SWAP(list[left], list[high], temp);

	return high;
}

void quick_sort(int list[], int left, int right)
{
	if (left < right)
	{
		int q = partition(list, left, right);

		quick_sort(list, left, q - 1);
		quick_sort(list, q + 1, right);
	}
}
int main(void)
{
	int nSize = MAX_SIZE;
	int list[MAX_SIZE] = { 5,3,8,4,9,1,6,2,7 };

	quick_sort(list, 0, nSize - 1);

	for (int i = 0; i < nSize; i++)
	{
		printf("%d ", list[i]);
	}
	return 0;
}