퀵소트

퀵소트는 O(nlogn)을 가지는 정렬 알고리즘으로 최대 O(n^2)과 같다고 한다.
정렬 방법은 다음과 같다.
1. pivot(기준값)을 정한다.
2. 왼쪽부터 pivot보다 작은 원소를 찾는다.(i)
3. 오른쪽부터 pivot보다 큰 원소를 찾는다.(j)
4. 두개가 모두 존재한다면 그 위치를 바꾼다.
5. 2,3,4 반복 후 더 이상 할 수 없다면 j와 pivot의 위치를 바꾼다.
6. pivot을 기준으로 다시 왼쪽과 오른쪽을 나누어 정렬을 시작한다.
해서 6번은 재귀함수를 이용하기로 했다.

void quicksort(int* data, int start, int end)
{
	if (start >= end) // 없으면 무한루프에 빠짐
		return;
	int pivot = start;
	int i = pivot + 1;
	int j = end;
	while (i <= j)
	{
		while (data[i] <= data[pivot] && i <= end) i++;
		while (data[j] >= data[pivot] && j >= start + 1) j--;
		if (i >= j) //서로 교차한 경우  pivot 과 j를 교환
		{
			int temp = data[j];
			data[j] = data[pivot];
			data[pivot] = temp;
		}
		else // 그렇지 않다면 i와 j를 교환
		{
			int temp = data[j];
			data[j] = data[i];
			data[i] = temp;
		}
	}

	quicksort(data, j + 1, end);
	quicksort(data, start, j - 1);
}