IT가 만드는 재기 넘치는 세상

퀵 정렬 ( Quick Sort )은 "찰스 앤터니 리처드 호어"가 개발한 정렬 알고리즘으로 현재 정렬 알고리즘 중에 최고의

속도를 자랑하며 많이 쓰이는 정렬방식이다.

최악의 경우는 n² 번의 비교를 수행하고 평균적으로 n log n 번의 비교를 수행하여 정렬을 하고 실질적으로는

메모리 참조가 지역화 되어 있어 CPU 캐시의 히트율이 높아 정렬시 제곱 시간만큼 걸릴 확률이 거의 없도록

알고리즘을 설계하는 것이 가능함

기본 알고리즘

    - 배결 가운데 하나의 원소를 고르고 그 원소를 Pivot이라 부른다.

    - Pivot 보다 작은 값은 앞쪽(Left)에 값이 오고 큰 값은 뒷쪽(Right)에 값이 오도록 한다.

    - 이렇게 Pivot의 위치가 정해지면 분할된 양쪽의 배열을 재귀적으로 이 과정을 반복함.

위의 그림과 같이 배열의 0번째 인덱스 ( 재귀 호출시에는 가장 앞쪽의 배열이 0번째 인덱스가 됨 )가 Pivot으로 정하여 해당

값 보다 작은 값은 왼쪽 큰 값은 오른쪽으로 이동하게 조건을 이용하여 분할 하였으며 이렇게 호출된 메서드는 완료시

하나의 pivot index가 정해지고 더이상 분할되지 않을때까지 재귀적으로 호출하여 값을 정렬 함

이 알고리즘의 이상적인 상태는 pivot이 되는 값이 양쪽을 균일하게 분할되게 하는 값일때 가장 빠른 속도를 낼수 있음

using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] nArr = new int[]{ 1, 4, 3,  5, 9, 6, 2, 7, 8, 10 };

            quick_sort( nArr, 0, nArr.Length-1);

            for (int i = 0; i < nArr.Length; i++)
                Console.Write(nArr[i] + "\t");
        }
        private static int ArryDivide(int[] Arry, int left, int right)
        {
            int PivotValue, temp;
            int index_L, index_R;

            index_L = left;
            index_R = right;

            //Pivot 값은 0번 인덱스의 값을 가짐
            PivotValue = Arry[left];

            while(index_L < index_R)
            {
                //Pivot 값 보다 작은경우 index_L 증가(이동)
                while ( (index_L <= right) && (Arry[index_L] < PivotValue) )
                    index_L++;

                //Pivot 값 보다 큰경우 index_R 감소(이동)
                while ( (index_R >= left)  && (Arry[index_R] > PivotValue) )
                    index_R--;

                //index_L 과 index_R 이 교차되지 않음
                if(index_L < index_R)
                {
                    temp = Arry[index_L];
                    Arry[index_L] = Arry[index_R];
                    Arry[index_R] = temp;

                    //같은 값이 존재 할 경우 
                    if (Arry[index_L] == Arry[index_R])
                        index_R--;
                }
            }

            //index_L 과 index_R 이 교차된 경우 반복문을 나와 해당 인덱스값을 리턴
            return index_R;
        }
        private static void quick_sort( int[] arry, int left, int right)
        {
            if(left < right)
            {
                int PivotIndex = ArryDivide(arry, left, right);

                quick_sort( arry, left, PivotIndex - 1);
                quick_sort( arry, PivotIndex + 1, right);
            }
        }
    }
}

결과

장점

    - 현재 모든 정렬 알고리즘보다 빠른 속도를 자랑한다

    - 평균적으로 n log n 번의 비교를 수행 하지만 메모리 참조가 지역화 되어 제곱 시간만큼 시간 복잡도가 걸리지 않음

    - 고정적으로 log n 만큼의 메모리를 필요로 함

단점

    - 정렬시 불균형하게 분할되 수행시간이 차이가 날수 있다.

정렬 알고리즘 테스트

• 버블 정렬 ( Bubble Sort ) Post 참고
• 삽입 정렬 ( Insertion Sort ) Post 참고
• 선택 정렬 ( Selection Sort ) Post 참고