Radix 정렬 구현

기수 정렬을 구현해보자

 

기수 정렬의 가장 큰 특징은 "정렬 순서상 앞서고 뒤섬의 판단을 위한 비교연산을 하지 않는다"

 

기본적으로 정렬 알고리즘의 이론상 성능의 한계는 O(nlog2n)으로 알려져 있는데

 

기수 정렬은 이러한 한계를 넘어설 수 있는 유리한 알고리즘이다.

 

다만 기수정렬의 단점은 범위가 매우 제한 적이다.

 

위에서 말하는 단점, 즉 범위의 정확한 뜻은 '데이터의 길이' 이다.

 

왜 데이터의 길이가 문제인가 하면 저장하는 버퍼, 즉 버킷의 갯수의 영향을 미치며

 

데이터 길이에 따른 별도의 알고리즘이 들어가야 한다. 별도의 알고리즘이 들어가면서 까지 기수 정렬은 효율적이지 않기 때문에

 

실제 사용하는 자료구조에서는 기수정렬을 많이 사용하지 않는다.

 

다음 그림은 한자릿 수의 기수정렬을 보여준다. 

 

 

 

원리는 간단하다.

 

들어가야할 자료구조를 보고 해당 버킷에 넣은다음 순서대로 꺼내면 자동으로 정렬이 되어 나온다.

 

버킷의 갯수는 들어가야할 자료의 유형(기수)에 맞게 만들어진다. 지금은 한자리 수, 10진수 자료구조가 들어가기 때문에 버킷이 10개가 만들어졌다.

 

만약 10진수가 아닌 16진수라면? 버킷의 갯수는 그만큼 늘어난다. (0 ~ F)

 

이렇든 기수정렬은 기수를 이용한 정렬 방식이기 때문에  세자릿수, 네자릿수 정수들을 정렬할 때에도, 이들이 10진수면 버킷 갯수는 10개가 필요, 16진수면 16개가 필요하다.

 

세자릿 수의 기수 정렬을 해보자.

 

기수 정렬의 자릿수가 늘어나면 방법이 LSD, MSD 정렬 방법이 있는데 여기서는 LSD 방식만 설명한다.

 

LSD는 Least, Significant Digit의 약자로 덜 중요한 자릿수에서부터 정렬을 진행해 나간다는 의미를 담고 있다.

 

{234, 132, 342, 143} 이란 3자릿 수를 가지고 정렬을 해보자. (1~4까지 있으므로 버킷은 4개만 생성)

 

우선 1번째로 첫번째 자릿수를 정렬 기준으로 두어 정렬을 한다.

버킷에 넣은다음 순서대로 꺼내면 다음과 같이 정렬 된다.

{234, 132, 342, 143}  => {342, 132, 143, 234}

 

1. 에서 정렬 된 배열을 가지고 두번째 자릿수를 정렬 기준으로 두어 정렬을 한다.

 

1.과정과 마찬가지로순서대로 꺼내면 다음과 같이 정렬 된다.

{342, 132, 143, 234} => { 234, 132, 143, 342}

 

2. 에서 정렬 된 배열을 가지고 세번째 자릿수를 정렬 기준으로 두어 다시 정렬한다.

 

마지막 자릿수 까지 정렬하면 다음과 같이 오름차순으로 정렬이 된다.

 

{132, 143, 234, 342}

 

LSD의 단점은 작은 자릿수 부터 비교를 해야하기 떄문에 중간에 대소를 판단하는 것을 불가능 하다는 단점이 있다.

 

하지만 이러한 단점이 프로그래밍하는데 있어서는 장점이 된다.( 구현이 MSD 보다 쉬운듯 ㅡ.ㅡv)

 

실제 코드를 구현 해보자.

 

우선 버킷은 Linked List 로 구현 하였으며 FIFO를 만족 시키기 위해 다음과 같이 구현하였다.

 

linkedListInit()

/* @bref     Linked List 초기화 함수
 * @detail  첫 head를 구별하기 위해 head의 데이터는 deadbeef로 하였다.
 *
 * @retval  head의 주소
 */
Node *linkedListInit()
{
    Node *_new = malloc(sizeof(Node));

    _new->next = NULL;
    _new->data = 0xdeadbeef;

    return _new;
}

 

linkedListInsert()

/* @bref    Linked List Insert 함수
 * @detail  Malloc으로 Node를 할당 받은 다음 연결한다.
 *          Malloc된 메모리에 데이터를 추가한다.
 *
 * @param   head: 연결 해야할 Node
 *          data: 추가해야 할 데이터
 *
 * @retval  None
 */
