퀵 정렬 (C#)

개요

퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 에 속한다.
분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법
합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다.

분할 정복(divide and conquer) 방법
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.

과정
리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
리스트의 크기가 0이나 1이 될 때까지 반복한다.

 

시간복잡도

O(N log N)

 

코드

private void DoQuickSort(int startIndex, int endIndex, int[] array)
{
    if (startIndex >= endIndex)
        return;
 
    int partitionIndex = Partition(startIndex, endIndex, array);
    
    // 왼쪽 부분 정렬
    DoQuickSort(startIndex, partitionIndex, array);
    
    // 오른쪽 부분 정렬
    DoQuickSort(partitionIndex + 1, endIndex, array);
}
 
private int Partition(int startIndex, int endIndex, int[] array)
{
    // 피벗을 랜덤으로 선택한다.
    Random random = new Random();
    int pivotIndex = random.Next(startIndex, endIndex + 1);
 
    // 피벗 값만 저장 (인덱스는 저장안함.)
    int pivot = array[pivotIndex];
 
    int leftMarker = startIndex - 1;
    int rightMarker = endIndex + 1;
    
    while (true)
    {
        // 피벗보다 큰 값을 찾을 때까지 오른쪽으로 이동
        while (array[++leftMarker] < pivot)
        {
            if (leftMarker >= endIndex)
                break;
        }
 
        // 피벗보다 작은 값을 찾을 때까지 왼쪽으로 이동
        while (array[--rightMarker] > pivot)
        {
            if (rightMarker <= startIndex)
                break;
        }
 
        
        // 마커가 교차했다면 정렬 완료.
        // 분할 지점을 반환한다.
        if (leftMarker >= rightMarker)
            return rightMarker;
            
        // 왼쪽에 작은 값, 오른쪽에 큰값을 위치
        Swap(ref array[leftMarker], ref array[rightMarker]);
    }
}