Velocity Reviews > Seg faults in merge and quick sort

# Seg faults in merge and quick sort

ralphedge@yahoo.com
Guest
Posts: n/a

 10-20-2006
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?

Mike Wahler
Guest
Posts: n/a

 10-20-2006

<(E-Mail Removed)> wrote in message
news:(E-Mail Removed) ups.com...
> These sorts work fine on 100000 ints but if I go much higher they will
> both segmentation fault

Post code that compiles, and maybe we'll have
a chance at helping find the problem.

A few things that stand out in your code:

-There are no declarations in scope for the
standard library functions you use. This can
often lead to unexpected behavior, and for
variadic functions such as 'printf()' the
behavior is undefined.

-The number of elements in an array definition
must be specified with a constant expression,
unless using a C99 compiler. Since the 'implicit
int' return type is not allowed by C99, it doesn't
appear you're using one. Perhaps you're using
some nonstandard feature of your compiler.

-Sizes of things (such as arrays) should be declared
with type 'size_t', not 'int'. Only 'size_t' is
guaranteed to be able to represent every possible
object size for a given implementation. If a signed
type such as 'int' is assigned a value outside its
range, the behavior is undefined. ("overflow" only
has a defined behavior for unsigned types).

I didn't even look at the logic of your code, too
many other fundamental issues need fixing first.

-Mike

dcorbit@connx.com
Guest
Posts: n/a

 10-20-2006
/*
** There is still lots of room for improvement here. You were missing
** and prototypes, and had implicit declaration of function types.
** You were getting segfaults because of the size of your automatic
variables.
** You should do a test to prove that the data is sorted.
** creating a reversed partition were wrong...) but creating a reversed
partition
** is a very good idea [hint -- this onerous version of qsort will
positively blow chunks]
*/

#include <stdlib.h>

extern void merge(int *, int *, int *, int);
extern void mergesort(int *, int);
extern int partition(int *, int, int);
extern void q_sort(int *, int, int);
extern void quicksort(int *, int);
extern void swap(int *, int, int);

void mergesort(int *a, int size)
{
int *b;
int *c;
int *bp;
int *cp;
int x;
int y;

b = malloc((size / 2) * sizeof *b);
c = malloc((size - (size / 2)) * sizeof *c);
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);
}
}

void 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++;
}
}
}

void quicksort(int *a, int size)
{
q_sort(a, 0, size - 1);
}

void q_sort(int *a, int l, int r)
{
int s;
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;
}

void swap(int *a, int b, int c)
{
int temp = *(a + b);
*(a + b) = *(a + c);
*(a + c) = temp;
}

#ifdef UNIT_TEST

#include <stdio.h>
#include <time.h>

