수다닷컴

질문 제목 : radix sort 시간단축방법좀..

자료구조 과제로 radix 소트를 이용한 프로그램을 만드는건데요 한 레코드에는 세개의 필드가 들어가고 필드의 우선순위는 코드에서보면 abc 순입니다. 과제 내용도 참 복잡한데.. 예를들면
5 //레코드의수
1 900 30 40 300 60 35 10 500 20 300 1004 35 10 405
// 1번레코드a 1번레코드b 1번레코드c 2번레코드a 2번레코드b 2번레코드c ... 이런식으로 입력되고
1 900 30 20 300 1004 35 10 405 35 10 500 40 300 60 // 이런식으로 출력됩니다.
정렬이 되긴 되는데 시간이 너무오래걸려서 점수를 못받게생겼네요..

질문 내용 :
코드입니다
#includestdio.h
#includememory.h
#includestdlib.h
typedef struct in_type{
unsigned int a;
unsigned int b;
unsigned int c;
struct in_type *next;
}in_type;
in_type head[4096], tail[4096];
in_type buffer[124];
void radix_sort(in_type *buffer, int num)
{
int i,j,k;
in_type bucket[4097];
in_type *tmp;
in_type *temp;
in_type *free;
int num_bucket[4097]={0};
memset(bucket,0,sizeof(in_type)*4097);
for(i=0; inum ;i++)
{
tmp=(in_type*)malloc(sizeof(in_type));
memcpy(tmp,buffer+i,sizeof(in_type));
if(!num_bucket[tmp-c])
{
head[tmp-c].next=tmp;
bucket[tmp-c]=head[tmp-c];
}
else
{
temp=&head[tmp-c];
while(1)
{
if( temp-a == temp - next- a && temp-b == temp- next- b && temp-c==temp-next-c )
break;

temp=temp-next;

}
temp-next=tmp;
}
(num_bucket[tmp-c])++;
}
for(i=0,j=0; i4096 ; i++)
{
if(num_bucket[i])
{
k=0;
while(1)
{
memcpy(buffer+j,bucket[i].next,sizeof(in_type));
buffer[j].next=&buffer[j];
j++;

free=bucket[i].next-next;
bucket[i].next=bucket[i].next-next;
num_bucket[i]--;
if(!num_bucket[i])
break;
}
}
}

memset(bucket,0,sizeof(in_type)*4097);
memset(num_bucket,0,4097*sizeof(int));
//버켓 //버켓 넘버 초기화
for(i=0; inum ;i++)
{
tmp=(in_type*)malloc(sizeof(in_type));
memcpy(tmp,buffer+i,sizeof(in_type));
if(!num_bucket[tmp-b])
{
head[tmp-b].next=tmp;
bucket[tmp-b]=head[tmp-b];
}
else
{
temp=&head[tmp-b];
while(1)
{
if(temp-a==temp-next-a && temp-b==temp-next-b&& temp-c==temp-next-c)
break;
temp=temp-next;

}
temp-next=tmp;
}
(num_bucket[tmp-b])++;
}

for(i=0,j=0; i4096 ; i++)
{
if(num_bucket[i])
{
k=0;
while(1)
{

memcpy(buffer+j,bucket[i].next,sizeof(in_type));
buffer[j].next=&buffer[j];
j++;

free=bucket[i].next-next;
bucket[i].next=bucket[i].next-next;

num_bucket[i]--;
if(!num_bucket[i])
break;
}
}
}
//버켓 //버켓 넘버 초기화
memset(bucket,0,sizeof(in_type)*4097);
memset(num_bucket,0,4097*sizeof(int));

for(i=0; inum ;i++)
{
tmp=(in_type*)malloc(sizeof(in_type));
memcpy(tmp,buffer+i,sizeof(in_type));
if(!num_bucket[tmp-a])
{
head[tmp-a].next=tmp;
bucket[tmp-a]=head[tmp-a];
}
else
{
temp=&head[tmp-a];
while(1)
{
if(temp-a==temp-next-a && temp-b==temp-next-b&& temp-c==temp-next-c)
break;
temp=temp-next;

}
temp-next=tmp;
}
(num_bucket[tmp-a])++;
}
for(i=0,j=0; i4096 ; i++)
{
if(num_bucket[i])
{
k=0;
while(1)
{
memcpy(buffer+j,bucket[i].next,sizeof(in_type));
buffer[j].next=&buffer[j];
j++;

free=bucket[i].next-next;
bucket[i].next=bucket[i].next-next;

p;num_bucket[i]--;
if(!num_bucket[i])
break;
}
}
}
}
int main(int argc, char *argv[])
{
int num, i;
scanf(%d, &num);

while(num != -1)
{
for(i = 0; i num; i++)
{
scanf(%d, &buffer[i].a);
scanf(%d, &buffer[i].b);
scanf(%d, &buffer[i].c);
buffer[i].next=&buffer[i];

}
radix_sort(buffer, num);

for(i = 0; i num; i++)
{
printf(%d , buffer[i].a);
printf(%d , buffer[i].b);
printf(%d , buffer[i].c);
}
printf(\n);
scanf(%d, &num);
}
return 0;
}

제가 코딩실력이 모자라서 코드가 좀 엉망이네요..
이상태에서 시간 조금이라도 단축하려면 어떻게 해야하나요 ㅠ

신청하기