Unity 개발자를 위한 C# Quick Sort(퀵 정렬) 구현

이전에 살펴본 Merge Sort는 배열을 분할하여 정렬된 덩어리를 만든 뒤 병합하는 방식이었습니다. 정렬이 병합 단계에서 완성되며, 이를 위해 추가 메모리 O(N)을 사용하는 것이 핵심 특징이었죠.

 

Quick Sort는 같은 O(N log N) 계열의 정렬이지만, 접근 방식은 완전히 다릅니다. 정렬된 결과를 병합해서 만드는 대신, 분할(divide) 과정 자체에서 정렬을 진행합니다. 즉, Merge Sort가 구조를 만든 뒤 합치는 정렬이라면, Quick Sort는 나누는 과정에서 이미 정렬이 진행되는 정렬입니다.

---

1. Quick Sort 개요 및 핵심 아이디어

Quick Sort(퀵 정렬)는 Divide and Conquer(분할 정복) 기반의 정렬 알고리즘입니다. 하지만 Merge Sort와 달리, 병합(Merge) 단계가 존재하지 않습니다.

 

핵심 아이디어는 다음 한 문장으로 요약할 수 있습니다.

 

"기준 값(Pivot)을 하나 정하고, 그 값을 기준으로 배열을 둘로 나눈다."

• Pivot보다 작은 값 → 왼쪽
• Pivot보다 큰 값 → 오른쪽
• Pivot은 최종 위치가 확정됨

이 분할이 끝나면, Pivot은 더 이상 움직이지 않아도 되는 정렬 완료 상태가 됩니다. 그리고 Pivot을 제외한 왼쪽 / 오른쪽 부분 배열에 대해 같은 작업을 재귀적으로 반복합니다.

---

2. Divide → Conquer 단계의 의미

1) Divide(분할)

• 배열에서 Pivot 하나를 선택합니다.
• Pivot을 기준으로 작은 값과 큰 값으로 배열을 재배치합니다.
• 이 과정에서 Pivot은 자신의 최종 위치에 놓입니다.

이 단계에서 이미 부분적인 정렬 효과가 발생합니다. 즉, Merge Sort와 달리 Quick Sort는 분할 자체가 정렬 작업입니다.

 

2) Conquer(정복)

• Pivot을 기준으로 나뉜 왼쪽 / 오른쪽 부분 배열을 다시 Quick Sort합니다.
• 부분 배열의 크기가 0 또는 1이 되면 종료됩니다.

Quick Sort에는 Merge 단계가 없습니다. 대신 Partition(분할) 과정이 반복되면서 pivot들이 하나씩 확정되고, 그 결과가 누적되어 전체 정렬이 완성됩니다. Conquer는 이 Partition을 왼쪽/오른쪽 구간에 대해 재귀적으로 반복하는 단계입니다.

---

3. Partition(분할)의 핵심 동작

Quick Sort의 성능과 특성은 Partition(분할) 구현 방식에 의해 결정됩니다. Partition은 “Pivot을 기준으로 배열을 둘로 나누는 작업”인데, 이 작업이 배열 내부에서 swap만으로(in-place) 진행된다는 점이 Quick Sort의 핵심입니다.

 

아래는 가장 직관적인 Lomuto Partition 방식을 기준으로, Pivot을 기준으로 배열이 실제로 어떻게 재배치되는지 단계별로 살펴보겠습니다.

 

예제 배열

[38, 27, 43, 3, 9, 82, 10]

• Pivot = 마지막 원소 10
• 목표 = Pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 재배치
• 결과 = Pivot은 자신의 “최종 위치”가 확정됨

※ Pivot을 10으로 선택한 이유

Quick Sort에서 Pivot은 특정한 값으로 고정된 개념이 아니라, 어떤 위치의 원소를 기준으로 삼을지에 대한 구현 선택입니다.

이 예제에서는 Lomuto Partition 방식에서 가장 단순한 규칙인 “배열의 마지막 원소를 Pivot으로 선택”하는 방식을 사용했기 때문에, 결과적으로 마지막 값인 10이 Pivot이 되었습니다.

