퀵 정렬 (Quick sort)

퀵 정렬

정렬 알고리즘 중에서 퀵 정렬은 많이 사용되는 알고리즘 중 하나로, 빠른 속도와 효율성으로 널리 알려져 있습니다. 퀵 정렬은 '분할 정복' 알고리즘을 기반으로 하며, 배열을 효율적으로 정렬하는 방법을 제공합니다.

개념 소개

퀵 정렬은 큰 문제를 작은 문제로 나누어 해결하는 분할 정복 알고리즘의 일종입니다. 주어진 배열을 피봇(pivot)을 기준으로 두 개의 하위 배열로 분할하고, 각 하위 배열을 재귀적으로 정렬하는 과정을 반복하여 전체 배열을 정렬합니다.

동작 과정

피봇 선택: 배열에서 피봇을 선택합니다. 피봇 값은 하위 배열을 분할할 때의 기준이 됩니다. 피봇 선택은 배열의 중간값이나 랜덤한 값으로 선택하는 것이 일반적입니다.

분할: 선택한 피봇을 기준으로 배열을 두 개의 하위 배열로 분할합니다. 작은 값은 왼쪽 배열에, 큰 값은 오른쪽 배열에 위치하도록 분할됩니다.

정복: 각 하위 배열에 대해 재귀적으로 퀵 정렬을 수행합니다. 이 단계에서 하위 배열이 더 이상 분할되지 않을 때까지 계속 정렬됩니다.

합병: 퀵 정렬은 비교 기반의 정렬 알고리즘이므로 합병 작업이 필요하지 않습니다. 각 단계에서 배열 내에서 요소의 위치가 조정되어 정렬이 이루어지기 때문입니다.

예시

아래는 퀵 정렬의 동작 예시입니다:

배열: [5, 3, 8, 4, 2, 7, 1, 6]
피봇 선택: 중간 값인 4 선택
분할: 작은 값: [3, 2, 1], 피봇 값: 4, 큰 값: [8, 7, 6]
재귀 정렬: 작은 값 배열과 큰 값 배열에 대해 퀵 정렬 수행
최종 정렬된 배열: [1, 2, 3, 4, 5, 6, 7, 8]

사진 예시

분할 정복

퀵 정렬은 분할 정복(divide and conquer) 알고리즘의 대표적인 예시 중 하나입니다. 이 알고리즘은 큰 문제를 작은 하위 문제로 분할하고, 각 하위 문제를 재귀적으로 해결하여 전체 문제를 해결하는 방식을 사용합니다. 특히 퀵 정렬은 배열을 빠르게 정렬하는 효율적인 방법 중 하나로 널리 알려져 있습니다.

분할 단계

퀵 정렬의 첫 번째 단계는 '분할' 단계입니다. 주어진 배열을 피봇(pivot)이라는 요소를 기준으로 두 개의 하위 배열로 분할합니다. 피봇은 주로 배열의 중간값이나 랜덤한 값을 선택합니다. 이렇게 하위 배열로 분할된 후 각 하위 배열은 독립적으로 정렬되는데, 이것이 분할 정복 알고리즘의 핵심 아이디어입니다.

정복 단계

하위 배열이 분할되었으면, 각각의 하위 배열에 대해 정렬을 수행합니다. 이 정렬은 재귀적으로 이루어집니다. 하위 배열이 더 이상 분할할 수 없는 작은 크기가 될 때까지 이 과정을 반복합니다. 각 하위 배열이 정렬된 후에는 원래 배열의 요소들도 정렬되어 있는 상태가 됩니다.

합병 단계

정렬된 하위 배열을 합병하는 작업은 필요하지 않습니다. 왜냐하면 퀵 정렬은 '비교 기반'의 정렬 알고리즘이기 때문에 각 단계에서 이미 배열 내에서 요소의 위치가 조정되어 정렬되기 때문입니다.

요약

퀵 정렬은 큰 문제를 작은 하위 문제로 분할하고, 이를 통해 각 하위 문제를 정렬하여 전체 문제를 해결하는 분할 정복 알고리즘의 대표적인 예시입니다. 이 알고리즘은 평균적으로 O(n log n)의 시간 복잡도를 가지며, 메모리 효율성도 높아 빠른 속도로 배열을 정렬할 수 있습니다.

