[알고리즘] 퀵 정렬 (Quick Sort) 이란? (C++로 구현하기)

퀵 정렬 (Quick Sort)이란?

이름부터가 퀵 정렬 (Quick Sort) 입니다. 빠르다는거겠죠?

맞습니다. 일반적인 상황에서 빠른 정렬 시간을 보장해준다고 합니다.

 

버블정렬, 삽입정렬, 선택정렬 등은 O(N²) 의 시간을 가지지만,

퀵 정렬은 평균적인 상황에서 O(N * log N) 의 시간을 가집니다.

그러므로 빠른 정렬이라고 할 수 있겠죠.

 

최악의 경우에서는 O(N²) 의 시간복잡도를 가집니다.

이 경우는 이미 정렬이 완료되어있는 경우로,

이런 경우에는 합병정렬을 사용하는 것을 고려해볼 수 있습니다.

 

 

 

동작 원리

아래와 같은 배열이 있다고 가정해보겠습니다.

 

 

퀵 정렬을 사용하기 위해서는 피벗 (Pivot) 이라는 기준점을 잡아주어야 합니다.

즉, 피벗을 기준으로 작은 것과 큰 것을 구분해서 정렬을 진행한다는 것입니다.

그렇다면 어떤 값을 피벗으로 잡아야할까요?

사실 피벗은 랜덤으로 잡거나, 특정한 알고리즘을 적용하여 선정하는 것이 좋습니다.

하지만, 저희는 구현의 편의성을 위해서 배열의 가장 첫 번째 원소로 하겠습니다.

아래와 같이 말입니다.

 

피벗을 잡았으므로 정렬을 시작해보겠습니다. 아래와 같은 값들을 찾을 것입니다.

- 왼쪽부터 시작해서, 피벗보다 큰 값을 가지는 값

- 오른쪽부터 시작해서, 피벗보다 작은 값을 가지는 값

 

한번 찾아보시기 바랍니다. 찾으셨나요?

정상적으로 찾았다면, 아래와 같은 값들이 찾아질 것입니다.

 

그리고 이제, 이 값들을 서로 바꿔줍니다.

 

이제 인덱스를 각각 증가시켜 가며 이 과정을 반복합니다.

언제까지냐구요?

두 인덱스가 만나거나, 교차해서 넘어간 점입니다.

즉, 왼쪽 인덱스를 i, 오른쪽 인덱스를 j라고 할 때, i <= j 가 만족하는 순간입니다. 아래와 같습니다.

 

거의 다 왔습니다.

이제 이 상태에서, pivot과 j 인덱스의 값을 바꿔주면 됩니다.

 

그럼 어떻게 되었나요?

보시는 것처럼, 피벗을 기준으로 왼쪽과 오른쪽이 정렬된 것을 보실 수 있습니다.

그리고 이제 왼쪽과 오른쪽 각각의 정렬을 위해서 재귀호출을 반복합니다.

그럼 최종적으로 완성된 배열을 확인할 수 있습니다.

 

 

 

구현 (C++)

#include <iostream>
#include <ctime>

#define MAX_ARR	20

using namespace std;

void quickSort(int arr[], int first, int last)
{
	if(first >= last) return;

	int pivot = first;
	int i = first + 1;
	int j = last;
	int tmp;

	while (i <= j)
	{
		while (arr[i] < arr[pivot] && i <= last) i++;
		while (arr[j] >= arr[pivot] && j > first) j--;

		if (i >= j) break;

		tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	tmp = arr[j];
	arr[j] = arr[pivot];
	arr[pivot] = tmp;

	quickSort(arr, first, j - 1);
	quickSort(arr, j + 1, last);
}

void print(int arr[], int N, const char* str)
{
	cout << str << '\n';
	for (int i = 0; i < N; i++) cout << arr[i] << " ";
	cout << '\n';
}

int main(void)
{
	srand(time(NULL));

	int arr[MAX_ARR];
	for (int i = 0; i < MAX_ARR; i++)
		arr[i] = rand() % 10 + 1;

	print(arr, MAX_ARR, "[PREV]");
	quickSort(arr, 0, MAX_ARR - 1);
	print(arr, MAX_ARR, "[NEXT]");

	return 0;
}