퀵 정렬 (C#)

개요

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

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

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

 

시간복잡도

O(N log N)

 

코드

static int[] array = { 10, 9, 6, 3, 8, 1 };
 
        static void QuickSort(int start, int end)
        {
            if (start >= end) return;
            int pivot = start, i = start + 1, j = end, temp;
 
            while (i <= j)  //엇갈릴 때까지 반복
            {
                while (i <= end && array[pivot] >= array[i] ) //오른쪽으로 이동 (값을 바꿔야 할때까지..)
                    i++;
 
                while (i > start && array[pivot] <= array[j]) //왼쪽으로 이동 (값을 바꿔야 할때까지..)
                    j--;
 
                if (i > j)  //
                {
                    Swap(ref array[pivot], ref array[j]);
                }
                else
                {
                    Swap(ref array[i], ref array[j]);
                }
            }
 
            QuickSort(start, j - 1);
            QuickSort(j + 1, end);
        }
 
        private static void Swap(ref int a, ref int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }