수다닷컴

제가 자료구조론을 수강하고있는대요 Radix sort에대해 알아오라고했더라고요. 교수님이 그리고 프로그램도 만들어야하는데.

기수정렬이라하겠음. 에대해 알아보니 자리수대로 비교하여 일의자리수 십의자리수 이렇게 차례대로비교하는 방법이라고

하더군요. 제가 기수정렬이대한 소스를 가져와서 분석하는데 비교될 숫자값이 어디서 입력되고 어디서 출력되는지는 알겠지만

radix_sort 부분에서 어디서 숫자들의 자릿수가 비교되는지 어떻게 순서가 정해지는지 잘모르겠네요. 프로그래밍 고수님들께

답변좀 부탁드리겠습니다. 저혼자서 기수정렬하는 프로그램을 짤수는있겠지만 먼저 이것부터 이해하고나서 만들어야겠네요

쩝.

#include stdio.h
#include stdlib.h
#define SIZE 10
#define BUCKETS 10 // 10진수
#define DIGITS 4 // 4자리 수까지 가능
#define MAX_QUEUE_SIZE 100
typedef int element;
typedef struct{
element queue[MAX_QUEUE_SIZE];
int front, rear;
}QueueType;
void error(char *message)
{
fprintf(stderr, %s\n, message);
exit(1);
}
// 초기화 함수
void init(QueueType *q)
{
q-front = q-rear = 0;
}
// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
return (q-front == q-rear);
}
// 포화 상태 검출 함수
int is_full(QueueType *q)
{
return ((q-rear+1)%MAX_QUEUE_SIZE == q-front);
}
// 삽입 함수
void enqueue(QueueType *q, element item)
{
if(is_full(q))
error(큐가 포화상태입니다);
q-rear = (q-rear+1) % MAX_QUEUE_SIZE;
q-queue[q-rear] = item;
}
// 삭제 함수
element dequeue(QueueType *q)
{
if(is_empty(q))
error(큐가 공백상태입니다);
q-front = (q-front+1) % MAX_QUEUE_SIZE;
return q-queue[q-front];
}
void radix_sort(int list[], int n)
{
int i, b, d, factor=1;
QueueType queues[BUCKETS];
for(b=0; bn; b++)
init(&queues[b]); // 모든 큐 초기화
for(d=0; dDIGITS; d++)
{
for(i=0; in; i++) // 데이터들을 자리수에 따라 큐에 삽입
enqueue(&queues[(list[i]/factor)%10], list[i]);
for(b = i = 0; bBUCKETS; b++) // 버킷에서 꺼내 list로 합침
while(!is_empty(&queues[b]))
list[i++] = dequeue(&queues[b]);
factor *= 10; // 다음 자리수로 간다
}
}
// 리스트 출력 함수
void print_list(int list[])
{
int i;
for(i=0; iSIZE; i++)
printf(%d번째 값 : %d\n, i+1, list[i]);
}
///////////////////////////////////////////////////////////////////////////////////
// 메인 함수
void main()
{
int i, num=0;
int list[SIZE];
for(i=0; iSIZE; i++)
{
printf(%d번 값 : , i+1);
scanf(%d, &list[i]);
num++;
}
printf(정렬 전\n);
print_list(list);
radix_sort(list, num);
printf(정렬 후\n);
print_list(list);
}

신청하기