퀵 정렬 (C#)

📌 퀵 정렬(Quick Sort) 이란?

퀵 정렬(Quick Sort)은 평균적으로 매우 빠른 실행 속도를 보이는 정렬 알고리즘이다.
기본적인 원리는 '분할 정복(divide and conquer)' 전략을 사용하여,
한 번 분할될 때마다 최소한 한 개의 원소(피벗, pivot)가 최종 위치를 찾아가는 것이다.

퀵 정렬의 기본 원리:
1. 피벗 선택: 배열에서 하나의 원소를 선택한다. 이 원소를 중심으로 배열을 두 부분으로 나눈다.
2. 분할: 피벗보다 작은 원소는 피벗의 왼쪽, 큰 원소는 피벗의 오른쪽으로 이동시킨다.
3. 재귀적 정렬: 분할을 통해 생성된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.

퀵 정렬의 성능은 피벗 선택 방법에 크게 의존하며, 최악의 경우 O(n^2)의 시간 복잡도를 가지지만, 평균적으로는 O(n log n)의 시간 복잡도를 가진다.

첫 정렬 시 배열 처음을 left, 끝을 right로 지정
left가 right보다 작을 때만 정렬 가능
첫 Partition에 의해 나온 Pivot을 기준으로 좌, 우측 작은 배열이 나오고 재귀적으로 정렬을 진행

구현 코드

static void Main()
{
    QuickSort quickSort = new QuickSort();

    int[] arr = { 3, 5, 2, 1, 4 };
    Console.Write(string.Join(", ", arr));
    Console.WriteLine();

    quickSort.Sort(arr, 0, arr.Length - 1);
    Console.Write(string.Join(", ", arr));
}

class QuickSort
{
    public void Sort(int[] arr, int left, int right)
    {
        // 좌, 우 나눌 수 있는 상황에서 분할
        if(left < right)
        {
            int pivot = Partition(arr, left, right);

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

        // 피벗보다 작은 값이면 i++와 j 번째 값을 교체
        for (int j = left; j < right; j++)
        {
            if (arr[j] <= pivot)
            {
                i++;

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

        // 피벗의 자리를 교체
        int tempPivot = arr[i + 1];
        arr[i + 1] = arr[right];
        arr[right] = tempPivot;

        return i + 1;
    }        
}