[완료]C Merge Sort 예제 어디가 문제일까요?

ahsan의 이미지

안녕하세요
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

singularof의 이미지

메모리 할당문제인거 같은데..

winner의 이미지

Bug를 어떻게 찾을까 고민하는게 programming 공부하는데 도움이 가장 많이 되었던 것 같습니다.
열심히 하세요.

sandrain의 이미지

mergeSort 함수를 다음과 같이 바꿨어요 ..

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)
   {
#if 0
      // 나누어진 배열 길이만큼 메모리 할당
      partU = (int *)malloc(sizeof(int) * h);
      partV = (int *)malloc(sizeof(int) * m);
 
      // 할당된 메모리에 배열을 복사
      arrayCopy(partU, data, h);
      arrayCopy(partV, data + h - 1, m);
#endif
 
      partU = malloc(sizeof(int) * array_length);
      partV = & partU[h];
 
      arrayCopy(partU, data, array_length);
 
      // 나누어진 배열을 각각 합병정렬
      mergeSort(partU, h);
      mergeSort(partV, m);
 
      partU_index = partV_index = data_index = 0;
 
      for ( ; data_index < array_length; ) {
	      if (partU_index == h)
		      data[data_index++] = partV[partV_index++];
		else if (partV_index == m)
			data[data_index++] = partU[partU_index++];
		else
			data[data_index++] = partU[partU_index] < partV[partV_index] ? partU[partU_index++] : partV[partV_index++];
 
      }
 
#if 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);
#endif
 
      free(partU);
      //free(partV);
   }
}

먼가 인덱스를 잘못계산하는 부분이 있나봅니다.

beautifool world~!

beautifool world~!

ahsan의 이미지

원래의 코드가 왜 잘못되었는지는 모르겠지만
메모리를 다루는 부분이라서 그런지 데이타를 h, m으로 나누지 않고,
partV = & partU[h]; 으로 처리하는 부분이 인상적입니다.

코드가 휠씬 짧아지고 오히려 이해하기 더 쉽군요.
훌륭한 가르침에 감사드립니다.

ahsan의 이미지

댓글의 댓글이 그냥 댓글로...

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.