[알고리즘, C] 퀵 정렬(Quick Sort) 구현

<퀵 정렬(Quick sort) 구현>

[QuickSort.c]

/*
* 알고리즘 - 퀵 정렬(Quick Sort)
* 파일명: QuickSort.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-26
* 이전 버전 작성 일자:
* 버전 내용: 간단한 퀵 정렬 구현
* 이전 버전 내용:
*/

#include <stdio.h>

// 데이터 이동(교환)에 사용
void Swap(int arr[], int idx1, int idx2)
{
	int temp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = temp;
}

// 피벗의 중간값을 구하기 위해 정의한 함수
int MedianOfThree(int arr[], int left, int right)
{
	// 배열로 가장 첫 번째 인덱스, 중간값, 가장 마지막 인덱스를 배열에 저장.
	int samples[3] = { left, (left + right) / 2, right };

	// 값의 대소 비교를 진행한다.
	// 값을 비교하여 중간값에 맞는 인덱스를 반환하기 위함
	if (arr[samples[0]] > arr[samples[1]])
		Swap(samples, 0, 1);

	if (arr[samples[1]] > arr[samples[2]])
		Swap(samples, 1, 2);

	if (arr[samples[0]] > arr[samples[1]])
		Swap(samples, 0, 1);

	// 마지막으로 중간값의 인덱스를 반환.
	return samples[1];
}

// 퀵 정렬을 실제로 수행하는 Partition 함수
int Partition(int arr[], int left, int right)
{
	int pivot_idx = MedianOfThree(arr, left, right);
	int pivot = arr[pivot_idx]; // 피벗 값의 위치는 가장 왼쪽으로
	int low = left + 1; // 피벗을 제외한 가장 왼쪽 값의 인덱스
	int high = right; // 피벗을 제외한 가장 오른쪽값의 인덱스

	Swap(arr, left, pivot_idx);

	printf("pivot: %d\n", pivot);

	while (low <= high) // low와 high의 값이 교차되지 않을 때까지 반복 수행
	{
		// 피벗보다 큰 값을 찾는 과정
		while (pivot >= arr[low] && low <= right)
			low++; // low를 오른쪽으로 이동

		// 피벗보다 작은 값을 찾는 과정
		while (pivot <= arr[high] && high >= (left + 1))
			high--; // high를 왼쪽으로 이동

		// low와 high가 교차되지 않았다면 Swap 수행
		if (low <= high)
			Swap(arr, low, high);
	}

	Swap(arr, left, high); // 피벗과 high가 가리키는 대상을 교환
	return high; // 옮겨진 피벗의 위치 정보 반환
}

void QuickSort(int arr[], int left, int right)
{
	if (left < right)
	{
		int pivot = Partition(arr, left, right); // 둘로 나눠서
		QuickSort(arr, left, pivot - 1); // 왼쪽 영역 실행
		QuickSort(arr, pivot + 1, right); // 오른쪽 영역 실행
	}
}

int main()
{
	//int arr[7] = {3, 2, 4, 1, 7, 6, 5};
	//int arr[3] = { 3, 3, 3 };
	int arr[15] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};

	int len = sizeof(arr) / sizeof(int);
	int i;

	QuickSort(arr, 0, len - 1);

	for (i = 0; i < len; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

 

[퀵 정렬의 이해]

퀵 정렬!

얼마나 빠르길래 퀵 정렬이라 하는 것인지는 모르지만, 일단 성능 상 가장 좋다고 알려져 있는 정렬 방식이다.

퀵 정렬은 병합 정렬과 얼핏 비슷해보이지만, 피벗이라는 값을 이용하여 분할하고 정렬하는 방식이다.

 

1) 초기화

병합 정렬에서는 left, mid, right만 썼지만, 여기서는 다섯 개의 변수를 핵심으로 진행한다.
먼저 left와 right는 동일한 개념으로 쓰였고, mid는 pivot으로 대체가 된다.
그리고 low는 피벗 값을 제외한 가장 왼쪽 지점을 가리키고, high는 피벗 값을 제외한 가장 오른쪽 지점을 가리키게 된다.

 

2) low와 high의 이동

low와 high는 피벗값을 기준으로 low는 오른쪽, high는 왼쪽으로 이동한다.
low는 피벗값보다 큰 값을 만날 때까지 이동하고, high는 피벗값보다 작은 값을 만날 때까지 이동한다.
더 정확히 말하면 이렇게 정리할 수 있다.

 

"low는 피벗값보다 우선 순위가 낮은 데이터를 만날 때까지,

high는 피벗값보다 우선 순위가 높은 값을 만날 때까지 이동한다."

여기서 low와 high의 이동은 별개라는 점이다.
절대 같이 이동하는 것이 아니다.

 

3) low와 high의 교환

해당 조건에 맞는 값까지 이동하게 되면 low와 high의 값을 교환한다.
이는 정렬의 상태에 좀 더 가까워지기 위해 교환을 하는 것이다.
교환을 한 이후에는 다시 이동을 하며 교환해야 하는 경우에는 교환을 한다.
그래서 계속 이동을 하다보면 low와 high가 교차하여 역전이 되는 상황이 온다.
이 때, 이동을 멈추고 피벗과 high가 가리키는 데이터를 서로 교환한다.
그러면 피벗이 위치한 자리는 정렬이 된 것이다.
이 상태에서 피벗을 기준으로 놓고 보면 다음과 같이 대략적으로 정렬이 된 상태가 된다.

왼쪽은 피벗보다 우선순위가 높은 값들이, 오른쪽에는 우선순위가 낮은 값들만이 위치하게 된다.
이후에는 피벗을 기준으로 왼쪽과 오른쪽에 있는 요소들에 대해 1~3의 과정을 반복하며 정렬을 수행한다.

[성능 평가]

퀵 정렬은 대체로 최선의 경우만을 따진다.
이는 피벗값을 대부분 중간값을 정해서 수행하기 때문에, 어지간해서는 최악의 경우가 되는 일이 없기 때문이다.
그리고 병합 정렬과 유사하게 피벗값을 기준으로 분할하여 정렬하는 방식이다.
분할하는데 수행 시간은 $log_2n$이다.

그리고 데이터의 수가 $n$이라면 퀵 정렬에서의 비교연산에 대한 빅-오는 $O(nlog_2n)$이 된다.
최악의 경우는 이미 다 정렬이 되어있는 상태에서 맨 왼쪽 값, 가장 작은 값을 피벗으로 택하는 경우이다.

이는 극단적인 상황이라고 볼 수 있다.
이때는 분할이 되는 횟수는 $n$이 되고, 데이터의 갯수가 $n$이라면 빅-오는 $O(n^2)$이 된다.
실제로 퀵 정렬은 같은 빅-오를 갖는 정렬 알고리즘과 비교했을 때에도 평균적으로 가장 빠른 것으로 알려져있다.
그 이유는 퀵 정렬의 데이터 이동횟수가 상대적으로 적은 부분에 있다.

그리고 병합 정렬과 마찬가지로 별도의 메모리 공간도 요구하지 않는다.
그래서 동일한 빅-오를 갖는 정렬 알고리즘 중에서도 평균적으로 가장 빠른 정렬 속도를 보이는 알고리즘이다.