Pivot을 어디서 선택하느냐는 정렬의 정확성에는 영향을 주지 않으며, 분할의 균형에 따라 성능 특성에만 영향을 줍니다. 이번 예제의 목적은 성능 최적화가 아니라 Partition 동작 원리를 명확히 설명하는 것이므로, 가장 직관적인 방식으로 Pivot을 선택했습니다.

 

3.1 Lomuto Partition의 포인터 의미

Lomuto 방식은 포인터를 두 개 사용합니다.

• j: left부터 right-1까지 순회하며 “값을 검사”하는 포인터
• i: Pivot보다 작은 값이 들어갈 “다음 위치”를 가리키는 포인터

규칙은 단순합니다.

• array[j] <= pivot 이면 → array[i]와 array[j]를 swap하고 i를 1 증가
• 순회가 끝나면 → pivot(array[right])와 array[i]를 swap하여 pivot을 최종 위치로 보냄

즉, Partition이 끝나는 순간에는 다음 조건이 만족됩니다.

• [left .. i-1] 구간: pivot 이하
• [i]: pivot (최종 위치 확정)
• [i+1 .. right] 구간: pivot 초과

 

3.2 예제로 Partition 과정을 한 단계씩 따라가기

초기 상태에서 pivot = 10, i = left(0) 입니다. 그리고 j는 0부터 right-1까지(여기서는 0~5) 순회합니다.

초기:
array = [38, 27, 43, 3, 9, 82, 10]
pivot = 10 (right)
i = 0
j = 0 (0..5 순회)

[38, 27, 43, 3, 9, 82, 10]
 i
 j

 

(1) j=0 → 38 비교

array[j]=38, pivot=10
38 <= 10 ? NO
→ swap 없음, i=0 유지, j++ (1)

[38, 27, 43, 3, 9, 82, 10]
 i
     j

 

(2) j=1 → 27 비교

27 <= 10 ? NO
→ swap 없음, i=0 유지, j++ (2)

[38, 27, 43, 3, 9, 82, 10]
 i
         j

 

(3) j=2 → 43 비교

43 <= 10 ? NO
→ swap 없음, i=0 유지, j++ (3)

[38, 27, 43, 3, 9, 82, 10]
 i
             j

 

(4) j=3 → 3 비교 (pivot 이하 발견)

3 <= 10 ? YES
→ swap(array[i], array[j]) = swap(array[0], array[3])

swap 전: [38, 27, 43, 3, 9, 82, 10]
swap 후: [(3), 27, 43, (38), 9, 82, 10]
i++ (1), j++ (4)

[3, 27, 43, 38, 9, 82, 10]
    i
                j

여기서 중요한 관찰은, pivot 이하 값을 만나면 그 값을 “왼쪽 분류 구간”으로 보내고(i 위치), 그 다음 칸을 다음 후보 자리로 지정(i++)한다는 점입니다.

 

(5) j=4 → 9 비교 (pivot 이하 발견)

9 <= 10 ? YES
→ swap(array[i], array[j]) = swap(array[1], array[4])

swap 전: [3, 27, 43, 38, 9, 82, 10]
swap 후: [3, (9), 43, 38, (27), 82, 10]
i++ (2), j++ (5)

[3, 9, 43, 38, 27, 82, 10]
       i
                   j

 

(6) j=5 → 82 비교

82 <= 10 ? NO
→ swap 없음, i=2 유지, j++ (6)

[3, 9, 43, 38, 27, 82, 10]
       i
                       j

 

(7) 마지막: Pivot을 최종 위치로 보내기

j 순회가 끝났다면, 이제 pivot(맨 끝 값)을 i 위치로 옮깁니다. 이 swap 한 번으로 pivot은 “정렬된 최종 위치”가 확정됩니다.

마지막 swap: swap(array[i], array[right]) = swap(array[2], array[6])