퀵 정렬은 피봇 선택 방법에 따라 성능이 달라질 수 있으며, 최악의 경우 시간 복잡도가 O(n^2)가 될 수 있습니다. 따라서 효율적인 피봇 선택 전략을 사용하는 것이 중요합니다. 또한, 퀵 정렬은 정렬이 안정성을 보장하지 않는 특징을 가지므로, 안정성이 필요한 경우에는 다른 정렬 알고리즘을 고려해야 합니다.

퀵 정렬은 분할 정복 알고리즘의 대표적인 사례로서, 큰 문제를 작은 문제로 나누어 해결하는 방식을 통해 효율적인 정렬을 수행합니다. 이해하기 쉽고 간결한 분할 정복의 예시 중 하나로 퀵 정렬은 컴퓨터 과학의 중요한 개념을 나타내는 좋은 사례입니다.

시간 복잡도

퀵 정렬은 배열을 빠르게 정렬하는 효율적인 알고리즘으로, 그 중요한 특징 중 하나는 평균적으로 O(n log n)의 시간 복잡도를 가진다는 것입니다. 그러나 최선의 경우와 최악의 경우에 따라 시간 복잡도가 어떻게 변하는지 자세히 알아보겠습니다.

평균 시간 복잡도: O(n log n)

퀵 정렬의 평균 시간 복잡도는 O(n log n)입니다. 이는 배열을 피봇을 기준으로 분할하고, 각 하위 배열을 정렬하는 작업이 평균적으로 n log n 번 수행되기 때문입니다. 피봇 선택에 무작위성을 포함하면, 데이터가 어떤 분포를 가지더라도 평균적으로 비교 및 분할이 균등하게 이루어져 높은 성능을 유지할 수 있습니다.

최선의 경우 시간 복잡도: O(n log n)

최선의 경우는 피봇을 선택하여 항상 중간값을 선택할 때 발생합니다. 이 경우에는 모든 분할이 균등하게 이루어지며, 재귀적으로 작은 하위 배열들이 정렬되기 때문에 시간 복잡도가 O(n log n)이 됩니다.

최악의 경우 시간 복잡도: O(n^2)

최악의 경우는 피봇을 항상 가장 크거나 작은 값으로 선택할 때 발생합니다. 이로 인해 분할이 한 쪽으로 치우쳐서 모든 원소가 하나의 하위 배열로만 분할되는 상황이 발생하며, 이는 O(n^2)의 시간 복잡도를 가져옵니다.

최악의 경우 개선: 랜덤한 피봇 선택

피봇 선택을 개선하여 최악의 경우 시간 복잡도를 피하는 방법 중 하나는 랜덤한 피봇 선택입니다. 랜덤한 피봇 선택은 평균적으로 균등한 분할을 유지하므로 최악의 경우 시간 복잡도를 대폭 개선할 수 있습니다.

요약

퀵 정렬은 평균적으로 O(n log n)의 빠른 시간 복잡도를 가지며, 최선의 경우에도 O(n log n)으로 효율적으로 작동합니다. 그러나 피봇 선택 방법에 따라 최악의 경우 시간 복잡도가 O(n^2)까지 증가할 수 있습니다. 이를 피하기 위해 랜덤한 피봇 선택이나 중앙값 피봇 선택과 같은 방법을 사용하여 성능을 개선할 수 있습니다.

퀵 정렬의 시간 복잡도는 데이터 분포와 피봇 선택에 따라 다르게 변할 수 있지만, 평균적으로 높은 성능을 유지하는 효율적인 정렬 알고리즘입니다.

피봇 선택

퀵 정렬은 배열을 빠르게 정렬하는 효율적인 알고리즘 중 하나입니다. 그러나 피봇(pivot) 선택 방법에 따라서는 최악의 경우 시간 복잡도가 급격하게 나빠질 수 있습니다. 이를 피하기 위해 피봇 값을 랜덤하게 설정하는 방법을 살펴보겠습니다.

피봇 선택 방법의 중요성

퀵 정렬에서 배열을 분할하려면 피봇을 선택하여 그 값을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 이동시킵니다. 그러나 배열이 이미 정렬되어 있거나 특정한 패턴을 가질 경우, 처음이나 마지막 값을 피봇으로 선택하면 최악의 경우가 발생할 수 있습니다. 이로 인해 정렬 과정이 매우 느려지게 됩니다.

랜덤한 피봇 선택

