448,563 Members | 1,307 Online Need help? Post your question and get tips & solutions from a community of 448,563 IT Pros & Developers. It's quick & easy.

# Seg faults in merge and quick sort

 P: n/a These sorts work fine on 100000 ints but if I go much higher they will both segmentation fault **************************MERGESORT*************** ****** mergesort(int *a, int size) //a is pointer to the array, size is # of elements { int b[(size/2)]; int c[(size-(size/2))]; int *bp; int *cp; int x; int y; bp = b; cp = c; if(size 1) { for(x = 0; x < (size/2); x++) { b[x] = *(a + x); } for(y = 0; y < (size - (size/2)); y++) { c[y] = *(a + x); x++; } mergesort(bp, (size/2)); mergesort(cp, (size - (size/2))); merge(a, bp, cp, size); } } merge(int *a, int *b, int *c, int size) { int i = 0, j = 0, k = 0; while(i < (size/2) && j < (size - (size/2))) { if(*(b + i) < *(c + j)) { *(a + k) = *(b + i); i++; } else { *(a + k) = *(c + j); j++; } k++; } if(i == (size/2)) { while(j < (size - (size/2))) { *(a + k) = *(c + j); k++; j++; } } else { while(i < (size/2)) { *(a + k) = *(b + i); k++; i++; } } } ******************************************* ********************QUICKSORT***************** quicksort(int *a, int size) { q_sort(a, 0, size - 1); } q_sort(int *a, int l, int r) { int s; //printf("\n%d - size", (r - l)); if(l < r) { s = partition(a, l, r); q_sort (a, l, s - 1); q_sort(a, s + 1, r); } } int partition(int *a, int l, int r) { int i, j, p; p = *(a + l); i = l; j = r + 1; while(1 < 2) { do ++i; while(*(a + i) <= p && i <= r); do --j; while (*(a + j) p && j >=l); if(i >= j) break; swap(a, i, j); } swap(a, l, j); return j; } swap(int *a, int b, int c) { int temp = *(a + b); *(a + b) = *(a + c); *(a + c) = temp; } ********************** here is the code I've been using to test with ****************** main() { int size = 100000, a[size], *ap, x; ap = a; time_t t0, t1; clock_t c0, c1; for(x = 0; x < size; x++) //set array in reverse order { a[x] = random()%size; } t0 = time(NULL); c0 = clock(); printf("\nMergesorting\n"); mergesort(ap, size); t1 = time(NULL); c1 = clock(); /*for(x = 0; x < size; x++) //print contents of array { printf("\n%d", a[x]); }*/ printf("\nMergesort(%d items)\nTime Difference: %f\tClock Cycle Difference: %f\n",size, (float) (t1-t0),(float) (c1-c0)); size = 100000; for(x = 0; x < size; x++) //set array in random order { a[x] = random()%size; } t0 = time(NULL); c0 = clock(); quicksort(ap, size); t1 = time(NULL); c1 = clock(); /*for(x = 0; x < size; x++) //print contents of array { printf("\n -%d", a[x]); }*/ printf("\nQuicksort(%d items)\nTime Difference: %f\tClock Cycle Difference: %f\n",size, (float) (t1-t0),(float) (c1-c0)); } **************************** Any idea why I'm getting seg errors? Oct 20 '06 #1
13 Replies

 P: n/a

 P: n/a Thanks for all the help...one more question Trying to figure out a better way to time the sorting, but there is no gethrtime on this computer(running MAC OS) Any suggestions?(is running sorts for small numbers several times and taking the average the only way, or is there something else I may be able to use?) Oct 21 '06 #4

 P: n/a ra*******@yahoo.com wrote: > Thanks for all the help...one more question Trying to figure out a better way to time the sorting, but there is no gethrtime on this computer(running MAC OS) Any suggestions?(is running sorts for small numbers several times and taking the average the only way, or is there something else I may be able to use?) http://www.mindspring.com/~pfilandr/C/e_driver/ http://www.mindspring.com/~pfilandr/...ver/e_driver.c loop_time = sort_time(s_L, s, n, 0, loops, &sort_error); s_time = sort_time(s_L, s, n, sort, loops, &sort_error) s_time -= loop_time; double sort_time(struct sf *s_L, e_type **s, size_t nmemb, size_t sort, long unsigned loops, int *sort_error) { size_t i; clock_t start, stop; start = clock(); while (start == clock()) { ; } start = clock(); while (loops-- != 0) { copyarray(s, s, nmemb); s_L[sort].sortfunc(s, nmemb); } stop = clock(); *sort_error = 0; switch (sort) { case 0: break; case 1: for (i = 1; nmemb i; ++i) { if (GT(s + i - 1, s + i)) { *sort_error = 1; break; } } copyarray(s, s, nmemb); break; default: if (comparray(s, s, nmemb) != 0) { *sort_error = 2; } break; } return (double)(stop - start) / (double)CLOCKS_PER_SEC; } -- pete Oct 21 '06 #5

 P: n/a ra*******@yahoo.com wrote: > Trying to figure out a better way to time the sorting, but there is no gethrtime on this computer(running MAC OS) What sorting? Quote sufficient material so that your posting makes some sense. -- Chuck F (cbfalconer at maineline dot net) Available for consulting/temporary embedded and systems. Oct 22 '06 #6

 P: n/a The mergesort and quicksort that I originally posted about... CBFalconer wrote: ra*******@yahoo.com wrote: Trying to figure out a better way to time the sorting, but there is no gethrtime on this computer(running MAC OS) What sorting? Quote sufficient material so that your posting makes some sense. -- Chuck F (cbfalconer at maineline dot net) Available for consulting/temporary embedded and systems. Oct 22 '06 #7

 P: n/a ra*******@yahoo.com should have written (but didn't because he top-posted instead): CBFalconer wrote: ra*******@yahoo.com wrote: > Trying to figure out a better way to time the sorting, but there is no gethrtime on this computer(running MAC OS) What sorting? Quote sufficient material so that your posting makes some sense. The mergesort and quicksort that I originally posted about... A few rules of thumb: 1) Don't top-post. 2) Keep context in the article. 3) Remove other people's signature blocks from your response. -- Bill Pursell Oct 22 '06 #8

 P: n/a ra*******@yahoo.com wrote: [format corrected] CBFalconer wrote: >>ra*******@yahoo.com wrote: >>>Trying to figure out a better way to time the sorting, but thereis no gethrtime on this computer(running MAC OS) What sorting? Quote sufficient material so that your posting makessome sense. The mergesort and quicksort that I originally posted about... Which doesn't compile. You realy have to post code that compiles to get any help. -- Ian Collins. Oct 22 '06 #9

 P: n/a Ian Collins said: ra*******@yahoo.com wrote: >>> The mergesort and quicksort that I originally posted about... Which doesn't compile. You realy have to post code that compiles to get any help. ....unless, of course, the question is "why won't this !\$&*!%)&\$ compile?" :-) -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at above domain (but drop the www, obviously) Oct 23 '06 #11 