합병정렬, 분할 정렬 알고리즘에 문제가 있는지 봐주세요.
해뜰참
질문 제목 : 합병정렬, 분할 정렬 알고리즘에 문제가 있는지 봐주세요.
질문 요약 :정렬들 소스 문제 있는지 봐주세요
질문 내용 :
제가 수업시간에 합병정렬하고분할정렬 아고리즘에 대해서 배웠는데요. 거기서 실습을 하다가 문제로 나온 소스들을 완성하지 못했습니다. 어디에 문제가 있는지 모르겠는데요. 어떤 부분을 수정해야 하는 건가요? 고수님들 가르쳐 주십시오.
합병정렬 임의의 열을 입력 받아 출력하고 그 과정또한 출력시킬것(미완성)
#include stdio.h
#include stdlib.h
#define MAX_SIZE 10
int sorted[MAX_SIZE]; // 추가 공간이 필요
/* i는 정렬된 왼쪽리스트에 대한 인덱스
j는 정렬된 오른쪽리스트에 대한 인덱스
k는 정렬될 리스트에 대한 인덱스 */
void merge(int list[], int left, int mid, int right)
{
int sorted[MAX_SIZE];
int i, j, k, l;
i=left;
j=mid+1;
k=left;
/* 분할 정렬된 list의 합병 */
while(i=mid && j=right)
{
if(list[i]=list[j])
sorted[k++] = list[i++];
else
sorted[k++] = list[j++];
}
if(imid)/* 남아 있는 레코드의 일괄 복사 */
for(l=j; l=right; l++)
sorted[k++] = list[l];
else/* 남아 있는 레코드의 일괄 복사 */
for(l=i; l=mid; l++)
sorted[k++] = list[l];
/* 배열 sorted[]의 리스트를 배열 list[]로 재복사 */
for(l=left; l=right; l++)
list[l] = sorted[l];
}
//
void merge_sort(int list[], int left, int right)
{
int mid;
if(leftright)
{
mid = (left+right)/2; /* 리스트의 균등 분할 */
merge_sort(list, left, mid); /* 부분 리스트 정렬 */
merge_sort(list, mid+1, right); /* 부분 리스트 정렬 */
merge(list, left, mid, right); /* 합병 */
}
}
void main()
{
int i;
int list[MAX_SIZE];
int n=MAX_SIZE;
for(
scanf(%d,&n);
for(i=0;in;i++)
printf(%d,list[i]);
printf(\n);
merge_sort(list,0,n-1);
for(i=0; in; i++)
printf(%d, list[i]);
}
분할정렬시간을 측정(미완성)
#include stdio.h
#include stdlib.h
#include time.h
#define MAX_SIZE 10
int list[MAX_SIZE]; /* 최대 배열 크기 */
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )//x와 y를 교환
int partition(int list[], int left, int right)
{
int pivot, temp;
int low,high;
low = left;
high = right+1;
pivot = list[left];
do {
do
low++;
while(low=right &&list[low]pivot);
do
high--;
while(high=left && list[high]pivot);
if(lowhigh) SWAP(list[low], list[high], temp);
} while(lowhigh);
SWAP(list[left], list[high], temp);
return high;
}
void partition_sort(int list[],int left,int right)
{
if(leftright)
{
int q=partition(list,left,right);
partition_sort(list,left,right);
partition_sort(list,left,q-1);
}
}
void main()
{
int i;
double start,finish;
start=clock();
for(i=0; iMAX_SIZE; i++)
{ /* 난수 생성 및 출력 */
list[i] = rand()%MAX_SIZE;/*난수 발생 범위 0~MAX_SIZE*/
}
partition_sort(list,0,MAX_SIZE);
finish=clock();
printf(time : %.3f\n,(finish-start)/CLK_TCK);
for(i=0; iMAX_SIZE; i++)
printf(%d\n, list[i]);
}