swap 전: [3, 9, 43, 38, 27, 82, 10]
swap 후: [3, 9, (10), 38, 27, 82, (43)]
                 ↑
            pivot 최종 위치 (= 2)

 

Partition 결과를 구간으로 보면 다음이 성립합니다.

• 왼쪽 [3, 9] → pivot(10) 이하
• pivot [10] → 최종 위치 확정
• 오른쪽 [38, 27, 82, 43] → pivot 초과

즉, Quick Sort는 이 Partition을 수행할 때마다 pivot 하나가 정렬 완료(확정)되고, 남은 왼쪽/오른쪽 구간에 대해 같은 작업을 반복하면서 전체 정렬을 완성합니다.

 

3.2.1 다음 단계: 좌·우 부분 배열에 대해 Partition 반복

첫 번째 Partition이 끝난 시점에서 배열 상태는 다음과 같습니다.

[3, 9, 10, 38, 27, 82, 43]
        ↑
     pivot 확정

 

여기서 중요한 점은, pivot(10)은 이미 최종 위치가 확정되었으므로 더 이상 어떤 정렬에도 관여하지 않는다는 것입니다. 이제 Quick Sort는 pivot을 제외한 왼쪽 / 오른쪽 부분 배열에 대해 같은 작업을 재귀적으로 수행합니다.

• 왼쪽 부분 배열: [3, 9] (index 0~1)
• 오른쪽 부분 배열: [38, 27, 82, 43] (index 3~6)

√ 왼쪽 부분 배열 [3, 9] 정렬

왼쪽 부분 배열의 길이는 2이며, Lomuto Partition 규칙에 따라 마지막 원소 9를 pivot으로 선택합니다.

부분 배열: [3, 9]
pivot = 9
i = 0
j = 0

 

(1) j=0 → 3 비교

3과 9를 비교하면 3 <= 9이므로, swap은 발생하지만 자기 자신과의 swap이며 배열 상태는 변하지 않습니다.

3 <= 9 ? YES
→ swap(array[i], array[j]) = swap(array[0], array[0])

swap 전: [3, 9]
swap 후: [(3), 9]
i++ (1), j++ (1)

[3, 9]
    i
    j

 

(2) 마지막: Pivot을 최종 위치로 보내기

마지막으로 pivot(9)을 i 위치로 보내지만, 이미 올바른 위치에 있으므로 결과는 동일합니다.

[3, 9]
    ↑
pivot(9) 최종 위치 확정

 

이로써 왼쪽 부분 배열 [3, 9]는 완전히 정렬되었습니다.

---

√ 오른쪽 부분 배열 [38, 27, 82, 43] 정렬

이제 오른쪽 부분 배열에 대해 같은 과정을 반복합니다. 배열 상태는 다음과 같습니다.

부분 배열: [38, 27, 82, 43]
pivot = 43
i = 0
j = 0

* 주의:
  - 여기서는 설명을 위해 이 부분 배열을 인덱스 [0..3]으로 다시 매겨 진행합니다.
  - 실제 코드 기준으로는 이 구간이 전체 배열의 [3..6]에 해당하며,
    따라서 i와 j의 시작 값도 (코드상) i=3, j=3에서 시작합니다.

 

(1) j=0 → 38 비교

38 <= 43 ? YES
→ swap(array[i], array[j]) = swap(array[0], array[0])

swap 전: [38, 27, 82, 43]
swap 후: [(38), 27, 82, 43]
i++ (1), j++ (1)

[38, 27, 82, 43]
     i
     j

 

(2) j=1 → 27 비교

27 <= 43 ? YES
→ swap(array[i], array[j]) = swap(array[1], array[1])

swap 전: [38, 27, 82, 43]
swap 후: [38, (27), 82, 43]
i++ (2), j++ (2)

[38, 27, 82, 43]
         i
         j

 

(3) j=2 → 82 비교

82 <= 43 ? NO
→ swap 없음, i=2 유지, j++ (3)

[38, 27, 82, 43]
         i
             j

 

(4) 마지막: Pivot을 최종 위치로 보내기

