[Algorithm] Quick Sort

• 분할 정복(divide and conquer) 방법 을 통해 주어진 배열을 정렬
• 분할 정복 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
• 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬

Implementation

void quickSort(int* arr, int start, int end) {
	if (start >= end) return;

	int pivot = start;
	int i = pivot + 1;
	int j = end;
	int temp;

	while (i <= j) {
		while (i <= end && arr[i] <= arr[pivot]) {
			i++;
		}

		while (j > start && arr[j] >= arr[pivot]) {
			j--;
		}

		if (i > j) {
			temp = arr[j];
			arr[j] = arr[pivot];
			arr[pivot] = temp;
		}
		else {
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	quickSort(arr, start, j - 1);
	quickSort(arr, j + 1, end);
}

• Time Complexity
  • 평균의 경우(Average cases) : T(n) = O(nlog₂n)
  • 최악의 경우(Worst cases) : T(n) = O(n^2) - 정렬하고자 하는 배열이 오름차순 정렬되어있거나 내림차순 정렬되어있는 경우
• Space Complexity : O(n)
• Execution Time (sec) : 0.005 (원소 30000개 기준)

장점

• 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환
• 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

단점

• 불안정 정렬(Unstable Sort) 이다.
• 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

C++ 코드

---

ref :
퀵정렬