수다닷컴

//in file merge.c
?xml:namespace prefix = o ns = urn:schemas-microsoft-com:office:office /
#include mergesort.h
/* Merge a[] of size m and b[] of size n into c[]. */

void merge(int a[], int b[], int c[], int m, int n)
{
int i = 0, j = 0, k = 0;

while (i m && j n)
if (a[i] b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
while (i m) /* pick up any remainder */
c[k++] = a[i++];
while (j n)
c[k++] = b[j++];
}

//
/* Mergesort: Use merge() to sort an array of size n. */

#include stdio.h
#include stdlib.h

void merge(int *, int *, int *, int, int);

void mergesort(int key[], int n)
{
int j, k, m, *w;

for (m = 1; m n; m *= 2)
;
if (m != n) {
printf(ERROR: Size of the array is not a power of 2 - bye!\n);
exit(1);
}
w = calloc(n, sizeof(int)); /* allocate workspace */
for (k = 1; k n; k *= 2) {
for (j = 0; j n - k; j += 2 * k)
merge(key + j, key + j + k, w + j, k, k); /* merge into w */
for (j = 0; j n; ++j)
key[j] = w[j]; /* write w back into key */
}
free(w); /* free the workspace */
}
mergesort() 함수를 2의 거듭제곱 크기에 대해서만이 아니라 임의의 크기의 배열에 대해서도 사용할 수 있도록 수정하여라. 이때 임의의 양수는 2의 거듭제곱의 합으로 표현할 수 있음을 상기하여라. 예를 들면 다음과 같다.
27 = 16 + 8 + 2 + 1

배열을 2의 거듭제곱 크기의 부분 배열의 집합으로 생각해 보자. 각 부분 배열을 정렬하고, 최종적으로 정렬된 배열을 만들기 위해 merge()를 사용하여라.이것좀 풀어주세요..

신청하기