Seg faults in merge and quick sort

Discussion in 'C Programming' started by ralphedge@yahoo.com, Oct 20, 2006.

  1. Guest

    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, 2006
    #1
    1. Advertising

  2. Mike Wahler Guest

    <> wrote in message
    news:...
    > 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
     
    Mike Wahler, Oct 20, 2006
    #2
    1. Advertising

  3. Guest

    /*
    ** There is still lots of room for improvement here. You were missing
    header files
    ** 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.
    ** You should try other distributions besides random (your comments
    about
    ** 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
    Copyright (C) Microsoft Corporation. All rights reserved.

    stest.c
    stest.c(91) : warning C4127: conditional expression is constant
    Microsoft (R) Incremental Linker Version 8.00.50727.42
    Copyright (C) Microsoft Corporation. All rights reserved.

    /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

    */
     
    , Oct 20, 2006
    #3
  4. Guest

    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, 2006
    #4
  5. pete Guest

    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/C/e_driver/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
     
    pete, Oct 22, 2006
    #5
  6. CBFalconer Guest

    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>
     
    CBFalconer, Oct 22, 2006
    #6
  7. Guest

    The mergesort and quicksort that I originally posted about...


    CBFalconer wrote:
    > 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>
     
    , Oct 22, 2006
    #7
  8. Bill Pursell Guest

    should have written (but didn't because
    he top-posted instead):
    > CBFalconer wrote:
    > > 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
     
    Bill Pursell, Oct 22, 2006
    #8
  9. Ian Collins Guest

    wrote:
    [format corrected]

    > CBFalconer wrote:
    >
    >> 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.
     
    Ian Collins, Oct 22, 2006
    #9
  10. CBFalconer Guest

    wrote:
    > CBFalconer wrote:
    >> 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...


    Rude top-posting fixed again. Don't top-post. Your reply belongs
    after, or possibly intermixed with, the snipped material to which
    you reply.

    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>
     
    CBFalconer, Oct 22, 2006
    #10
  11. Ian Collins said:

    > 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)
     
    Richard Heathfield, Oct 23, 2006
    #11
  12. Groovy hepcat was jivin' on 20 Oct 2006 14:00:44
    -0700 in comp.lang.c.
    Seg faults in merge and quick sort's a cool scene! Dig it!

    >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


    // comments are invalid in C90. Implicit int return type is invalid
    in C99. Are you writing C90 or C99 code? Either way you have invalid
    code.
    Don't post code with // comments here. They have a tendancy to wrap,
    making it hard to copy, paste and compile your code.
    You have an int function (in C90, but nothing valid in C99), but are
    not returning anything from it. This is invalid. Perhaps you want a
    void function instead?

    void mergesort(int *a, int size)
    >{
    >
    > int b[(size/2)];
    > int c[(size-(size/2))];


    VLAs are invalid in C90.

    > int *bp;
    > int *cp;
    > int x;
    > int y;
    > bp = b;
    > cp = c;


    What's the point of that? As far as I can see you're not using bp
    and cp, except to pass them to mergesort(). Why not just pass b and c
    instead?

    > if(size > 1)
    > {
    >
    > for(x = 0; x < (size/2); x++)
    > {
    > b[x] = *(a + x);


    What's with the *(a + x) notation? It's not wrong; but it is
    inconsistent when you have b[x]. What's wrong with b[x] = a[x] or
    (less clearly) *(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)));


    There's no declaration of mergesort() in scope.

    > merge(a, bp, cp, size);


    There's no declaration of merge() in scope.

    > }
    >}
    >
    >merge(int *a, int *b, int *c, int size)


    Once again, this is invalid: int function (in C90) without returning
    anything. Want a void function?

    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++;
    > }
    > }
    >}
    >
    >********************QUICKSORT*****************
    >
    >quicksort(int *a, int size)


    Once again, this is invalid: int function (in C90) without returning
    anything. Want a void function?

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


    There's no declaration of q_sort() in scope.

    >}
    >
    >q_sort(int *a, int l, int r)


    Once again, this is invalid: int function (in C90) without returning
    anything. Want a void function?

    void q_sort(int *a, int l, int r)
    >{
    > int s;
    > //printf("\n%d - size", (r - l));


    If you must comment things out, cut them out altogether before
    posting. Otherwise they just clutter the code.

    > if(l < r)
    > {
    > s = partition(a, l, r);
    > q_sort (a, l, s - 1);
    > q_sort(a, s + 1, r);


    There's no declaration of q_sort() in scope.

    > }
    >}
    >
    >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);


    There's no declaration of swap() in scope.

    > }
    > swap(a, l, j);


    There's no declaration of swap() in scope.

    > return j;
    >}
    >
    >swap(int *a, int b, int c)


    Once again, this is invalid: int function (in C90) without returning
    anything. Want a void function?

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


    Once again, you should specify the return type to be C99 compatible.
    It is a good idea in C90 too. In either case, main() should return an
    int. And do remember to return a value. Portable and valid return
    values include 0, EXIT_SUCCESS and EXIT_FAILURE (the latter two
    defined in stdlib.h).

    int main(void)
    >{
    > int size = 100000, a[size], *ap, x;
    > ap = a;
    > time_t t0, t1;
    > clock_t c0, c1;


    time_t and clock_t are undeclared. They're not built-in types,
    y'know. You have to define them by including time.h. You also need
    this header for the time() and clock() functions.

    > for(x = 0; x < size; x++) //set array in reverse order
    > {
    > a[x] = random()%size;
    > }
    > t0 = time(NULL);
    > c0 = clock();


    There's no declaration of time() or clock() in scope. See above.

    > 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));


    Look what you've done! You've created a string literal so big it
    wraps. This will not compile when copy/paste/compiled. Break large
    string literals down before posting. Eg.:

    printf("\nMergesort(%d items)\nTime Difference: %f\tClock "
    "Cycle Difference: %f\n",
    size, (float) (t1-t0), (float) (c1-c0));

    Adjacent string literals are merged into a single string, thus what
    looks like two separate strings here actually end up as a single
    string.
    Also, these casts are rather pointless. t0 and t1 are time_t, which
    might be an integer type. In that case t1 - t0 would be calculated in
    integer arithmetic. You then cast the resulting integer to float and
    print the value as double. (printf()'s %f conversion specifier is for
    double, not float. But that's sort of OK, because floats are promoted
    to double when passed to a variadic function such as printf().
    However, double would be a better type to cast to, to avoid the need
    for promotion.) Now, perhaps what you really need is (double)t1 -
    (double)t0. This casts t1 and t0 to double *before* the calculation
    takes place. Thus the calculation is done in double precision floating
    point arithmetic, and you get a double result. Remember:

    (type_X)(a - b)

    means subtract a from b and then cast the result to type_X, whereas:

    (type_X)a - (type_X)b

    means cast a and b to type_X and then subtract the result of the
    former cast from the result of of the latter. The ultimate results are
    very different.
    Anyhow, it is rather pointless to do any casting anyhow. You're
    subtracting (what might be) an integer from (what might be) an
    integer. What possible benefit can be gained by casting to a floating
    type? To get the difference between two time_t values as a floating
    value representing seconds (which makes a little more sense), you
    should use difftime().
    Just one more thing about the above printf() statement. You need to
    include stdio.h for a prototype of printf(). Otherwise you invoke
    undefined behaviour.

    > size = 100000;
    > for(x = 0; x < size; x++) //set array in random order
    > {
    > a[x] = random()%size;


    There's no declaration of random() in scope. It is not a standard
    function, and you haven't defined it yourself.

    > }
    >
    > 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));


    See above.

    return 0;
    >}


    You need to indent better and more consistently. You should use more
    white space, and use it more logically and consistently. Code that is
    ugly or poorly laid out is harder to read and understand than nicely
    formatted code.

    >Any idea why I'm getting seg errors?


    Are you sure you can create automatic arrays as large as 100000 *
    sizeof(int)? My guess is that your implementation allocates automatic
    variables on a stack, and that you are overflowing the stack. Of
    course, this is just a guess. I haven't paid too much attention to
    your program's logic. (That's what comes from writing code that's
    poorly laid out. If you make it hard for us to read, we very often
    just couldn't be bothered trying to figure it out.) I might have
    missed something that could cause a segfault.

    --

    Dig the even newer still, yet more improved, sig!

    http://alphalink.com.au/~phaywood/
    "Ain't I'm a dog?" - Ronny Self, Ain't I'm a Dog, written by G. Sherry & W. Walker.
    I know it's not "technically correct" English; but since when was rock & roll "technically correct"?
     
    Peter Shaggy Haywood, Oct 24, 2006
    #12
  13. On 20 Oct 2006 14:00:44 -0700, wrote:

    > These sorts work fine on 100000 ints but if I go much higher they will
    > both segmentation fault
    >


    Your mergesort allocates in aggregate about 2N worth of temporaries at
    one time, in addition to N in main(), on the stack. Assuming 8-bit
    byte and 32-bit int as are pretty widespread today but not universal,
    that's 1.2MB. Some (many?) implementations (and the platforms they run
    on) have stacksize limits significantly less than the address-space
    because it is assumed that 'runaway' stack usage is likely a bug
    and/or to allow for multiple threads each with their own stack. You
    don't identify your implementation but there may well be an
    implementation dependent way of increasing the stacksize.

    Alternatively, using malloc as suggested by Dann Corbit will often
    allow much larger total allocation (from heap space) but: (1) you
    should still check for failure and do something more intelligent than
    using a failed allocation, at least output a clear error message
    before suiciding; and (2) you should free() before returning from each
    level as otherwise your total (cumulative) allocation is roughly N *
    log2 N actual data (not N * (2+eps)) plus a _lot_ of overhead for the
    huge number of small allocations. That last you could avoid by
    switching to something else, even bubblesort, below some floor like 8
    or 16; this is often a good idea in any case as the k for the 'good'
    O(N logN) methods is usually higher than for the simple O(bad) ones.

    Alternatively alternatively, since these allocations are strictly LIFO
    and of one known element type and of a knowable total, you could do
    your own ad-hoc allocation out of a single large static array, or
    perhaps a single large malloc'ed space, with nearly no overhead:

    int tempspace [100000*21/10]; /* slop to allow for quantizing
    on the different call paths; this is probably more than needed
    but it's not worth it to me to do the exact analysis */
    long avail = 100000*21/10;

    /* to be pedantic, those constant expressions could fail on a machine
    with 17-bit to 20-bit ints if the compiler doesn't protect itself as
    any sensible one will; to be absolutely safe suffix with L */

    void mergesort (int *a, size_t n)
    {
    int *b = & tempspace [ avail -= n/2 ];
    int *c = & tempspace [ avail -= n - n/2 ];
    /* or int * b = tempspace + (avail -= n/2) etc. if you prefer */
    assert (avail >= 0); /* just in case, should never fail */
    ... logic including recursive calls ...
    avail += n;
    }

    You can also simplify things slightly (with any allocation method) by
    allocating _one_ temporary of size n and passing halves in the
    recursive calls and to merge, and it simplifies merge to pass it both
    half-lengths instead of writing out (and perhaps actually executing)
    the split computation in several places:
    int b [n] or int *b = as above;
    memcpy (b, a, n * sizeof *b);
    mergesort (b+0, n/2);
    mergesort (b+n/2, n-n/2);
    merge (a, b, n/2, b+n/2, n-n/2);

    And I see (only?!) Shaggy has noted that *(ary_or_ptr + sub) is
    (exactly!) the same in C as ary_or_ptr[sub], but the latter is more
    common, conventional, and familiar and so usually preferable.

    - David.Thompson1 at worldnet.att.net
     
    Dave Thompson, Nov 6, 2006
    #13
  14. pete Guest

    Dave Thompson wrote:

    > void mergesort (int *a, size_t n)


    > You can also simplify things slightly (with any allocation method) by
    > allocating _one_ temporary of size n and passing halves in the
    > recursive calls and to merge, and it simplifies merge to pass it both
    > half-lengths instead of writing out (and perhaps actually executing)
    > the split computation in several places:


    It makes more sense to allocate one temporary
    of size n/2 for the first half of the array
    and to leave the second half in place.

    /* BEGIN m_sort.h */

    #ifndef H_M_SORT_H
    #define H_M_SORT_H

    #include <stddef.h>
    /*
    ** m_sort is a stable,
    ** merge/insertion sort function.
    */
    void m_sort(void *base, size_t nmemb, size_t size,
    int (*compar)(const void *, const void *));

    #endif

    /* END m_sort.h */

    /* BEGIN m_sort.c */

    #include <stdlib.h>
    #include <assert.h>

    #include "m_sort.h"
    #include "i_sort.h"

    #define TOO_SMALL 1

    #define BYTE_CPY(A, B) \
    { \
    p1 = (A); \
    p2 = (B); \
    end = p2 + size; \
    do { \
    *p1++ = *p2++; \
    } while (p2 != end); \
    }

    static void merg(unsigned char *base, unsigned char *buff,
    size_t nmemb, size_t size,
    int (*compar)(const void *, const void *));

    void m_sort(void *base, size_t nmemb, size_t size,
    int (*compar)(const void *, const void *))
    {
    assert(TOO_SMALL >= 1);
    if (nmemb > TOO_SMALL) {
    void *buff = malloc(nmemb / 2 * size);

    if (buff != NULL) {
    merg(base, buff, nmemb, size, compar);
    free(buff);
    } else {
    /*
    ** If malloc returns NULL,
    ** then you might want to handle it differently.
    */
    i_sort(base, nmemb, size, compar);
    }
    } else {
    i_sort(base, nmemb, size, compar);
    }
    }

    static void merg(unsigned char *base, unsigned char *buff,
    size_t nmemb, size_t size,
    int (*compar)(const void *, const void *))
    {
    if (nmemb > TOO_SMALL) {
    unsigned char *p1, *p2, *end, *mid_ptr;
    size_t const half_nmemb = nmemb / 2;
    size_t const half_bytes = half_nmemb * size;
    unsigned char *const after_buff = buff + half_bytes;
    unsigned char *const middle = base + half_bytes;
    unsigned char *const after_array = base + nmemb * size;

    merg(middle, buff, nmemb - half_nmemb, size, compar);
    merg(base, buff, half_nmemb, size, compar);
    do {
    if (compar(base, middle) > 0) {
    mid_ptr = middle;
    buff = after_buff;
    do {
    buff -= size;
    mid_ptr -= size;
    BYTE_CPY(buff, mid_ptr);
    } while (base != mid_ptr);
    mid_ptr = middle;
    BYTE_CPY(base, mid_ptr);
    mid_ptr += size;
    base += size;
    while (middle != base) {
    if (compar(buff, mid_ptr) > 0) {
    BYTE_CPY(base, mid_ptr);
    mid_ptr += size;
    } else {
    BYTE_CPY(base, buff);
    buff += size;
    }
    base += size;
    }
    while (after_buff != buff) {
    if (after_array != mid_ptr) {
    if (compar(buff, mid_ptr) > 0) {
    BYTE_CPY(base, mid_ptr);
    mid_ptr += size;
    } else {
    BYTE_CPY(base, buff);
    buff += size;
    }
    base += size;
    } else {
    do {
    BYTE_CPY(base, buff);
    base += size;
    buff += size;
    } while (after_buff != buff);
    break;
    }
    }
    break;
    } else {
    base += size;
    }
    } while (middle != base);
    } else {
    i_sort(base, nmemb, size, compar);
    }
    }

    /* END m_sort.c */

    /* BEGIN i_sort.h */

    #ifndef H_I_SORT_H
    #define H_I_SORT_H

    #include <stddef.h>
    /*
    ** i_sort is a stable insertion sort with a qsort interface.
    */
    void i_sort(void *base, size_t nmemb, size_t size,
    int (*compar)(const void *, const void *));

    #endif

    /* END i_sort.h */

    /* BEGIN i_sort.c */

    #include "i_sort.h"

    void i_sort(void *base, size_t nmemb, size_t size,
    int (*compar)(const void *, const void *))
    {
    unsigned char *array, *high, *low, *p1, *p2, *end, swap;

    if (nmemb-- > 1) {
    array = base;
    do {
    low = array;
    array += size;
    high = array;
    while (compar(low, high) > 0) {
    p1 = low;
    p2 = high;
    end = p2 + size;
    do {
    swap = *p1;
    *p1++ = *p2;
    *p2++ = swap;
    } while (p2 != end);
    if (low == base) {
    break;
    }
    high = low;
    low -= size;
    }
    } while (--nmemb != 0);
    }
    }

    /* END i_sort.c */


    --
    pete
     
    pete, Dec 3, 2006
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Andrew King
    Replies:
    1
    Views:
    305
    John Harrison
    Apr 7, 2004
  2. Sharad Kala

    Re: malloc creates seg faults?

    Sharad Kala, Feb 14, 2005, in forum: C++
    Replies:
    2
    Views:
    302
    Sharad Kala
    Feb 14, 2005
  3. Jane Austine
    Replies:
    0
    Views:
    320
    Jane Austine
    Aug 14, 2003
  4. grid

    Optimasation and seg faults

    grid, Jul 20, 2005, in forum: C Programming
    Replies:
    11
    Views:
    511
    SM Ryan
    Jul 21, 2005
  5. sapsi

    QT, ctypes dll and SEG Faults

    sapsi, Aug 17, 2008, in forum: Python
    Replies:
    2
    Views:
    343
    Matthieu Brucher
    Aug 17, 2008
Loading...

Share This Page