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 참고

정렬하고자 하는 배열중 최소의 값을 찾아 차례 차례 순서에 따라 값을 교체 해주는 방식으로 최소값을 찾는 시간은

처음 찾을때 보다 정렬이 진행 될수록 찾는 시간이 단축되는 구조 입니다.

  - 검색 시작지점은 배열의 인덱스 0부터 시작하며 진행순서에 따라 시작지점 인덱스는 1씩 증가

  - 최소값 또는 최대값을 가진 인덱스를 찾고 시작 인덱스와 교환

위의 사진처럼 오름차순으로 정렬을 진행할때 회차에 따라 시작인덱스는 1씩증가되며 시작인덱스 외의 나머지 인덱스들을

검색하여 가장 작은 값을 찾아 교환해주는 방식으로 진행됩니다.

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 };
            int TargetIndex, temp;

            //배열의 마지막 값은 자연스럽게 정렬이 되므로 배열크기 -1 만큼 반복
            for(int i = 0; i < nArr.Length-1; i++)
            {
                //정렬방식에 따라 교환이 이루어질 인덱스
                TargetIndex = i;

                //비교대상 인덱스는 시작인덱스 +1 에서 배열의 마지막까지 반복
                for(int j = i+1; j < nArr.Length; j++)
                {
                    //정렬방식 < : 오름차순, > : 내림차순
                    if (nArr[j] < nArr[TargetIndex])
                        TargetIndex = j;
                }
                
                if( i != TargetIndex)
                {
                    //검색을 시작한 가장 앞쪽 인덱스와 교환
                    temp = nArr[i];
                    nArr[i] = nArr[TargetIndex];
                    nArr[TargetIndex] = temp;
                }
            }

            for (int i = 0; i < nArr.Length; i++)
                Console.Write(nArr[i] + "\t");
        }
    }
}

결과

장점

    - 비교적 쉬운 코드로 구현 가능

    - 정렬이 진행됨에 따라 속도는 빨라짐

    - 버블 정렬보다 값의 복사와 이동이 적어 비교적 빠름

단점

    - 데이터의 크기가 커질수록 효율이 떨어짐

    - 데이터 정렬 속도가 고정적으로 n의 제곱만큼 걸려 더이상의 정렬 속도를 기대할수 없음

정렬 알고리즘 테스트

시간적인 측면에서는 고정적으로 정렬시간이 안정적이지만 더이상의 속도를 낼수 없고 구현이 간단한 정렬방식의

구조적 한계 때문에 비효율적인 방법 입니다.

• 버블 정렬 ( Bubble Sort ) Post 참고
• 삽입 정렬 ( Insertion Sort ) Post 참고
• 퀵 정렬 ( Quick Sort ) Post 참고

버블 정렬과 같이 단순 비교문을 이용하여 정렬하고자 하는 값를 옴겨 놓는 방식은 비슷하나

키( Key )에 해당하는 값을 정하고 앞쪽의 하나씩 비교 대상 값과 비교하여 위치를 옴겨 놓는 방식

- key 값은 배열의 두번째 인덱스 값부터 시작하며 1회당 인덱스를 1씩 증가시켜 배열의 끝까지 도달합니다.

- 비교 대상 ( compare ) 값은 key 인덱스보다 -1 낮은 인덱스부터 시작하며 1회당 -1씩 감소 시켜 배열의 처음까지 도달합니다.

- 비교 조건(오름차순, 내림차순)에 해당한다면 값을 교환 변경 합니다.

key의 시작 인덱스 : 1

comare의 시작 인덱스 : 0

위의 사진과 조건에 해당할때만 값의 복사가 일어나서 버블 정렬과 다르게 시간을 단축시키는 요소가 생깁니다.

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 };

            // nKey : 키 값
            // nCompareIndex : 비교 값이 되는 인덱스
            // nCount : 값의 교환 횟수
            int nKey, nCompareIndex, nCount; 
            nCount = 0;

            // 코드의 이해를 돕기위해 반복문의 인자 값을 이용목적으로 변수이름을 사용
            // 시작 키 인덱스 : 1
            for (int KeyIndex = 1; KeyIndex < nArr.Length; KeyIndex++)
            {
                nKey = nArr[KeyIndex];

                // 시작 비교 인덱스 : 0
                // nArr[nCompareIndex] > nKey : 오름차순
                // nArr[nCompareIndex] < nKey : 내림차순
                for (nCompareIndex = KeyIndex - 1; nCompareIndex >= 0 && nArr[nCompareIndex] > nKey; nCompareIndex--)
                {
                    nArr[nCompareIndex + 1] = nArr[nCompareIndex];
                    nCount++;
                }

                nArr[nCompareIndex + 1] = nKey;
            }

            Console.WriteLine("Count : {0}", nCount);

            for (int i = 0; i < nArr.Length; i++)
                Console.Write(nArr[i] + "\t");

        }
    }
}