마지막 swap: swap(array[i], array[right]) = swap(array[2], array[3])

swap 전: [38, 27, 82, 43]
swap 후: [38, 27, (43), (82)]
                   ↑
              pivot 최종 위치

 

이제 다시 두 부분 배열로 나뉩니다.

• 왼쪽: [38, 27]
• 오른쪽: [82] (길이 1 → 정렬 완료)

---

√ 부분 배열 [38, 27] 정렬

마지막으로 [38, 27]에 대해 Partition을 수행합니다. pivot은 마지막 원소 27입니다.

 

(1) j=0 → 38 비교

38 <= 27 ? NO
→ swap 없음, i=0 유지, j++ (1)

[38, 27]
 i
     j

 

(2) 마지막: Pivot을 최종 위치로 보내기

마지막 swap: swap(array[i], array[right]) = swap(array[0], array[1])

swap 전: [38, 27]
swap 후: [(27), (38)]
           ↑
      pivot 최종 위치

 

3.2.2 전체 정렬 완료

모든 재귀 호출이 종료되면, 배열 전체는 다음과 같이 정렬됩니다.

[3, 9, 10, 27, 38, 43, 82]

 

이 흐름을 통해 확인할 수 있듯이, Quick Sort는 Partition을 수행할 때마다 pivot 하나를 확정하고, 정렬되지 않은 영역을 점점 줄여가며 전체 정렬을 완성합니다.

 

즉, Merge Sort처럼 “병합 단계에서 정렬이 완성되는 구조”가 아니라, 분할(Partition) 단계 자체가 곧 정렬 과정이라는 점이 Quick Sort의 가장 중요한 특징입니다.

 

※ 동작을 시각적으로 확인해보기

아래 링크는 Quick Sort의 핵심 과정인 Pivot 선택 → Partition(분할) → 재귀 정렬 흐름을 단계별로 시각화해 주는 도구입니다. Quick Sort는 배열을 반으로 “잘라서 병합”하는 방식이 아니라, Pivot을 기준으로 왼쪽(작은 값) / 오른쪽(큰 값)으로 재배치하는 Partition 과정에서 정렬이 진행된다는 점이 핵심입니다. 시각화를 통해 Pivot이 한 번 확정될 때마다 정렬되지 않은 구간이 어떻게 줄어드는지, 그리고 재귀 호출이 어떤 구조로 이어지는지 직관적으로 확인할 수 있습니다.

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

---

4. 왜 평균 O(N log N)이 되는가

Quick Sort의 평균 시간 복잡도는 O(N log N)입니다. 이 역시 구조로 보면 직관이 생깁니다.

 

1) 평균 분할 깊이 = log N (균형 분할 가정)

Quick Sort는 Merge Sort처럼 배열을 “항상 반으로” 자르는 정렬이 아닙니다. 대신 Partition 결과가 pivot을 기준으로 어느 정도 균형 있게 나뉘는 경우가 평균적으로 많다는 가정에서 재귀 깊이가 log N 수준으로 내려갑니다.

 

예를 들어, 분할이 매번 대략 절반에 가깝게 일어난다고 가정하면(예: 4:6, 5:5 등), 구간 크기는 다음처럼 빠르게 줄어듭니다.

N
~ N/2
~ N/4
~ N/8
...

 

즉, “구간의 크기가 1이 될 때까지 대략 2로 나누는 단계 수”가 재귀 깊이가 되며, 그 깊이는 log₂N 수준입니다.

※ 왜 평균적으로 분할 깊이가 log N 인가 (수식으로 보기)

Quick Sort에서 분할 결과가 평균적으로 균형에 가깝게 이루어진다고 가정하면, 각 재귀 단계마다 정렬 대상 구간의 크기는 대략 절반 수준으로 줄어듭니다.

이를 수식으로 표현하면 다음과 같습니다.

N / (2^k) = 1

즉, 배열의 길이가 1이 되기까지 2로 몇 번 나누어야 하는가를 나타내는 식입니다.
양변에 2^k를 곱하면 다음과 같습니다.

