[완료]C Merge Sort 예제 어디가 문제일까요?
안녕하세요
C programming bile이라는 책의 예제중에 MergeSort 코드입니다.
컴파일은 되는데 실행하면 에러가 납니다. 이유를 모르겠습니다.
잘못된 부분 지적해 주시길 부탁드립니다.
#include <stdio.h> #include <stdlib.h> #define DATA_MAX 100 void mergeSort(int data[], int array_length); void arrayCopy(int *dest, int const *origin, int n); int main() { int data[DATA_MAX]; int i; // 임의의 수를 생성하여 배열에 저장 printf("Random Number Generator."); for(i=0; i<DATA_MAX; i++) { if( i % 10 == 0) putchar('\n'); data[i] = rand() % 1000; printf("%4d, ", data[i]); } mergeSort(data, DATA_MAX); // 정렬한 후 배열을 순서대로 출력 printf("\nSorting by merge Sort."); for(i=0; i<DATA_MAX; i++) { if( i % 10 == 0) putchar('\n'); printf("%4d, ", data[i]); } putchar('\n'); return 0; } void mergeSort(int data[], int array_length) { // 변수 선언과 동시에 배열의 길이를 반으로 나눔 int h = array_length / 2; int m = array_length - h; int partU_index, partV_index, data_index; int *partU, *partV; // 새로 생성될 배열 포인터 // 배열의 길이가 1 이면 정렬할 것이 없음 if(array_length > 1) { // 나누어진 배열 길이만큼 메모리 할당 partU = (int *)malloc(sizeof(int) * h); partV = (int *)malloc(sizeof(int) * m); // 할당된 메모리에 배열을 복사 arrayCopy(partU, data, h); arrayCopy(partV, data + h - 1, m); // 나누어진 배열을 각각 합병정렬 mergeSort(partU, h); mergeSort(partV, m); partU_index = partV_index = data_index = 0; // 정렬된 두 배열을 처음부터 읽어 가면서 합침. // 어느 한쪽이 비게 되면 루프 종료 while(partU_index < h && partV_index < m) { if(partU[partU_index] < partV[partV_index]) data[data_index] = partU[partU_index++]; else data[data_index] = partV[partV_index++]; data_index++; } // 남아 있는 배열을 복사해서 합침 if(partU_index == h) arrayCopy(data + data_index, partV + partV_index, m - partV_index); else arrayCopy(data + data_index, partU + partU_index, m - partU_index); free(partU); free(partV); } } void arrayCopy(int *dest, const int *origin, int n) { int i = 0; for(; i < n; i++) dest[i] = origin[i]; }
=====실행에러메시지=====
Random Number Generator.
383, 886, 777, 915, 793, 335, 386, 492, 649, 421,
362, 27, 690, 59, 763, 926, 540, 426, 172, 736,
211, 368, 567, 429, 782, 530, 862, 123, 67, 135,
929, 802, 22, 58, 69, 167, 393, 456, 11, 42,
229, 373, 421, 919, 784, 537, 198, 324, 315, 370,
413, 526, 91, 980, 956, 873, 862, 170, 996, 281,
305, 925, 84, 327, 336, 505, 846, 729, 313, 857,
124, 895, 582, 545, 814, 367, 434, 364, 43, 750,
87, 808, 276, 178, 788, 584, 403, 651, 754, 399,
*** glibc detected *** ./ex: munmap_chunk(): invalid pointer: 0x09d7f348 ***
======= Backtrace: =========
/lib/libc.so.6(cfree+0x1bb)[0x27a19b]
./ex[0x80487ad]
./ex[0x80486b0]
./ex[0x804869e]
./ex[0x804869e]
./ex[0x804869e]
./ex[0x804869e]
./ex[0x8048556]
/lib/libc.so.6(__libc_start_main+0xdc)[0x223dec]
./ex[0x8048391]
======= Memory map: ========
001eb000-00205000 r-xp 00000000 08:02 944706 /lib/ld-2.5.so
00205000-00206000 r-xp 00019000 08:02 944706 /lib/ld-2.5.so
00206000-00207000 rwxp 0001a000 08:02 944706 /lib/ld-2.5.so
0020e000-0034b000 r-xp 00000000 08:02 944721 /lib/libc-2.5.so
0034b000-0034d000 r-xp 0013c000 08:02 944721 /lib/libc-2.5.so
0034d000-0034e000 rwxp 0013e000 08:02 944721 /lib/libc-2.5.so
0034e000-00351000 rwxp 0034e000 00:00 0
0047f000-0048a000 r-xp 00000000 08:02 944757 /lib/libgcc_s-4.1.2-20080102.so.1
0048a000-0048b000 rwxp 0000a000 08:02 944757 /lib/libgcc_s-4.1.2-20080102.so.1
0049f000-004a0000 r-xp 0049f000 00:00 0 [vdso]
08048000-08049000 r-xp 00000000 08:05 3277606 /var/home/danuplus/c/algorithm/sort2/ex
08049000-0804a000 rw-p 00000000 08:05 3277606 /var/home/danuplus/c/algorithm/sort2/ex
09d7f000-09da0000 rw-p 09d7f000 00:00 0
b7fbf000-b7fc1000 rw-p b7fbf000 00:00 0
b7fcb000-b7fcc000 rw-p b7fcb000 00:00 0
bffe3000-bfff8000 rw-p bffe3000 00:00 0 [stack]
932, 60, 676, 368, 739, 12, 226, 586, 94, 539, Aborted
아
메모리 할당문제인거 같은데..
한 두군데 보이는군요.
Bug를 어떻게 찾을까 고민하는게 programming 공부하는데 도움이 가장 많이 되었던 것 같습니다.
열심히 하세요.
..이렇게
mergeSort 함수를 다음과 같이 바꿨어요 ..
먼가 인덱스를 잘못계산하는 부분이 있나봅니다.
beautifool world~!
beautifool world~!
답변 감사드립니다
원래의 코드가 왜 잘못되었는지는 모르겠지만
메모리를 다루는 부분이라서 그런지 데이타를 h, m으로 나누지 않고,
partV = & partU[h]; 으로 처리하는 부분이 인상적입니다.
코드가 휠씬 짧아지고 오히려 이해하기 더 쉽군요.
훌륭한 가르침에 감사드립니다.
지울수 없음
댓글의 댓글이 그냥 댓글로...
댓글 달기