[알고리즘] 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

특징

1. 불안정 정렬(Unstable Sort): 동일한 값에 대해 상대적인 순서가 유지되지 않을 수 있습니다.
2. 제자리 정렬(In-place Sort): 입력 배열 내에서 정렬이 수행되며, 추가적인 메모리를 사용하지 않습니다.
3. 분할 정복(Divide and Conquer): 큰 문제를 작은 문제로 분할하여 해결하는 방식을 사용합니다.
4. 평균적으로 빠른 속도: 평균적으로 O(n log n)의 시간 복잡도를 가지므로 대부분의 경우에 빠른 속도를 보입니다.
5. 재귀적 구현: 주로 재귀 함수를 통해 구현되며, 스택의 호출로 인해 추가적인 메모리를 사용할 수 있습니다.

알고리즘 동작 방식

1. 배열에서 하나의 원소를 피벗(Pivot)으로 선택합니다.
2. 피벗을 기준으로 작은 값은 피벗의 왼쪽에, 큰 값은 피벗의 오른쪽에 위치시킵니다. 이 과정을 피벗을 기준으로 분할(partition)이라고 합니다.
3. 피벗을 제외한 왼쪽 부분 배열과 오른쪽 부분 배열에 대해 재귀적으로 위의 과정을 반복합니다.
4. 부분 배열의 크기가 1 이하가 될 때까지 반복하여 정렬을 완료합니다.

장점

1. 평균적으로 매우 빠른 속도를 보입니다. 평균 시간 복잡도가 O(n log n)으로 매우 효율적입니다.
2. 제자리 정렬이므로 메모리 사용량이 작습니다.
3. 대부분의 입력에 대해 좋은 성능을 보이며, 대용량 데이터에도 적용 가능합니다.

단점

1. 최악의 경우에는 시간 복잡도가 O(n^2)가 될 수 있습니다. 피벗 선택에 따라 분할이 한쪽으로 치우칠 때 발생합니다.
2. 불안정 정렬이기 때문에 원소들의 상대적인 순서가 변할 수 있습니다.
3. 재귀적인 구현을 사용하므로, 재귀 호출에 따른 스택 메모리 사용량이 크게 증가할 수 있습니다.

요약

퀵 정렬은 평균적으로 매우 빠른 속도를 가지고 있으며, 대부분의 경우에 효율적인 정렬 알고리즘입니다.

그러나 최악의 경우에는 시간 복잡도가 O(n^2)가 될 수 있으므로, 입력 데이터에 따라 성능 변동이 크다는 점에 유의해야 합니다.

https://fullyunderstood.com/pseudocodes/quick-sort/

void DoQuickSort()
{
	vector<int> arr;
	arr.assign(rand() % 30, int());

	for (auto& num : arr)
		num = rand() % 100;

	cout << "Before Sort" << endl;

	for (auto num : arr)
		cout << num << " ";

	cout << endll << "After Sort" << endl;

	QuickSort(arr, 0, arr.size() - 1);
	for (auto num : arr)
		cout << num << " ";

	cout << endll;

	Pause;
	return;
}

void QuickSort(vector<int>& arr, int left, int right)
{
	// 리스트의 크기가 1 이하인 경우, 정렬이 이미 완료된 상태
	if (left >= right)
		return;

	// 리스트의 첫 요소를 pivot으로 설정
	int pivot = arr[left];
	// pivot보다 작은 요소들의 마지막 인덱스
	int i = left + 1;
	// pivot보다 큰 요소들의 첫 인덱스
	int j = right;

	// i와 j가 교차할 때까지 pivot보다 작은 요소는 i를, pivot보다 큰 요소는 j를 찾음
	while (i <= j)
	{
		while (i <= right && arr[i] > pivot)		
			i++;
		while (j >= left + 1 && arr[j] < pivot)		
			j--;

		// i와 j가 교차하지 않은 경우, i와 j를 교환
		if (i <= j)
			swap(arr[i], arr[j]);
	}

	// pivot을 기준으로 분할된 왼쪽과 오른쪽 부분 리스트를 재귀적으로 정렬
	swap(arr[left], arr[j]);
	QuickSort(arr, left, j - 1);
	QuickSort(arr, j + 1, right);
}