자료구조 과제 #2

/*
자료구조 - 2번째 과제물.
제출 기한 : 2006. 3. 31. Friday 6:00 PM.

주어진 숫자를 radix sort algorithm (pp. 350-357) 을 이용하여 정렬하라.

예 (radix 가 10일 경우):

329        720        720        329
457        355        329        355
657        436        436        436
839  ->    457   ->   839   ->   457
436        657        355        657
720        329        457        720
355        839        657        839

Input 양식:
5                // input 개수
10329353
2340213
234091223
2342321
2341323

Output 양식:
2340213
2341323
2342321
10329353
234091223

조건:
1. 각 숫자는 최대 9자리이다.
2. Input은 C:ass2_input.txt에서 입력 받아서 C:ass2_output.txt에 출력하면 된다.
3. 제출시 파일명은 "학번_이름_반"으로 작성하세요. 여기서 반은 과제물 제출 게시판의 반입니다.(A,B,C)
  예) 200621094_홍길동_A.exe /200621094_홍길동_A.c
4. 소스 파일과 실행 파일모두 제출 하셔야 합니다.  
5. input 개수에 상관없이 작동해야 합니다. 단 integer범위를 벗어나진 않습니다.
6. c: 폴더에 실행파일이 없을 경우에도 동작해야 합니다.
7. Radix_Size에 변동 사항이 있을 경우 공지사항에 다시 올리겠습니다.
8. 공지 사항을 꼭 확인해 주세요.
*/

#include <stdlib.h>  // to use function: atoi()
#include <string.h>  // to reset buffer: memset()
#include <windows.h> // for class CTimeCouter
#include <stdio.h>  // for class CTimeCouter

#define IN_FILE "c:\\ass2_input.txt"
#define OUT_FILE "c:\\ass2_output.txt"

// global variables here
struct data{
int* list;      // input data enters here
int* temp;  // mydata.temporary data to exchange
int num_in;    // number of inputs
}mydata;

struct time{
LARGE_INTEGER   st, ed, freq ;
   double          gap ;
   BOOL            bEnable;
   char            szName[256];
   UINT            counter;
   double          fTotal_Time;
}mytime;

static void Start()
{
mytime.gap = 0.0;         // init
mytime.bEnable = FALSE;
mytime.counter = 0;
mytime.fTotal_Time = 0.0;

// system test
QueryPerformanceCounter ( &mytime.st ) ;
if ( mytime.st.QuadPart == 0 )
{
 mytime.bEnable= FALSE;
 OutputDebugString("시스템이 지원이 안됨,,, 사용할 수 없음[CTimeCounter Class]\n");
}

// start()
mytime.counter ++;
QueryPerformanceCounter ( &mytime.st ) ;
}

static void End()
{
char szMsg[64];

QueryPerformanceCounter ( &mytime.ed ) ;
QueryPerformanceFrequency ( &mytime.freq ) ;

// 소요 시간 계산
mytime.gap = ( (double) (mytime.ed.QuadPart - mytime.st.QuadPart )) / ( (double) mytime.freq.QuadPart ) ;
mytime.fTotal_Time += mytime.gap;

sprintf ( szMsg, "수행시간 %.6f초\n", mytime.gap) ;
OutputDebugString(szMsg);
}

int read(FILE * in_file)
{
char tmpr[10]="";
int i;

fscanf(in_file,"%s",&tmpr);
if (atoi(tmpr)==0) return 0; // break if input is zero
else
{
 mydata.num_in=atoi(tmpr)+1;

 mydata.list = (int*)malloc(sizeof(int)*mydata.num_in); // memory allocation as size of mydata.num_in, and link this to mydata.list
 mydata.temp = (int*)malloc(sizeof(int)*mydata.num_in); // memory allocation as size of mydata.num_in, and link this to mydata.temp

 for(i=1; i<mydata.num_in; i++)
 {
  fscanf(in_file,"%s",&tmpr);
  mydata.list[i] = atoi(tmpr);
 }
}
return 1;
}

static void sort(FILE* out_file)
{
int cnt[256], idx[256], i;

Start(); // start stopwatch

memset(cnt, 0, 1024); // initializing count
idx[0]=0; // initializing index
for(i=0; i<mydata.num_in; i++)   cnt[(mydata.list[i] >> 0) & 255]++;
for(i=1; i<256; i++)   idx[i] = idx[i-1] + cnt[i-1];
for(i=0; i<mydata.num_in; i++)   mydata.temp[idx[(mydata.list[i] >> 0) & 255]++] = mydata.list[i];

memset(cnt, 0, 1024); // initializing count
idx[0]=0; // initializing index
for(i=0; i<mydata.num_in; i++)   cnt[(mydata.temp[i] >> 8) & (255)]++;
 for(i=1; i<256; i++)   idx[i] = idx[i-1] + cnt[i-1];
for(i=0; i<mydata.num_in; i++)   mydata.list[idx[(mydata.temp[i] >> 8) & 255]++] = mydata.temp[i];

memset(cnt, 0, 1024); // initializing count
idx[0]=0; // initializing index
for(i=0; i<mydata.num_in; i++)   cnt[(mydata.list[i] >> 16) & (255)]++;
for(i=1; i<256; i++)   idx[i] = idx[i-1] + cnt[i-1];
for(i=0; i<mydata.num_in; i++)   mydata.temp[idx[(mydata.list[i] >> 16) & 255]++] = mydata.list[i];

memset(cnt, 0, 1024); // initializing count
idx[0]=0; // initializing index
for(i=0; i<mydata.num_in; i++)   cnt[(mydata.temp[i] >> 24) & (255)]++;
for(i=1; i<256; i++)   idx[i] = idx[i-1] + cnt[i-1];
for(i=0; i<mydata.num_in; i++)   mydata.list[idx[(mydata.temp[i] >> 24) & 255]++] = mydata.temp[i];

End();  // stop stopwatch

fprintf(out_file,"%.10f\n", mytime.fTotal_Time);
for(i=0; i<mydata.num_in-1;i++) fprintf(out_file,"%d ", mydata.list[i]);
fprintf(out_file,"\n");
}

void main(void)
{
   FILE *in_file, *out_file;

in_file=fopen(IN_FILE,"r");
out_file=fopen(OUT_FILE,"w");

while(read(in_file)) sort(out_file);

fclose(in_file);
fclose(out_file);

free(mydata.list);
free(mydata.temp);
}