C# - 퀵 정렬 (Quick Sort)

⚡ 퀵 정렬 (Quick Sort) – 빠르고 강력한 분할 정복 정렬 알고리즘

1. 개념

퀵 정렬은 분할 정복(Divide and Conquer) 전략을 사용하는 정렬 알고리즘이다.
중간 기준값(피벗)을 선택하여 작은 값은 왼쪽, 큰 값은 오른쪽으로 나눈 뒤,
각 부분을 재귀적으로 정렬하는 방식으로 작동한다.

---

2. 작동 방식 요약

1. 피벗(Pivot)을 선택
2. 피벗보다 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 분할
3. 각 부분 배열에 대해 재귀적으로 퀵 정렬 수행
4. 병합 없이 정렬 완료

---

3. C# 예제 코드 (새로운 예시)

void QuickSort(int[] arr, int left, int right)
{
    if (left >= right) return;

    int pivotIndex = Partition(arr, left, right);

    QuickSort(arr, left, pivotIndex - 1);
    QuickSort(arr, pivotIndex + 1, right);
}

int Partition(int[] arr, int left, int right)
{
    int pivot = arr[right];
    int i = left - 1;

    for (int j = left; j < right; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;
            (arr[i], arr[j]) = (arr[j], arr[i]); // C# 튜플 스왑
        }
    }

    (arr[i + 1], arr[right]) = (arr[right], arr[i + 1]);
    return i + 1;
}

✅ 사용 예:

int[] data = { 8, 4, 7, 3, 10, 2 };
QuickSort(data, 0, data.Length - 1);

---

4. 시간/공간 복잡도

경우	시간 복잡도
평균	O(n log n)
최악 (피벗 선택이 최악일 때)	O(n²)

 

• 공간 복잡도: O(log n) (재귀 호출 스택)

---

5. 특징

• 비교 기반 정렬 중 매우 빠름
• 불안정 정렬 (같은 값의 순서가 바뀔 수 있음)
• 제자리 정렬(In-place): 별도 배열이 필요하지 않음
• 피벗 선택 방식에 따라 성능이 달라짐 (랜덤 피벗, 중앙값 등 개선 가능)

---

6. 예시

[5, 2, 8, 1, 6]
→ 피벗: 6 → [5, 2, 1] [6] [8]
→ 왼쪽 정렬: [2, 1, 5] → [1, 2, 5]
→ 최종 정렬: [1, 2, 5, 6, 8]

---

7. 마무리 요약

• 퀵 정렬은 많은 데이터에 빠르게 정렬을 수행할 수 있는 알고리즘이다.
• 다만, 피벗 선택을 잘못하면 성능이 급격히 나빠질 수 있기 때문에, 개선된 버전(랜덤 피벗, 3-way 퀵 정렬 등)도 많이 활용된다.
• 실제 라이브러리 내부에서도 자주 사용됨.