C 로 구현한 알고리즘 - 3부 알고리즘, 12장. 정렬과 탐색

12장에서는 Divide-and-Conquer 의 대표적인 예인,

퀵소트(Quicksort)와 머지소트(Mergesort)를 알아보겠다.

이진 탐색은 굳이 설명할 필요성도 못 느끼겠다.

학교 다닐 때, 교수님이 소트를 가르키다가 소트를 왜 하나요? 라는 질문을 한 적이 있었다.

그 땐, 그런거 생각할 정신이 없었던거 같다. 조금만 생각해보면 쉬운걸...

당연히 자료를 찾기 쉽도록(탐색) 하기 위해서다...

머, 여기까지만 하고, 이번에는 대표적인 D&C 방법의 소트인

퀵소트와 머지소트를 알아보고, 부가적으로 소트에 대한 이야기를 조금 하겠다.

먼저, 소트에 대한 이야기

Sorting(정렬)

( http://en.wikipedia.org/wiki/Sorting_algorithm )

- "in place"(인플레이스) : 어떤 Sorting Algorithm이 "in place" 라는 말은, 원본 데이터 공간에서 Sorting을 한다는 말이다.

                                    즉, Sorting을 위한 추가 저장공간이 필요하지 않다는 말이다.

                                    (물론 Swap 을 위한 상수크기의 공간정도는 필요하다.)

- Stability(안정성) : Sorting 되지 않은 데이터들 중, 같은 Key값을 가지고 있는 A, B가 있다고 가정하자.

                           Sorting 후에도 이 A, B의 Order가  바뀌지 않는다면 이 Sorting Algorithm은 Stability를 가진다고 한다.

Quicksort(퀵소트)

( http://en.wikipedia.org/wiki/Quicksort )

퀵소트는 대표적인 Divide and Conquer 알고리즘이다.

퀵소트는 주어진 리스트를 임의의 값(Pivot)을 기준으로 큰 리스트와 작은 리스트로 나누고,

두 리스트에 대해서 Recusive하게 퀵소트를 실행하는 과정으로 리스트를 정렬한다.

그리고 퀵소트는 in place sorting 이다.

int 형에 대해서 퀵소트를 하는 C 함수는 다음과 같다.

void qsort_int(int *d, int s, int e) {
    int p = d[e];
    int i = s, j = e;

    if(s == e)
        return ;

    while(i < j) {
        while(i < j && d[i] < p) i++;
        while(j > i && d[j] > p) j--;
        if(i < j) {
            swap_int(&d[i], &d[j]);
            i++;
        }
    }
    swap_int(&d[i], &d[e]);

    qsort_int(d, s, i-1);
    qsort_int(d, i, e);
}

Mergesort(머지소트, 합병정렬)

( http://en.wikipedia.org/wiki/Merge_sort )

Divide and Conquer 알고리즘의 또 다른 예이다.

머지소트는 주어진 리스트를 반으로 나누고,

두 리스트에 대해서 Recusive하게 머지소트를 수행한다.

정렬된 두 리스트에 대해서 정렬된 하나의 리스트로 합병한다.

퀵소트와의 차이점은,

1. 정렬할 자료의 크기만큼의 추가 저장공간이 필요하다는 점.

2. 최악의 경우에도 시간복잡도는 O(n log n) 이라는 점.

3. Stable 한 정렬이라는 점. (같은 key 의 자료에 대해서 order 가 유지된다는 말)

4. 전체 자료 집합 모두를 동시에 메모리에 유지하지 않으면서도 수행가능 하다는 점.

   (아주 큰 자료일 경우 유용하다)

정도랄까?

시각적으로 표시하면 아래와 같다.

(출처: http://en.wikipedia.org/wiki/File:Merge_sort_algorithm_diagram.svg )

int형에 대해서 머지소트를 수행하는 C함수는 다음과 같다.

void msort_int(int *d, int s, int e) {
    int c = (s+e)/2;
    int i = s, j = c+1, k = 0;
    int *d2 = NULL;

    if(s == e)
        return ;

    msort_int(d, s, c);
    msort_int(d, c+1, e);

    d2 = (int*)malloc(sizeof(int)*(e-s+1));

    while(i <= c && j <= e) {
        if(d[i] < d[j])
            d2[k++] = d[i++];
        else
            d2[k++] = d[j++];

        if(i > c)
            while(j <= e) d2[k++] = d[j++];
        if(j > e)
            while(i <= c) d2[k++] = d[i++];
    }

    memcpy(&d[s], d2, sizeof(int)*(e-s+1));
    free(d2);
}

(메모리 할당 관련 오류 처리코드는 빠져있다. 실사용을 위해서는 추가 저장공간에 대하여 적절히 고려되어야 하겠다)

결론

Divide and Conquer 은 참 좋은 알고리즘이다. 쉽고, 병렬처리에도 좋고...

하지만 Dynamic Programming을 사용해야 하는 곳에 사용하게 되면 끔찍해 진다는거..