기수정렬
기수정렬은 다른 정렬들과는 달리 유일하게 비교연산이 없습니다.
정렬 알고리즘들의 성능 한계인 O(nlog2N)을 유일하게 뛰어 넘을 수 있는 알고리즘입니다.
하지만 단점으로는 적용 범위에 한계가 있습니다.
1 5 4 2 3 6 이런 것은 정렬 가능 하지만 11 23 333 2 4 이런 것들은 정렬 불가합니다.
즉 자릿 수가 다를 경우 정렬 불가능 하다는 겁니다.
하지만 이를 위해 여러 알고리즘을 모색하였습니다.
기본적인 한자리 숫자 기수 정렬의 원리를 알아보겠습니다. 우선 버킷에 정렬 숫자들을 담습니다. 버킷은 양동이입니다.
즉 1 4 2 3 이라는 숫자가 있으면 1은 버킷 1에 4는 버킷 4에 2는 버킷 2에 3은 버킷 3에 들어갑니다.
이것을 버킷 순서대로 꺼냅니다.!! 그럼 1 2 3 4 라고 정렬 돼서 나오겠죠 그림으로 보시죠
이런 식으로 되죠.
기수정렬은 이렇듯이 십진수라면 버킷의 개수는 10개입니다.
기수정렬의 방식중 LSD방식과 MSD방식이 있습니다.
LSD방식은 덜 중요 자릿수 부터 정렬해나갑니다. 첫 자리수 부터 정렬 대상입니다.
MSD방식은 가장 큰 자릿수를 대상으로 정렬해나갑니다.
우선 LSD 방식부터 보시죠.
134 224 232 122라는 정렬 대상이 있습니다. 5진수이기 때문에 버킷은 5개만 있으면 되겠죠. ㅎㅎ
우선 첫 째 자리 숫자 4 4 2 2 가 있습니다. 4 4 가 있는 숫자는 버킷 4에 차례대로 넣으시고 2 2 가 있는 숫자는 버킷 2에 넣습니다.
그럼 버킷 2에는 122 / 232 순서로 들어가 있고 버킷 4에는 224/134 순서로 있겠죠. 버킷2에서 차례때로 꺼냅니다. 그담 버킷4에서 차례대로 꺼냅니다.
그럼 232 122 134 224 순서로 돼있을 겁니다. 그 다음 두 번째 자리수 3 2 3 2가 있죠 마찬가지 방법으로 버킷에 넣습니다. 그림으로 보시죠
1단계
2단계
3단계
이렇게 총 3단계로 버킷에 넣고 빼는 과정으로 정렬이 이루어집니다.
MSD방식은 반대로 큰 자리 숫자로 먼저 버킷에 넣고 빼는 과정으로 이루어집니다. 하지만 장점으로는 중간에 정렬이 끝날 수 있지만 중간에 데이터를 점검해야합니다.
구현의 난이도가 상당합니다. 심지어 빅오의 차이도 없습니다. 성능은 동일합니다.
따라서 LSD방식으로 접근해보도록 하겠습니다.
2자리 숫자와 3자리 숫자를 정렬 할 때는 2자리 숫자의 큰 자릿수는 0으로 계산합니다.
여러분들 혹시 숫자들의 자릿수의 숫자를 추출하는 방법에 대해 아시나요 ?? 아시는 분도 있고 모르시는 분들도 있을겁니다.
32라는 숫자에서 2라는 숫자와 3이라는 숫자를 뽑기위해서는 어떻게 접근할까요 ??
32에서 2라는 숫자는 10으로 나눈 나머지가 되지않나요 ??
3은 32에서 10으로 나누고 그 값을 또 10으로 나눠보면 나머지가 3이지 않나요 ?? 이렇게 접근하면됩니다.
즉
첫 번째 자리 추출 method: 숫자%10
두 번째 자리 추출 method: 숫자/10%10
세 번째 자리 추출 method: 숫자/100%10
방식으로 접근 하면 됩니다.
그다음 버킷은 큐를 이용해야겠죠 선입 선출 구조이기 때문에 먼저 들어온게 차례대로 먼저 나가야합니다. 마치 영화표 줄처럼 말이죠 ㅎㅎ
큐는 연결리스트 기반으로 짠 큐를 사용하겠습니다.
우선 큐의 소스파일 을 보이도록 할게요. 주석 처리를 해놔서 이해하시기 편하실겁니다.
<ListBaseQueue.c> 메인파일
#include <stdio.h>
#include <stdlib.h>
#include "ListBaseQueue.h"
//연결 기반 큐 이정찬
void QueueInit(Queue * pq) //큐초기화
{
pq->front = NULL;
pq->rear = NULL;
}
int QIsEmpty(Queue * pq)
{
if(pq->front == NULL) //만약에 큐의 front가 null이면 비어있다.!!
return TRUE;
else
return FALSE;
}
void Enqueue(Queue * pq, Data data)//삽입 rear이용
{
Node * newNode = (Node*)malloc(sizeof(Node)); //새노드 생성
newNode->next = NULL; //next는널로 초기화
newNode->data = data;//데이터 부분에 데이터 삽입 => 데이터/null 블록 생성
if(QIsEmpty(pq)) //큐가 비어있따면 새로운 노드를 front와 rear에 연결
{
pq->front = newNode;
pq->rear = newNode;
}
else //비어있지 않으면
{
pq->rear->next = newNode; //rear가 가리크는 노드의 next가 다음 새 노드를 가리키고
pq->rear = newNode; // rear는 새노드를 다시 가리키게 한다. 즉 f->node/next->new node(rear이 가리킴)
}
}
Data Dequeue(Queue * pq)//삭제 front이용
{
Node * delNode;
Data retData;
if(QIsEmpty(pq)) //비어있으면 에러
{
printf("Queue Memory Error!");
exit(-1);
}
delNode = pq->front; //front가 가리키는 노드를 delNode에 대입
retData = delNode->data; //반환 데이터
pq->front = pq->front->next; //front는 한칸 앞으로 이동
free(delNode);//메모리 해체
return retData;
}
Data QPeek(Queue * pq)
{
if(QIsEmpty(pq))
{
printf("Queue Memory Error!");
exit(-1);
}
return pq->front->data;
}
<ListBaseQueue.h> 헤더파일
#ifndef __LB_QUEUE_H__
#define __LB_QUEUE_H__
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node
{
Data data;
struct _node * next;
} Node; //데이터+링크
typedef struct _lQueue
{
Node * front;
Node * rear;
} LQueue; //front와 rear(삭제 삽입시 사용)
typedef LQueue Queue;
void QueueInit(Queue * pq);//큐 초기화
int QIsEmpty(Queue * pq);//큐 비었는지 확인
void Enqueue(Queue * pq, Data data); //삽입
Data Dequeue(Queue * pq); //삭제
Data QPeek(Queue * pq); //추출
#endif
그리고 기수 정렬 코드를 선보이도록 할게요. 이 코드는 위에서 보인 리스트기반 큐를 선언합니다.
#include <stdio.h>
#include "ListBaseQueue.h"
#define BUCKET_NUM 10
//기수 정렬 이정찬 연결 큐 기반
void RadixSort(int arr[], int num, int maxLen) // maxLen은 가장 긴 데이터의 길이
{
Queue buckets[BUCKET_NUM];
int bi;
int pos;
int di;
int divfac = 1;
int radix;
// 총 10개의 버킷 초기화
for(bi=0; bi<BUCKET_NUM; bi++)
QueueInit(&buckets[bi]);
// 가장 긴 데이터의 길이만큼 반복
for(pos=0; pos<maxLen; pos++)
{
// 정렬 대상의 수만큼 반복
for(di=0; di<num; di++)
{
// N번째 자리의 숫자 추출
radix = (arr[di] / divfac) % 10;
// 추출한 숫자를 근거로 데이터 버킷에 저장
Enqueue(&buckets[radix], arr[di]);
}
// 버킷 수만큼 반복
for(bi=0, di=0; bi<BUCKET_NUM; bi++)
{
// 버킷에 저장된 것 순서대로 다 꺼내서 다시 arr에 저장
while(!QIsEmpty(&buckets[bi]))
arr[di++] = Dequeue(&buckets[bi]);
}
// N번째 자리의 숫자 추출을 위한 피제수의 증가
divfac *= 10;
}
}
버킷은 큐입니다. 총 10개짜리 버킷 큐를 선언합니다.
우선 첫 for문을 이용하여 총 10개의 버킷을 초기화합니다. 이때 버킷은 큐이기 때문에 큐를 초기화 하면됩니다. QueueInit함수를 이용합니다.
RadixSort 함수의 매개변수로 마지막 인자에서 최대 길이만큼 for문을 돌려줍니다. 그래야 자릿수가 적은 숫자들도 비교가 가능합니다 0으로써
그 다음 정렬할 대상 수만큼 반복합니다. 이때 이제 첫 자리 숫자와 등등을 뽑아줍니다. 위에서 말한 공식있죠 그것을 이용하시면 됩니다.
추출한 자리 값을 radix에 넣고 버킷의 인덱스에 넣은 후 Enqueue함수를 통해 큐를 삽입합니다. 정렬 대상 수만큼 반복했다면 즉 버킷에 삽입이 끝났다면
이제 버킷에서 삭제를 하여 추출합니다. 버킷 수만 큼 반복을 하여 비어있지 않을 때 까지 arr배열에 버킷에 있는 숫자를 삭제하여 집어넣습니다.
그다음 첫 , 두번 째 세번째 자리 숫자를 추출하기 위한 숫자를 10배 증가시킵니다.
이렇게 가장 긴 숫자만큼 반복합니다. 그러면 정렬 완료입니다.
성능은 빅오 O(n)입니다.
