C# - 퀵 정렬(Quick Sort)

퀵정렬(Quick Sort)

퀵 정렬에서는 피벗(Pivot)을 기준으로 배열을 분할하고, 각 부분 배열에 대해 정렬 작업을 수행하지만 피벗을 다시 처리하는 부분 문제는 호출하지 않는다. 한 번 피벗의 위치가 정해지면 해당 피벗은 정렬이 완료된 것으로 취급되어 중복 계산이 발생하지 않는다.

핵심 : 키 값을 잡아 더 큰것과 더 작은것 바꾸기

---

01 피벗 선택

퀵 정렬의 핵심은 피벗(pivot)을 선택하는 것이다. 피벗은 배열의 원소 중에서 하나를 선택한다. 피벗 선택의 효율성이 정렬 속도에 영향을 미친다.

02 분할

선택된 피벗을 기준으로 배열을 두 부분으로 분할한다. 피벗보다 작은 값은 피벗의 왼쪽으로, 큰 값은 피벗의 오른쪽으로 배치된다. 분할 과정 후에는 피벗의 위치가 최종적으로 결정된다.

03 정복

분할된 두 부분 배열에 대해 재귀적으로 퀵 정렬을 수행한다. 각 부분 배열은 독립적으로 정렬되며, 정렬이 완료된 후에는 피벗의 위치가 확정된다.

04 결합

정렬된 부분 배열들을 결합하여 최종적으로 정렬된 배열을 얻는다. 결합된 배열은 피벗을 기준으로 왼쪽은 작은 값들, 오른쪽은 큰 값들로 구성된다.

---

코드

01 피벗 선택

int pivot = arr[0];

02 분할(Partition)

while (i <= j)
{
    while (i <= j && arr[i] <= pivot) // 값이 피벗보다 작거나 같을 때
        i++;
    while (j >= i && arr[j] > pivot)// 값이 피벗보다 클때
        j--;

    if (i < j)
    {
        // Swap arr[i] and arr[j]
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

 

03 피벗을 최종 위치에 넣기

i와 j가 교차하게되면 j는 피벗이 들어가야할 최종 위치가 된다. j를 선택하는 이유는 j의 위치에서 왼쪽들의 값은 피벗보다 작거나 같은 값들이기 때문이다.

int tempPivot = arr[0];
arr[0] = arr[j];
arr[j] = tempPivot;

 

---

04 정복

1) 왼쪽

List<int> leftSubarray = QuickSort(arr.GetRange(0, j), j);

 

2) 오른쪽

List<int> rightSubarray = QuickSort(arr.GetRange(j + 1, n - j - 1), n - j - 1);

---

04결합

List<int> sortedArray = new List<int>();

sortedArray.AddRange(leftSubarray);
sortedArray.Add(pivot);
sortedArray.AddRange(rightSubarray);

 

---

예시 문제

List<int> array = new List<int> { 5, 1, 9, 3, 7, 6, 8, 2, 4 };
List<int> sortedArray = QuickSort(array,9);

 

과정

1) i<= j arr[i]는 pivot보다 큰 값을 찾고 arr[j]는 pivot보다 작은 값을 찾으면 swap

arr[2]와 arr[8] swap

arr[4]와 arr[7] swap

2) 반복문을 빠져나오고 마지막 arr[j]에 pivot값 넣기

3) 왼쪽 오른쪽 분할시킨 다음 재귀로 똑같이 구하기

 

 

---

시간 복잡도

최선의 경우

T(n) = O(nlog₂n)

피벗의 선택이 항상 중간 값일때

순환 호출의 깊이(n) * 각 순환 호출 단계의 비교 연산 ( log₂n )

 

최악의 경우

T(n) = O(n^2)

이미 정렬된 배열에서 피벗이 항상 최솟값이나 최댓값으로 선택될 때

순환 호출의 깊이(n) * 각 순환 호출 단계의 비교 연산 ( logn )

---

정리

장점

데이터 이동 최소화: 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동시키므로 데이터 이동이 최소화된다.
시간 복잡도: 평균적으로 O(n log n)으로 다른 정렬 알고리즘에 비해 빠르다.

---

단점

불안정 정렬: 동일한 값에 대해 상대적인 순서가 변할 수 있다. 피벗 값의 상대적인 크기에 따라 요소들이 서로 교환되기 때문에 동일한 값을 가진 요소들의 상대적인 순서가 유지되지 않을 수 있다.
최악의 경우 시간 복잡도: 피벗의 선택이 최악인 경우 O(n^2)이다.
정렬된 배열 효율성: 이미 정렬된 배열에 대해 효율성이 떨어진다.

---

불안정 정렬이란?

동일한 값을 가진 요소들이 상대적인 순서가 정렬 이전과 정렬 이후에 유지되지 않을 수 있는 정렬 알고리즘을 의미한다. 정렬된 결과에서 동일한 값을 가진 요소들간에 상대적인 순서가 보장되지 않을 수 있다.

예시

정렬 전: [3a, 2, 1, 3b]
정렬 후: [1, 2, 3b, 3a] 또는 [1, 2, 3a, 3b]

---

코드 전문

static List<int> QuickSort(List<int> arr,int n)
{
    if (arr.Count == 0)
    {
        return new List<int>();
    }
            
    int pivot = arr[0];

    int i = 1;
    int j = n - 1;
    
    while (i <= j)
    {
        while (i <= j && arr[i] <= pivot)
            i++;
         while (i <= j && arr[j] > pivot)
            j--;

        if (i < j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int tempPivot = arr[0];
    arr[0] = arr[j];
    arr[j] = tempPivot;

    List<int> leftSubarray = QuickSort(arr.GetRange(0, j), j);
    List<int> rightSubarray = QuickSort(arr.GetRange(j + 1, n - j - 1), n - j - 1);
    List<int> sortedArray = new List<int>();

    sortedArray.AddRange(leftSubarray);
    sortedArray.Add(pivot);
    sortedArray.AddRange(rightSubarray);
    
    return sortedArray;
}