Heap/Radix/Quick Sort에 대하여

Quick Sort : O(NlogN), 최악의 경우 O(N^2)을 보장하는 소팅.

Heap Sort : O(NlogN)을 보장하는 소팅

Radix Sort : O(dN)을 보장하는 소팅(자리수)

으로 이론적으로만 알고있어서 오늘 구현해본결과, 속도차이가 그닥 나지않음을 발견했다

알고리즘공부하면서 Big-O표기법에 대해 항상 께림직했던게, 결국 Big-O는 수학에서 말하는 N이 충분히 큰 경우(sufficiently large) 계수는 무시할 수 있기에, 계수를 제외한 값을 표현해준다는 것이다.

Quick Sort는 별 할말이없다. 워낙 유명한 소팅이라.. 굳이 한마디 하자면 pivot을 그지같이 잡거나 해서 최악의 경우 N^2이라곤 하지만, 생각보다?(이름만큼?) 속도가 빠르다

Heap Sort

Heap Sort를 하려면 먼저 Heap Tree를 구성해야한다.

Heap Tree를 구성하는방식에는 상향식(Bottom-Up)과 하향식(Top-Down)이 있으나, 시간복잡도가 각각 O(N), O(NlogN)이라 하니 하향식은 패스.

(그림만보고 뭔말인지 이해하기는 쉽지않을것같다.. 쓸만한 그림이 없어서 이거라도..)

상향식 Heap Tree구성방법은 N/2부터시작해서 아래쪽으로 작은 Heap Tree를 순차적으로 구축해나가는 방식이다. (주의할 점은 N/2의 자식노드중 하나가 비어있다면 까먹지말고 꼭 처리해줄것)

그 후 Heap Sorting을 하는건데. Priority Queue를 구현해봐서 알겠지만 Heap Sorting의 시간복잡도는 O(NlogN)이다. 

하지만 간과하지 말아야 할 것은 앞서 구현했던 Heap Tree에서 N의 시간을 소모했기 떄문에 결국 총 필요한 시간은 엄밀히 말하면(N+1)logN이다.

물론 N이 충분히 커지면 NlogN≒(N+1)logN이지만 우리가 푸는 문제의 N범위가 어떤지에 따라 두 계수를 같은선상에 놓고 볼 것인지는 고민해 봐야 할 문제이다.

Radix Sort

처음 2016년 6월 첫 Expert시험에서 만난 Radix Sort는 정말 신세계였는데..

그럴만한 것이 이론상으로 자릿수를 엄청 크게 줘버리면 시간복잡도는 O(N)이 되버리니까..

   int i, b[MAX], m=0, exp=1;

 

    for( i=0 ; i<n ; i++ )

    {

        if( a[i] > m )

            m = a[i];

    }

 

    while( m/exp > 0 )

    {

        int bucket[자릿수] = {0};

         

        for( i=0 ; i<n ; i++ )

            bucket[a[i]/exp%자릿수]++;

 

        for( i=1 ; i<자릿수 ; i++ )

            bucket[i] += bucket[i-1];

 

        for( i=n-1 ; i>=0 ; i-- )

            b[--bucket[a[i]/exp%자릿수]] = a[i];

 

        for( i=0 ; i<n ; i++ )

            a[i] = b[i];

 

        exp *= 자릿수;

1. 먼저 배열의 맥시멈 값을 찾는다. (O(N))

2. bucket이라는 counting하는 배열을 만들어 가장 낮은자리수가 0~(자리수-1)까지 몇개씩 있는지 확인한다. 알기쉽게 10의자리수로 예를 들면, bucket[10]짜리 배열을 만들어서 bucket[i]에는 1의자리수가 i인 원소가 몇개있는지 카운팅한다(O(N))

3. 일의자리가 0인 원소가 몇개인지, 1인원소가 몇개인지 ... , 9인원소가 몇개인지 알았으니 배열의 뒷순서부터 차례대로 b라는 queue에 담는다(O(N), 1의자리기준으로 정렬완료)

4. 정렬된 b를 다시 원래배열 a에 붓는다(O(N))

이걸 자릿수만큼 반복한다 (*d)

결국 총 시간복잡도는 O((N+N+N+N)*d) = O(4dN)이고, 역시 N이 충분히 커지면 O(dN), O(N)이라 할 수 있지만.. 실제 성능은 글쎄.. N이 충분히 커야 제 성능을 발휘할듯

4번스탭을 줄이려고 애초에 a[N][2]인 배열을 잡아 idx를 1,0으로 변환시키며 붓는 방식으로 해봤는데

결국 그래도 3dN. 더 줄일 수 있는 방식이 있을 것 같긴 하지만, 문제에서 그정도로 깐깐한 시간을 주지 않고서는 구현해볼일이 없을 것 같음.

다만 유일한 희망은 사용할 수 있는 메모리양이 무지 크다면 자리수를 그만큼 크게잡아버리면된다..

(1~10000을 정렬할때 10000칸짜리 queue를 만들어버리면 while문이 한번만에 끝난다..)

Heap/Radix/Quick모두 알아두면 좋지만 시간이 충분히 남아 할게 없을 때 다른 정렬을 구현하여 시간을 줄여보도록하자. 다만 메모리가 충분히크다면 Radix, 전체 정렬이아닌 앞부분 일부의 정렬이 필요하다면 Heap을 쓰면 좋을 것 같다.