결과

장점

    - 비교적 쉬운 코드로 구현 가능

    - 데이터의 크기가 작을 수록 복잡한 코드로 구현된 정렬보다 빠를수 있음

    - 같은 구현 난이도의 버블 정렬보다 정렬 속도의 이점을 가지고 있음

단점

    - 데이터의 크기가 커질수록 효율이 떨어짐

    - 최악의 경우 비교 횟수와 교환 횟수가 버블정렬과 같이 n의 2승만큼 커질수 있음

정렬 알고리즘 테스트

단적인 측면에서는 버블 정렬보다는 빠르지만 근본적인 효율에서는 비효율적인 방법 입니다.

• 버블 정렬 ( Bubble Sort ) Post 참고
• 선택 정렬 ( Selection Sort ) Post 참고
• 퀵 정렬 ( Quick Sort ) Post 참고

인접한 두 원소를 비교 하여 정렬하는 방법입니다.

단순히 A > B  라는 조건식을 이용하여 1회전 마다 큰 값이든 작은 값이든 하나씩 위치를 맞춰가는 방식으로

정렬하고자 하는 자료의 n의 2승만큼 반복하여 정렬합니다.

- 오름 차순 : 작은 값을 먼저 오게 만드는 정렬 방식 ( 1, 2, 3 ... )으로 A>B 라면 교환하여 정렬합니다.

- 내림 차순 :  큰 값을 먼저 오게 만드는 정렬 방식 ( ... 3, 2, 1 ) 으로 A<B 라면 교환하여 정렬합니다.

내림차순

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 };

            int nTemp;
            int nCount = 0;
            for(int i = 0; i < nArr.Length-1; i++)
            {
                for (int j = 0; j < nArr.Length-1; j++)
                {
                    if(nArr[j] < nArr[j+1])  
                    {
                        nTemp = nArr[j+1];
                        nArr[j+1] = nArr[j];
                        nArr[j] = nTemp;
                    }
                    nCount++;
                }
            }

            Console.WriteLine("Count : {0}", nCount);

            for(int i = 0; i < nArr.Length; i++)
                Console.Write(nArr[i] + "\t");
        }
    }
}

결과

조건식만 바꿔준다면 오름차순으로 정렬됩니다. ( nArr[j] > nArr[j+1] )

결과에서 알수있듯 총 비교횟수는 81회입니다. 이는 데이터 총갯수 - 1의 2승 만큼 계산되어 진것으로 연산순서는

아래와 같습니다.

//------- 시작 --------
// 1 4 3 5 9 6 2 7 8 10
//------- 1 회 --------
// 4 1 3 5 9 6 2 7 8 10
// 4 3 1 5 9 6 2 7 8 10
// 4 3 5 1 9 6 2 7 8 10
// 4 3 5 9 1 6 2 7 8 10
// 4 3 5 9 6 1 2 7 8 10
// 4 3 5 9 6 2 1 7 8 10
// 4 3 5 9 6 2 7 1 8 10
// 4 3 5 9 6 2 7 8 1 10
// 4 3 5 9 6 2 7 8 10 1

//------- 2 회 --------
// 4 3 5 9 6 2 7 8 10 1
// 4 5 3 9 6 2 7 8 10 1
// 4 5 9 3 6 2 7 8 10 1
// 4 5 9 6 3 2 7 8 10 1
// 4 5 9 6 3 2 7 8 10 1
// 4 5 9 6 3 7 2 8 10 1
// 4 5 9 6 3 7 8 2 10 1
// 4 5 9 6 3 7 8 10 2 1
// 4 5 9 6 3 7 8 10 2 1
// ...

장점

- 구현이 간단하다

단점

- 구조상 모든 요소들을 비교하고 이동시키기 때문에 효율적이지 못하다

일반적으로 자료의 이동 보다 교환 작업이 연산 작업이 복잡하기 때문에 구현의 단순성에도 불구하고

거의 쓰이지 않습니다.

• 삽입 정렬 ( Insertion Sort ) Post 참고
• 선택 정렬 ( Selection Sort ) Post 참고
• 퀵 정렬 ( Quick Sort ) Post 참고