재시민

int partition(vector<int>& v, int left, int right) {
	int pivot, temp, low, high;
	low = left;
	high = right+1 ;
	pivot = v[left];
	
	do {
		do {
			low++;
		} while (low <= right && v[low] < pivot);// low right 만나지 않거나 같고, v[low] 값이 피봇 보다 작다면 반복
		do {
			high--;
		} while (high >= left && v[high] > pivot);// high left 만나지 않거나 같고, v[high] 값이 피봇보다 크다면 반복
		if (low < high) {
			swap(v[low], v[high]);
		}
	} while (low < high);

	swap(v[left], v[high]);
	return high;
}
void QuickSort(vector<int>& v,int left, int right) {
	if (left < right) {
		int q = partition(v, left, right);
		QuickSort(v, left, q - 1);
		QuickSort(v, q + 1, right);
	}
	
}

제자리성 : 제자리 정렬 (순환호출로 인해 제자리가 아니라고도 할 수 있음)

안정성 : 불안정 (swap)

시간 복잡도

평균시간 복잡도 = O(nlogn) (분할 과정이 트리와 비슷하여 트리의 높이 만큼 곱해진다.)

최악시간 복잡도 = O(n2)

알고리즘

1. low, high 값을 늘리고, 줄이면서, 설정된 피봇 값보다 크거나 작다면 멈춘다.

2. 이때 low < high 이면 v[low], v[high] 스왑

3. do-while 종료 후 기존의 피봇값과 high 값을 변경하여 피봇 재설정

4. 설정된 피봇값을 중심으로 두개로 분할히여 퀵소트 진행