int linkedListInsert(Node *head, int data)
{
    Node *_new = malloc(sizeof( Node));
    Node *_local = head;

    while (_local->next != NULL)
    {
        _local = _local->next;
    }

    _new->data = data;
    _local->next = _new;
    _new->next = NULL;

    return 0;
}

 

linkedListGet_FIFO()

/**
 * @bref     LinkedList 데이터 꺼내는 함수
 * @detail   FIFO 구조이므로 head의 첫번째 Node 값을 가지고 온다음 free 한다.
 *           데이터가 0xdeadbeef일 경우 header 이므로 제거하지 않는다.
 *
 * @retval   Data
 */
int linkeListGet_FIFO(Node *head, bool data_del)
{
    Node *_local = head;
    int ret = 0;

    ret = head->data;

    if (ret == 0xdeadbeef && _local->next != NULL)
    {
        _local = _local->next;
        ret = _local->data;
    }

    if (data_del == true && _local->data != 0xdeadbeef)
    {
        head->next = _local->next;

        free(_local);
    }

    return ret;
}

다음은

 

radixSort를 구현하기 위한 함수이다.

 

앞서 말했던 데이터 길이에 따른 특별한 알고리즘이 필요하다 했는데 특별한 알고리즘이 이 함수에 해당한다.

 

/* @bref     bucket 기수의 판단 기준
 * @detail   각 자릿수의 맞게 bucket index를 구한다.
 *
 * @param    digit: 자릿수
 *           data: 판단해야할 data
 *
 * @retval   bucket index
 */
Data bucketIndex(int digit, Data data)
{
    Data ret = 0;
    Data tmp1 = 0;
    Data tmp2 = 0;

    switch (digit)
    {
        case 1:
            ret = data % 10;
            break;
        case 2:
            tmp1 = data % 10;
            tmp2 = (data - tmp1) / 10;
            ret = tmp2 % 10;
            break;
        case 3:
            tmp1 = data % 100;
            tmp2 = (data - tmp1) / 100;
            ret = tmp2;
            break;

        default:
            break;
    }

    return ret;
}

 

기수정렬을 구현한 함수이다.

/* @bref     기수 정렬
 * @detail   기수 정렬을 한다 현재 구현은 3자릿수 까지만 구현 되어 있다.
 *
 * @param    notation: 버킷의 갯수를 만드는 기준
 *           len: 정렬해야할 데이터 갯수
 *           arr[]: 정렬해야할 배열 주소
 *
 * @retval   bucket index
 */
int radixSort(Data arr[], int len,  Notation notation)
{
    TR_FUNC(TRACE);
    int array_start = 0;
    Node *_bucket[notation];
    Data *_local_arr = arr;
    //notaion이 10진수 이므로 10개만 만든다.
    for (int index = 0; index < notation; index++)
    {
        _bucket[index] = linkedListInit();
    }
    // 정렬해야할 자릿수만 큼 돌린다.
    // TODO: digit 역시 arg로 받게 만들 필요 있다.
    for (int digit = 1; digit < 4; digit++)
    {
        array_start = 0;
        // array의 데이터를 index에 맞게 삽입한다.
        for (int index = 0; index < len; index++)
        {
            Data insert_index = bucketIndex(digit, _local_arr[index]);
            linkedListInsert(_bucket[insert_index], _local_arr[index]);
        }

        // array의 데이터를 다시 꺼낸다.
        for (int bucket_index = 0; bucket_index < len; bucket_index++)
        {
            while (linkeListGet_FIFO(_bucket[bucket_index], false) != 0xdeadbeef)
                arr[array_start++] = linkeListGet_FIFO(_bucket[bucket_index], true);
        }
    }

    return 0;

}

len은 배열의 크기, Notation은 자릿수를 말하며 현재 구현은 3자릿수 까지 밖에 구현이 되어 있지 않다.

 

앞서 설명한대로 3자릿수 가 최대이므로 for문, digit 변수를 통해 3번을 돌리며 정렬을 하고 있다.

 

다음 main 함수를 통해 검증하였다.

Data array[] = {107,884,173,153,255,222,766,715,649,262};


int main(void)
{
    printf("Start Radix Sort \r\n");

    for (int i = 0; i <= (sizeof(array) / sizeof(int)) - 1; i++)
    {
        printf(" %d",array[i]);
    }

    printf("\r\n");

    int array_len = sizeof(array) / sizeof(Data);

    radixSort(array, array_len, NOTATION);

    printf("End Radix Sort\r\n");

    for (int i = 0; i <= (sizeof(array) / sizeof(int)) - 1; i++)
    {
        printf(" %d",array[i]);
    }

    printf("\r\n");
    return 0;
}

 

실행 결과

 

코드 링크: https://github.com/KJT9109/Data_Structure