2^k = N

이 식에서 k를 구하면,

k = log₂N

이 값이 바로 재귀 호출 트리의 평균 높이이며, Quick Sort가 균형 분할이 이루어질 경우 평균 O(N log N)이 되는 이유입니다.

단, 이는 어디까지나 평균적인 분할 상황을 가정한 설명이며, Pivot 선택이 계속 한쪽으로 치우치면 이 가정은 성립하지 않습니다.

 

2) 각 단계(레벨)의 비용 = O(N)

Partition 한 번은 해당 구간을 left부터 right-1까지 한 번 순회하며 swap을 수행합니다. 즉, 한 레벨에서 발생하는 “전체 스캔 비용”은 결국 O(N)으로 볼 수 있습니다.

• 분할 깊이(평균): log N
• 레벨당 Partition 총 작업량: N

따라서 평균 시간 복잡도는 O(N log N)이 됩니다.

※ 최악의 경우: O(N²)

Pivot이 매번 한쪽 끝으로 치우치게 선택되면 (예: 항상 최솟값 또는 최댓값을 pivot으로 선택하는 경우), Partition 결과는 매 단계마다 0 : (N−1) 형태로 나뉘게 됩니다.

 

이런 상황은 pivot을 항상 배열의 첫 번째 또는 마지막 원소로 선택하는 구현에서, 이미 정렬되어 있거나 거의 정렬된 입력 데이터가 주어질 때 쉽게 발생합니다. 이 경우 재귀 깊이는 N에 가까워지고, 각 단계에서 O(N) 크기의 스캔이 반복되므로 Quick Sort의 최악 시간 복잡도는 O(N²) 이 됩니다.

---

5. 공간 복잡도와 특징

Quick Sort는 배열 내부에서 swap만 수행하는 정렬입니다. 따라서 Merge Sort와 달리 추가 배열이 필요하지 않습니다.

• 추가 배열 메모리: 없음 (재귀 호출 스택은 사용)
• In-place 정렬: 입력 배열 내부에서 원소를 직접 교환(swap)하여 정렬하는 방식
• 안정 정렬이 아님(Stable X)

즉, Quick Sort는 공간 효율을 극대화한 대신, Pivot 선택에 따라 성능 편차가 발생하는 정렬입니다.

---

6. C# 기반 Quick Sort 구현

using System;

namespace Daebak.Common.Algorithms.Sorting
{
    /// <summary>
    /// Quick Sort (퀵 정렬)
    /// - Divide and Conquer(분할 정복) 기반 정렬
    /// - 평균 시간 복잡도: O(N log N)
    /// - 최악 시간 복잡도: O(N^2) (pivot 선택이 한쪽으로 치우칠 경우)
    /// - In-place 정렬 (추가 배열 사용 없음)
    /// - 안정 정렬 아님 (Stable X)
    /// </summary>
    public static class QuickSort
    {
        /// <summary>
        /// 외부에서 호출되는 진입점
        /// - 전체 배열을 대상으로 Quick Sort 시작
        /// </summary>
        public static void Sort(int[] array)
        {
            // null 이거나 원소가 0~1개면 이미 정렬된 상태
            if (array == null || array.Length <= 1)
            {
                return;
            }

            // 전체 구간 [0, Length-1]에 대해 Quick Sort 수행
            QuickSortRange(array, 0, array.Length - 1);
        }

        /// <summary>
        /// 배열의 특정 구간 [left, right]를 Quick Sort
        /// - Partition을 통해 pivot 하나를 확정
        /// - pivot 기준으로 왼쪽 / 오른쪽 구간을 재귀적으로 정렬
        /// </summary>
        private static void QuickSortRange(int[] array, int left, int right)
        {
            // 구간에 원소가 0개 또는 1개면 정렬할 필요 없음
            if (left >= right)
            {
                return;
            }

            // Partition 수행
            // pivot은 이 호출에서 "정렬 완료(확정)" 상태가 됨
            int pivotIndex = Partition(array, left, right);

            // pivot을 제외한 왼쪽 구간 정렬
            QuickSortRange(array, left, pivotIndex - 1);

            // pivot을 제외한 오른쪽 구간 정렬
            QuickSortRange(array, pivotIndex + 1, right);
        }

