수다닷컴

질문 제목 :
합병 정렬 소스 문제점좀 알려주세요..(첨부)질문 내용 :
합병정렬을 코딩 하는 중인데요.
동적할당으로 2가지 방법으로 하는데 한가지 방법은 mergesort에서 동적 할당을 하는 방법이고,
두번째 방법(메모리 절약)은 merge하는 부분에서 동적 할당을 하는데요 두 가지 정렬의 시간차이가 너무 많이 나네요..
두번째 방법이 훨씬 느리네요;; 차이점을 좀 알려주세요 ( 십만개 이상 입력을 하였을때)

int main()
{
int datanum;
int *unsorteddata;

printf(정렬 할 숫자의 갯수를 입력 하세요 : );
scanf(%d,&datanum);
srand((unsigned) time(null));
unsorteddata = (int *)malloc(sizeof(int)*(datanum+1));
for(int i = 0; idatanum; i++)
{
unsorteddata[i] = rand()%100;
}
printf(\n);

//merge_sort(unsorteddata,datanum);
merge_inplace_sort(unsorteddata,0,datanum-1);

// 정렬 후 출력 부분
for(int i = 0; idatanum; i++)
{
if(i % 10 == 0) printf(\n);
printf(%d , unsorteddata[i]);
}
printf(\n);

free(unsorteddata); // 메모리 해제
system(pause);
return 1;
}
1번 코드
void merge_sort(int arr[], int n)
{
int h = n/2;
int m = n-h;
int *left,*right;
int i,j;

if(n1)
{
left = (int *)malloc((h-1)*sizeof(int));
right = (int *)malloc((m-1)*sizeof(int));
for(i = 0; ih; i++) left[i] = arr[i];
for(i = 0; im; i++) right[i] = arr[h+i];

merge_sort(left,h);
merge_sort(right,m);
merge(left,right,h,m,arr);
}

}
void merge(int* left,int* right,int h, int m, int arr[])
{
int i,j,k,t;
i = j =k = 0;
while( ih && jm)
{
if(*(left+i) *(right+j)) arr[k]=left[i++];
else arr[k] = right[j++];
k++;
}

if(ih-1)
{
for( t=k; th+m;t++)
arr[t] = right[j++];
}
else
{
for(t = k; th+m; t++)
arr[t] = left[i++];
}
}

2번방법

void merge_inplace_sort(int unsorteddata[], int low, int high)
{
int mid;
if(highlow)
{
mid = (low + high)/2;
merge_inplace_sort(unsorteddata,low, mid);
merge_inplace_sort(unsorteddata,mid+1, high);
merge_inplace(unsorteddata,low, mid, high);
}
}
void merge_inplace(int unsorteddata[], int low, int mid, int high)
{
int i, j, k,t;

i = low;
j = mid +1;
k = low;
int *temparr;
temparr = (int*)malloc(sizeof(int)*(high+1));

while(i=mid && j=high)
{

if(unsorteddata[i] unsorteddata[j]) temparr[k++] = unsorteddata[i++];

elsetemparr[k++] = unsorteddata[j++];
}
if(imid) for(t=j;t=high;t++) temparr[k++]=unsorteddata[t];
else for(t=i;t=mid;t++) temparr[k++]=unsorteddata[t];
for(t = low; t=high; t++) unsorteddata[t] = temparr[t];

free(temparr);
}

보기에 불편하실수 있을거 같네요.. 차이점 좀 알려주세요~!

신청하기