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

01. 퀵 정렬의 개념

• 불안정 정렬이며, 다른 원소와의 비교를 통해 정렬하는 비교 정렬
• 분할 정복 알고리즘이다.
• 매우 빠른 속도를 보장 ( O(NlogN) )
• 주로 순환 호출로 구현

02. 과정 설명

오름차순으로 정렬한다고 가정한다.

1. 리스트 안에 있는 한 요소를 선택 (보통 맨 앞의 원소), 이를 Pivot이라고 한다.
2. 피벗을 기준으로, 피벗보다 작은 요소들을 모드 왼쪽으로 옮기고 피벗보다 큰 요소를 오른쪽으로 옮긴다.
3. 피벗을 제외한 왼쪽, 오른쪽 요소들을 각각 따로 정렬한다.
4. 나눠진 부분들이 더 이상 분할이 불가능 할 떄까지 반복

03. 자세한 설명

• 배열에 [4, 6, 3, 2, 8, 7, 9, 1, 0, 5] 가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬한다.
• 초기 상태에서 pivot을 0번 원소로 가정한다. (4)
  • 이제 pivot값 4를 기준으로 왼 쪽 원소들은 4보다 작게, 오른쪽 원소들은 4보다 크게 분할해야 한다.
  • 그리고 왼쪽과 오른쪽을 같은 방식으로 정복할것
• 1번 원소부터 시작해서, 4보다 큰 원소를 찾는다.
  • 1번 원소인 6이 해당 (인덱스를 기억하자)
• 맨 끝 9번 원소부터 내려가면서, 4보다 작은 원소를 찾는다.
  • 8번 원소인 0이 해당
• 두 값을 교체한다.
  • 배열은 이제 [4, 0, 3, 2, 8, 7, 9 ,1, 6, 5]
• 2번 원소부터 다시 시작해서 4보다 큰 원소를 찾는다.
  • 4번 원소 8이 해당
• 8번 원소부터 시작해서 4보다 작은 원소 찾는다.
  • 7번 원소 1이 해당
• 또 두 값을 교체
  • [4, 0, 3, 2, 1, 7, 9, 8, 6, 5]
• 4번 원소부터 시작해서 4보다 큰 원소 찾는다.
  • 5번 원소 7
• 7번 원소부터 내려가면서 4보다 작은 원소
  • 4번 원소 1
• 왼쪽 인덱스가 오른 쪽 인덱스보다 커진 상황이다
  • 이 상황이 pivot의 위치가 결정된 상황이다.
  • pivot과 작은 원소의 위치를 교체해준다.
• [1, 0, 3, 2, 4, 7, 9, 8, 6, 5]
  • Pivot 값인 4를 기준으로, 왼쪽 부분 리스트에는 4보다 작은 값이, 오른쪽 부분 리스트에는 4보다 큰 값이 들어간 것을 볼 수 있다.
• 이제 각 부분 리스트에 대해 같은 작업을 반복해 주면 된다.

04. C++ 코드

#include <iostream>

using namespace std;

int arr[500] = {};

void quicksort(int* pArr, int start, int end)
{
	if (start >= end)
		return;

	int pivot = start;
	int left = start + 1;
	int right = end;

	while (left < right)
	{
		// pivot보다 큰 수가 나올 때까지
		while (left <= end && pArr[left] < pArr[pivot])
			++left;
		// pivot보다 작은 수가 나올 때까지
		while (right > start && pArr[right] > pArr[pivot])
			--right;

		// 엇갈린 경우 pivot 교체
		if (left > right)
		{
			int temp = pArr[pivot];
			pArr[pivot] = pArr[right];
			pArr[right] = temp;
		}
		// 아닌 경우 좌우 교체 => 작은 수가 앞으로 오게 된다.
		else
		{
			int temp = pArr[right];
			pArr[right] = pArr[left];
			pArr[left] = pArr[right];
		}
	}

	quicksort(pArr, start, pivot - 1);
	quicksort(pArr, pivot + 1, end);
}

int main()
{
	int n;
	cin >> n;

	for (int i = 0; i < n; ++i) { cin >> arr[i];}

	quicksort(arr, 0, n - 1);

	for (int i = 0; i < n; ++i) { cout << arr[i] << " "; }

	return 0;
}

05. 퀵 정렬의 시간 복잡도

• 레코드의 크기 N = 2^k 인 경우, 순환 호출의 깊이는 pivot에 의해 균등하게 나누어진다고 가정할 때 log2^k = k이다.
• 각 순환 호출 단계마다 pivot위치를 찾기 위한 비교연산은 N번이다. (첫 번째 나누기라고 했을 때 2개의 레코드로 나뉘어지고, 각 레코드마다 1/2만큼의 길이를 가지기 때문에 1/2 * 2 = 1이므로
• 따라서 최선의 경우 kN = NlogN이다.
• 하지만, 레코드가 정렬되어 있는 경우에는 모든 원소가 왼쪽, 오른쪽 둘 중 하나로 쏠리기 때문에 순환 호출의 깊이가 N이 된다. (k = N)
• 따라서 최악의 경우 O(N^2)일 수 있다.
• 표준 라이브러리의 경우 O(NlogN)을 보장하기 위해 피벗값을 설정할 때 추가적인 로직을 더해준다는 듯.