        /// <summary>
        /// Lomuto Partition 방식
        /// - pivot을 기준으로 배열을 두 구간으로 분리
        /// - pivot은 array[right] (구간의 마지막 원소)
        /// 
        /// 분할이 끝나면 다음 조건이 성립:
        /// - [left .. pivotIndex-1] : pivot 이하
        /// - [pivotIndex]           : pivot (최종 위치 확정)
        /// - [pivotIndex+1 .. right]: pivot 초과
        /// </summary>
        private static int Partition(int[] array, int left, int right)
        {
            // pivot은 구간의 마지막 원소로 선택
            int pivot = array[right];

            // i: pivot 이하 값이 들어갈 다음 위치
            int i = left;

            // j: left부터 right-1까지 순회하며 값을 검사
            for (int j = left; j < right; j++)
            {
                // 현재 값이 pivot 이하라면
                if (array[j] <= pivot)
                {
                    // pivot 이하 값을 왼쪽 분류 구간(i 위치)으로 이동
                    Swap(array, i, j);

                    // 다음 pivot 이하 값이 들어갈 위치로 i 증가
                    i++;
                }
            }

            // 마지막으로 pivot을 i 위치로 이동
            // 이 swap 한 번으로 pivot의 최종 위치가 확정됨
            Swap(array, i, right);

            // pivot의 최종 인덱스 반환
            return i;
        }

        /// <summary>
        /// 배열 내 두 인덱스의 값을 교환
        /// - Quick Sort는 swap 기반 정렬
        /// </summary>
        private static void Swap(int[] array, int a, int b)
        {
            int temp = array[a];
            array[a] = array[b];
            array[b] = temp;
        }
    }
}

---

7. Unity 환경에서 테스트

using UnityEngine;
using Daebak.Common.Algorithms.Sorting;

public class Test_QuickSort : MonoBehaviour
{
    private void Start()
    {
        int[] data = { 38, 27, 43, 3, 9, 82, 10 };

        Debug.Log("Before Sort : " + string.Join(", ", data));

        QuickSort.Sort(data);

        Debug.Log("After Sort : " + string.Join(", ", data));
    }
}

 

출력 결과

Before Sort : 38, 27, 43, 3, 9, 82, 10
After Sort : 3, 9, 10, 27, 38, 43, 82

---

8. 마무리

Quick Sort는 병합 없이 분할만으로 정렬을 완성하는 알고리즘입니다. Merge Sort와 동일한 평균 시간 복잡도를 가지면서, 공간 효율은 훨씬 뛰어나다는 장점이 있습니다. 반면, Pivot 선택이 나쁘면 성능이 급격히 떨어질 수 있기 때문에, 실무에서는 랜덤 Pivot이나 Median-of-Three 기법을 함께 사용합니다.

※ Pivot 선택 최적화 기법

• Random Pivot: Pivot을 무작위로 선택하여 입력 데이터 편향을 완화
• Median-of-Three: 첫 값, 중간 값, 마지막 값 중 중앙값을 Pivot으로 선택

두 기법 모두 분할이 한쪽으로 쏠리는 상황을 줄여 Quick Sort가 평균적인 성능(O(N log N))을 안정적으로 유지하도록 돕습니다.

이로써 O(N log N) 계열의 대표적인 두 정렬, Merge Sort와 Quick Sort의 구조적 차이를 모두 살펴봤습니다.

 

※ 다음 글에서는 Heap Sort를 살펴보며, 이진 힙(Binary Heap) 구조를 이용해 최댓값(또는 최솟값)을 반복적으로 선택하여 정렬을 완성하는 방식과, 이 방식이 입력 데이터의 형태와 무관하게 항상 O(N log N)을 보장하는 이유를 중심으로 정리합니다.