int main(int argc, char **argv)
{
int size = 100000;
int *a;
int *ap,
x;
time_t t0,
t1;
clock_t c0,
c1;

if (argc > 0) {
int tsize;
tsize = atoi(argv[1]);
if (tsize > 0) {
size = tsize;
} else {
printf("Invalid size of %d specified. Using 10000.\n",
tsize);
}
}
a = malloc(size * sizeof *a);
if (a == NULL) {
puts("ERROR: Out of memory.");
exit(EXIT_FAILURE);
}
ap = a;
for (x = 0; x < size; x++) {
a[x] = rand() % size;
}
t0 = time(NULL);
c0 = clock();
printf("\nMergesorting\n");
mergesort(ap, size);
t1 = time(NULL);
c1 = clock();
printf("\nMergesort(%d items)\nTime Difference: %f\tClock Cycle
Difference: %f\n",
size, (float) (t1 - t0), (float) (c1 - c0));

for (x = 0; x < size; x++) {
a[x] = rand() % size;
}

t0 = time(NULL);
c0 = clock();
quicksort(ap, size);
t1 = time(NULL);
c1 = clock();
printf("\nQuicksort(%d items)\nTime Difference: %f\tClock Cycle
Difference: %f\n",
size, (float) (t1 - t0), (float) (c1 - c0));
return 0;
}
#endif
/*
C:\tmp>cl /W4 /Ox /DUNIT_TEST stest.c
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.42
for 80x86

stest.c
stest.c(91) : warning C4127: conditional expression is constant
Microsoft (R) Incremental Linker Version 8.00.50727.42

/out:stest.exe
stest.obj

C:\tmp>stest -9
Invalid size of -9 specified. Using 10000.

Mergesorting

Mergesort(100000 items)
Time Difference: 0.000000 Clock Cycle Difference: 93.000000

Quicksort(100000 items)
Time Difference: 0.000000 Clock Cycle Difference: 0.000000

C:\tmp>stest frog
Invalid size of 0 specified. Using 10000.

Mergesorting

Mergesort(100000 items)
Time Difference: 0.000000 Clock Cycle Difference: 93.000000

Quicksort(100000 items)
Time Difference: 0.000000 Clock Cycle Difference: 16.000000

C:\tmp>stest 0
Invalid size of 0 specified. Using 10000.

Mergesorting

Mergesort(100000 items)
Time Difference: 0.000000 Clock Cycle Difference: 109.000000

Quicksort(100000 items)
Time Difference: 0.000000 Clock Cycle Difference: 16.000000

C:\tmp>stest 1000000

Mergesorting

Mergesort(1000000 items)
Time Difference: 1.000000 Clock Cycle Difference: 1032.000000

Quicksort(1000000 items)
Time Difference: 0.000000 Clock Cycle Difference: 141.000000

C:\tmp>stest 10000000

Mergesorting

Mergesort(10000000 items)
Time Difference: 24.000000 Clock Cycle Difference: 23391.000000

Quicksort(10000000 items)
Time Difference: 4.000000 Clock Cycle Difference: 3703.000000

*/

ralphedge@yahoo.com
Guest
Posts: n/a

 10-21-2006
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?)

pete
Guest
Posts: n/a

 10-21-2006
http://www.velocityreviews.com/forums/(E-Mail Removed) 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[1], s[2], nmemb);
s_L[sort].sortfunc(s[1], nmemb);
}
stop = clock();
*sort_error = 0;
switch (sort) {
case 0:
break;
case 1:
for (i = 1; nmemb > i; ++i) {
if (GT(s[1] + i - 1, s[1] + i)) {
*sort_error = 1;
break;
}
}
copyarray(s[0], s[1], nmemb);
break;
default:
if (comparray(s[0], s[1], nmemb) != 0) {
*sort_error = 2;
}
break;
}
return (double)(stop - start) / (double)CLOCKS_PER_SEC;
}

--
pete

CBFalconer
Guest
Posts: n/a

 10-22-2006
(E-Mail Removed) 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.
<http://cbfalconer.home.att.net>

ralphedge@yahoo.com
Guest
Posts: n/a

 10-22-2006
The mergesort and quicksort that I originally posted about...

CBFalconer wrote:
> (E-Mail Removed) 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.
> <http://cbfalconer.home.att.net>

Bill Pursell
Guest
Posts: n/a

 10-22-2006
(E-Mail Removed) should have written (but didn't because
> CBFalconer wrote:
> > (E-Mail Removed) 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

Ian Collins
Guest
Posts: n/a

 10-22-2006
(E-Mail Removed) wrote:
[format corrected]

> CBFalconer wrote:
>
>>(E-Mail Removed) 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...
>

Which doesn't compile. You realy have to post code that compiles to get
any help.

--
Ian Collins.

CBFalconer
Guest
Posts: n/a

 10-22-2006
(E-Mail Removed) wrote:
> CBFalconer wrote:
>> (E-Mail Removed) 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...

after, or possibly intermixed with, the snipped material to which

Your original post has nothing to do with it. It is long gone from
here, if it ever arrived. Usenet is not a reliable medium. Google
is not a respectable interface to Usenet. Your articles should
stand by themselves, because there is no guarantee that any other
articles are visible to the reader. That is the purpose of
quoting.

Get yourself a proper newsreader. Thunderbird from mozilla.org
comes to mind. If your ISP is so faulty that it doesn't provide a
newserver, try teranews.com.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>