이러한 문제를 피하기 위해 피봇 값을 랜덤하게 선택하는 것이 좋습니다. 랜덤하게 피봇을 선택하면 데이터의 패턴이나 정렬 상태에 상관없이 어느 정도의 확률로 좋은 성능을 유지할 수 있습니다.

과정 설명

배열에서 랜덤한 인덱스를 선택합니다. 이렇게 선택된 인덱스에 해당하는 값을 피봇으로 사용하게 됩니다.
피봇 값을 배열의 맨 오른쪽 값과 바꿉니다. 이렇게 하면 피봇 값이 가장 오른쪽에 위치하게 됩니다.
이제 퀵 정렬을 진행합니다. 피봇 값보다 작은 값을 왼쪽으로, 큰 값을 오른쪽으로 이동시킵니다. 이 단계에서 피봇 값을 기준으로 배열이 분할됩니다.

장점

랜덤한 피봇 선택은 데이터의 패턴에 무관하게 피봇 값을 고르기 때문에 최악의 경우를 피할 수 있습니다. 이로 인해 퀵 정렬의 평균적인 성능을 안정적으로 유지할 수 있습니다.

코드

#include <stdio.h>
#include <stdlib.h>

void	swap_value(int *arr, int i, int j)
{
	int	temp;

	temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
	return ;
}

int	partition(int *arr, int left, int right)
{
	int	i;
	int	j;
	int	pivot;

	i = left;
	j = right;
	pivot = right;
	swap_value(arr, pivot, left + rand() % (right - left));
	while (i < j)
	{
		while (arr[i] <= arr[pivot] && i < right)
			++i;
		while (arr[j] >= arr[pivot] && j > left)
			--j;
		if (i < j)
			swap_value(arr, i, j);
	}
	swap_value(arr, pivot, i);
	pivot = i;
	return (pivot);
}

void	quick_sort(int *arr, int left, int right)
{
	int	pivot;
	
	if (left >= right)
		return ;
	pivot = partition(arr, left, right);
	quick_sort(arr, left, pivot - 1);
	quick_sort(arr, pivot + 1, right);
	return ;
}

int	main(void)
{
	int	n_of_input;
	int	arr[1000000];

	scanf("%d", &n_of_input);
	for (int i = 0; i < n_of_input; i++)
		scanf("%d", &arr[i]);
	quick_sort(arr, 0, n_of_input - 1);
	for (int i = 0; i < n_of_input; i++)
		printf("%d ", arr[i]);
	return (0);
}

시간 복잡도 비교

병합 정렬과 퀵 정렬은 둘 다 분할 정복 알고리즘을 사용하여 배열을 작은 하위 배열로 분할하는 점에서 유사합니다. 그럼에도 불구하고 병합 정렬의 런타임이 퀵 정렬보다 느린 이유에는 몇 가지 이유가 있습니다.

1. 추가적인 공간 사용
   병합 정렬은 분할된 하위 배열을 별도의 임시 배열에 복사한 후, 정렬된 하위 배열을 다시 합병하는 과정을 거칩니다. 이 때, 추가적인 공간이 필요하게 되어 메모리 사용량이 증가합니다. 특히 배열이 크거나 하위 배열의 수가 많을 경우, 이로 인해 메모리 관리가 더 복잡해지며 런타임에 오버헤드가 발생할 수 있습니다.

2. 합병 작업의 부하
   병합 정렬에서의 합병 작업은 분할된 하위 배열을 합치는 작업으로, 정렬된 두 하위 배열을 비교하며 병합합니다. 이 과정에서 인덱스를 이동하고 값을 복사하는 작업이 필요한데, 특히 배열이나 리스트의 요소들을 연속적으로 메모리에 접근하는 것보다는 캐시 메모리를 더 많이 활용하는 퀵 정렬보다 느릴 수 있습니다.

3. 재귀적인 호출
   병합 정렬은 합병 작업에서 하위 배열을 재귀적으로 합치는 과정을 거칩니다. 재귀 호출은 함수 호출 및 반환의 오버헤드를 가지며, 특히 재귀 호출이 많을수록 성능에 부정적인 영향을 미칠 수 있습니다. 반면에 퀵 정렬은 분할과정이 복잡하지만 재귀적인 호출을 최소화할 수 있어 더 빠른 런타임을 가질 수 있습니다.