■ 퀵 정렬(Quick Sort)
퀵 정렬은 기준값(Pivot)을 하나 선택한 뒤, 그보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 보내며 배열을 분할하고, 각 부분을 재귀적으로 다시 정렬하는 알고리즘이다.
퀵 정렬의 핵심 원리는 다음과 같다.
- Pivot(기준값)을 하나 정한다.
- 배열을 pivot보다 작은 부분과 큰 부분으로 나눈다.
- 이 두 부분을 재귀적으로 다시 퀵 정렬한다.
이처럼 퀵 정렬은 분할(Divide) → 정복(Conquer) → 결합(Combine)의 순서를 따르는 전형적인 분할 정복(Divide and Conquer) 알고리즘이다.
- 조금 복잡해 보일 수 있지만, pivot을 기준으로 어떻게 분할되고, 재귀가 어디까지 이어지는지만 이해하면 직접 구현하는 데에도 큰 어려움이 없다.
■ 퀵 정렬 구현 - Hoare 분할 방식(C#)
퀵 정렬에는 대표적으로 두 가지 분할 방식이 있는데, 이번에는 구현이 좀 복잡하지만 성능이 더 우수한 Horea 방식을 먼저 설명하겠다.
- 1959년 퀵 정렬을 처음 고안한 Tony Hoare가 제안한 방식.
- 양쪽 끝에서 포인터를 시작해 서로 이동시킨다.
1. Pivot값 선택
퀵 정렬에서 가장 중요한 요소 중 하나는 Pivot값 선택이다.
Pivot값이 항상 배열의 최솟값이나 최댓값으로 선택되는 경우, 시간복잡도가 최악의 경우 $O(n^2)$까지 증가할 수 있다.
public static class SortArray<T> where T : IComparable<T>
{
private static Random rand = new Random();
// 퀵 정렬
public static void QuickSort(T[] arr, int low, int high)
{
if (low >= high) return;
var pivot = arr[rand.Next(low, high + 1)];
}
}그래서 pivot값을 선택할 때 배열의 맨 앞 혹은 맨 뒤를 선택해도 되지만, 공평한 선택을 위해 랜덤 하게 pivot을 선택하는 방식으로 구현하였다.
public static class SortArray<T> where T : IComparable<T>
{
private static Random rand = new Random();
// 퀵 정렬
public static void QuickSort(T[] arr, int low, int high)
{
if (low >= high) return;
//var pivot = arr[rand.Next(low, high + 1)];
var pivot = MedianOfThree(arr[low], arr[(low + high) / 2], arr[high]);
}
public static T MedianOfThree<T>(T a, T b, T c) where T : IComparable<T>
{
if (a.CompareTo(b) > 0)
{
if (b.CompareTo(c) > 0)
return b; // a > b > c
else if (a.CompareTo(c) > 0)
return c; // a > c > b
else
return a; // c > a > b
}
else
{
if (a.CompareTo(c) > 0)
return a; // b > a > c
else if (b.CompareTo(c) > 0)
return c; // b > c > a
else
return b; // c > b > a
}
}
}혹은 배열의 첫 번째 원소, 중간 위치의 원소, 마지막 위치의 원소 중 중간값을 Pivot값으로 사용하는 Median-of-Three 방식을 사용할 수 있다.
- 이 경우 pivot을 고를 때 데이터 분포를 어느 정도 고려하기 때문에, 더 안정적인 Pivot을 선택하게 된다.
2. 포인터 이동
public static class SortArray<T> where T : IComparable<T>
{
private static Random rand = new Random();
// 퀵 정렬
public static void QuickSort(T[] arr, int low, int high)
{
if (low >= high) return;
var pivot = arr[rand.Next(low, high + 1)];
var leftIndex = low;
var rightIndex = high;
while(true)
{
while (arr[leftIndex].CompareTo(pivot) < 0) { leftIndex++; }
while (arr[rightIndex].CompareTo(pivot) > 0) { rightIndex--; }
if (leftIndex >= rightIndex) break;
if (leftIndex <= rightIndex)
{
(arr[leftIndex], arr[rightIndex]) = (arr[rightIndex], arr[leftIndex]);
leftIndex++;
rightIndex--;
}
}
}
}leftIndex는 배열의 시작점(low), rightIndex는 배열의 끝 지점(high)에서 시작하여 서로를 향해 이동한다.
- 왼쪽 포인터(leftIndex)의 이동
- leftIndex는 해당 위치의 값이 pivot보다 작을 때만 오른쪽(++)으로 이동한다.
- 만약 pivot보다 크거나 같은 값을 만나면, 그 위치에서 멈춘다. → 이 값은 정렬이 필요한 대상이기 때문.
- 오른쪽 포인터(rightIndex)의 이동
- rightIndex는 해당 위치 값이 pivot보다 클 때만 왼쪽(—)으로 이동한다.
- pivot보다 작거나 같은 값을 만나면 멈춘다. → 이 값 역시 교환 대상이기 때문.
두 포인터가 모두 멈췄고, leftIndex가 rightIndex를 넘지 않았다면, 두 값을 교환한 뒤 각 포인터를 한 칸씩 이동한다.
- 두 포인터가 서로 교차(leftIndex ≥ rightIndex)하면 분할 탐색을 종료하고 다음 재귀 단계로 넘어간다.
▶ 포인터는 항상 동시에 움직이는 것이 아니다! 한쪽 포인터가 교환 대상을 찾았다고 해도, 다른 포인터가 멈출 때까지 기다린 뒤 교환이 이루어진다.
3. 배열 분할
public static class SortArray<T> where T : IComparable<T>
{
private static Random rand = new Random();
// 퀵 정렬
public static void QuickSort(T[] arr, int low, int high)
{
if (low >= high) return;
var pivot = arr[rand.Next(low, high + 1)];
var leftIndex = low;
var rightIndex = high;
while (true)
{
while (arr[leftIndex].CompareTo(pivot) < 0) { leftIndex++; }
while (arr[rightIndex].CompareTo(pivot) > 0) { rightIndex--; }
if (leftIndex >= rightIndex) break;
if (leftIndex <= rightIndex)
{
(arr[leftIndex], arr[rightIndex]) = (arr[rightIndex], arr[leftIndex]);
leftIndex++;
rightIndex--;
}
}
// 배열 분할
if (low < rightIndex)
{
QuickSort(arr, low, rightIndex);
}
if (rightIndex + 1 < high)
{
QuickSort(arr, rightIndex + 1, high);
}
}
}
두 포인터가 교차하여 분할이 완료되면, 왼쪽 구간(low ~ rightIndex), 오른쪽 구간(rightIndex + 1~ high)에 대해 각각 재귀적으로 다시 퀵 정렬을 수행한다.
- 이때, 시작 인덱스가 끝 인덱스보다 작을 때만 재귀호출해야 한다. 그렇지 않으면 불필요한 호출이 발생하거나 예외가 발생할 수 있다.
우측 배열의 범위를 leftIndex ~ high가 아닌 rightIndex + 1 ~ high로 지정하는 이유
QuickSort(arr, rightIndex + 1, high)와 같이 우측 배열을 재귀 호출할 때, 범위의 시작점을 leftIndex 대신 rightIndex + 1로 사용하는 이유는 다음과 같다.
Hoare 분할 방식에서는 두 포인터(leftIndex, rightIndex)가 같은 위치에서 멈추는 경우가 있을 수 있다.
이때 우측 범위의 시작점을 leftIndex로 지정하면, 이미 분할에 사용된 중간 값을 다시 포함하게 되어 중복 정렬이 발생할 수 있다.
하지만 포인터가 교차되었을 때는 leftIndex == rightIndex + 1이기 때문에, rightIndex + 1을 시작점으로 사용하는 것이 중복 없이 정확하게 오른쪽 배열을 분할하는 방법이다.
■ 퀵 정렬 구현 - Lomuto 분할 방식(C#)
Lomuto분할 방식은 Pivot을 배열의 마지막 요소로 고정하고, 하나의 포인터(i)를 사용해서 Pivot보다 작은 값들을 앞으로 모은 뒤, 마지막에 Pivot을 정확한 자리에 이동시킨다.
i는 Pivot보다 작은 값들이 누적되는 마지막 위치를 가리킨다.
j는 순차적으로 배열을 탐색하면서, pivot보다 작은 값을 만나면,
- i를 한 칸 증가시키고, arr[i]와 arr[j]를 교환한다.
이렇게 하면 pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 자연스럽게 정렬된다.
- 최종적으로 i + 1 위치에 pivot을 교환하면, pivot은 자신보다 작은 값과 큰 값 사이, 정확한 위치에 놓이게 된다.
▶ 구현 전체 코드
public static class SortArray<T> where T : IComparable<T>
{
// 퀵 정렬 Lomuto
public static void LomutoQuickSort(T[] arr, int low, int high)
{
if (low >= high) return;
var pivotIndex = LomutoSplit(arr, low, high);
LomutoQuickSort(arr, low, pivotIndex - 1);
LomutoQuickSort(arr, pivotIndex + 1, high);
}
private static int LomutoSplit(T[] arr, int low, int high)
{
var pivot = arr[high];
var i = low - 1;
for(var j = low; j < high; ++j)
{
if (arr[j].CompareTo(pivot) > 0) continue;
i++;
(arr[i], arr[j]) = (arr[j], arr[i]);
}
(arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
return i + 1;
}
}위의 설명과 동일하게, j가 pivot보다 작거나 같다면 i를 한 칸 증가시키고, arr[i]와 arr[j]를 교환한다.
이 과정을 반복하면 pivot보다 작은 값들이 앞쪽에 정렬되며, 마지막으로 i + 1위치와 pivot(배열의 마지막 원소)을 교환하여 pivot이 정확한 위치에 들어오도록 한다.
- 이후, pivot이 들어온 위치를 기준으로 우측과 좌측으로 나누어 다시 정렬을 실시한다.
■ 퀵 정렬의 시간복잡도
퀵 정렬은 Pivot을 기준으로 배열을 두 부분으로 분할하고, 각 부분에 대해 다시 퀵 정렬을 수행하는 분할 정복 알고리즘이다.
- 수식이 부담스럽게 느껴지지만 의외로 간단한 구조다. 퀵 정렬을 통해 시간복잡도 계산에 익숙해지면, 다른 분할 정복 알고리즘도 한결 쉽게 이해할 수 있다.
$$ T(n) = 2T(\frac{n}{2}) + O(n) $$
[재귀 관계식]
Pivot을 기준으로 분할하는데 드는 시간은 $O(n)$이다.
- 배열의 모든 요소를 pivot과 비교해야 함 → 비교 $n$번
- 이 단계는 1회 분할마다 $O(n)$의 시간이 걸린다.
또한, 2개의 하위 배열에 대해 다시 퀵 정렬을 수행한다.
- pivot 기준으로 나눈 두 배열의 크기가 각각 $\frac{n}{2}$라면,
- $T(n)$ 크기의 배열을 두 번 정렬해야 한다. → $2T(\frac{n}{2})$
1. 마스터 정리(Master Theorem)
$$ T(n) = aT(\frac{n}{b}) + O(n^d) $$
[마스터 정리]
위 재귀식을 일반화하면 위와 같은 형태로 정리할 수 있다. 여기서 각각의 의미는 다음과 같다.
- $a$ = 부분 문제의 갯수
- $\frac{n}{b}$ = 각 부분 문제의 크기
- $O(n^d)$ = 분할/ 병합 등 부분 문제 외의 작업에 걸리는 시간
이때, 시간복잡도는 a, b, d 값의 관계에 따라 3가지 경우로 나뉘게 된다.
Case 1. $d < \log_ba$
이 경우는 하위 문제를 푸는 데 걸리는 시간이 전체 시간을 지배하는 경우이다.
예를 들어, 정렬하는 것보다 재귀적으로 더 많이 나눠서 정렬하는 데 시간이 더 드는 상황이다.
- 시간복잡도는 재귀가 좌우한다. 따라서 수식은 다음과 같이 정리된다.
$$ T(n) = \Theta(n^{\log_b a}) $$
Case 2. $d = \log_ba$
분할과 병합의 시간과 재귀 호출 시간복잡도가 같을 때이다. 대부분의 평균적인 정렬 알고리즘이 이 경우에 해당한다.
- 이 경우 로그 항이 추가된다.
$$ T(n) = \Theta(n^d \log n) $$
Case 3. $d > \log_ba$
이 경우는 하위 문제를 푸는 시간보다 분할 자체가 더 많은 계산을 필요로 할 때이다. 따라서 분할이 시간복잡도를 지배하게 되어 아래와 같이 정리된다.
$$ T(n) = \Theta(n^d) $$
퀵 정렬을 마스터 정리에 대입하면 다음과 같다.
- $a = 2$ (두 부분으로 나누므로)
- $b = 2$ (한 번 나눌 때 절반 씩)
- $d = 1$ (분할하는 데 $O(n)$의 시간)
따라서 $\log_ba = \log_22 = 1$ 이므로, $d = \log_b a$가 된다. 결국 퀵 정렬은 두 번째 케이스에 해당하며, 평균적인 시간복잡도는 $O(n \log n)$이 된다.
- 하지만 Pivot이 항상 가장 크거나, 가장 작은 값을 선택해 한쪽으로만 나뉘게 되면 $O(n^2)$의 시간복잡도를 가지게 된다. (분할 자체가 재귀보다 더 많은 계산을 필요로 하기 때문)
'Unity,C# > 알고리즘' 카테고리의 다른 글
| [Unity] 쿼드트리(QuadTree) 공간분할 알고리즘 (3) | 2025.08.26 |
|---|---|
| [정렬 알고리즘, C#] 병합 정렬(Merge Sort) (1) | 2025.06.20 |
| [정렬 알고리즘, C#] 삽입 정렬(Insertion Sort) (0) | 2025.06.17 |
| [정렬 알고리즘, C#] 선택 정렬(Selection Sort) (0) | 2025.06.17 |
| [정렬 알고리즘, C#] 버블 정렬(Bubble Sort) (1) | 2025.06.17 |