CODEWITHSUNDEEP
csortingmergesort
Gannicus
Gannicus

Reputation: 530

Keeps getting garbage values when doing merge sort in C

I am working on a generic merge sort algorithm. Now the problem is I keep getting garbage values when I print the content of the supposedly "sorted" array.

The merge sort algorithm:

void merge(void *a, int n, int size, int (*fcmp)(const void *, const void *)){
    int i, j, k, mid=n/2;
    void * temp = (void *)malloc(n*size);

    for(i=0, j=mid, k=0; k<n; k++){
        if((i<mid)&&(j>=  n)){
            memcpy(temp+(k*size), a+i*size, size);
            i++;
        }
        else if((i<mid)&&(fcmp(a + i*size, a+j*size) <= 0)){
            memcpy(temp+(k*size), a+j*size, size);
            j++;
        }
    }

    for(i=0, j=0; j<n; i++, j++)
        memcpy(a+(j*size),temp+(i*size),size);
    free(temp);
}

void genmsort(void *a, int n, int size, int (*fcmp)(const void *, const void *)){
    if(n>1){
        genmsort(a, n/2, size, (int(*)(const void *, const void *)) compnode);
        genmsort(a+(n/2)*size, n-n/2, size, (int(*)(const void *, const void *)) compnode);
        merge(a, n, size, (int(*)(const void *, const void *)) compnode);
    }
}

The compnode function:

int compnode(node *a, node *b){
    return (strcmp(a->name, b->name));
}

The initialization function:

void init_node(node a[], int n){
int i;
    for(i=0; i<n; i++){
        a[i].stdno=i+1;
        sprintf(a[i].name, "%li", a[i].stdno);
    }
    srand(8);
    for(i=0; i<n; i++)
        genswap(a+i, a+(rand()%n), sizeof(node));
}

And the main function: 

int main(){
    int n=10;
    clock_t t1, t2;

    node *b;
    b=(node *)malloc(n*sizeof(node));
    init_node(b, n);

    t1=clock();
    genmsort(b, n, sizeof(node), (int(*)(const void *, const void *)) compnode);

    t2=clock();
    free(b);
}

What could be wrong here? I'm sorry for the lengthy code but I hope you can understand it. I would really appreciate your help because I am stuck with this code for some time now.

Upvotes: 1

Views: 393

Answers (2)

Jonathan Leffler
Jonathan Leffler

Reputation: 753585

Auxilliary problems

Transcribed from the comments to the question.

For pity's sake, write compnode() sanely so that you don't have to go through the ghastly casts! Write it to take two const void * arguments and convert them in the code (it'll be a no-op):

int compnode(const void *v1, const void *v2)
{
    const node *a = v1;
    const node *b = v2;
    return strcmp(a->name, b->name);
}

Also, don't use GCC's extensions. It is a bad habit if you have any pretensions towards writing portable code. Writing a+(n/2)*size where the argument is void *a is undefined behaviour per the C standard. You have to convert to char * (or some other type other than void *) before adding.

In genmnode(), you should be passing fcmp to the recursive functions and the merge() function, instead of passing compnode() directly.

Gannicus asked:

What do you mean pass fcmp instead of compnode?

WhozCraig explained:

[It] means you're passing your custom comparator function to the "generic" sort function as the fcmp parameter. Within that function, you blindly pass compnode to the recursive calls. You should be passing fcmp to those recursive calls instead, or your "generic" ideology just went out the window.

Primary problem

The primary problem is in your merge() function. The interface to that is most unusual. Normally, you pass two arrays to be merged, along with the size of each. You've chosen to pass one array and do some fancy footwork. The code in the main for loop in screws everything up.

void merge(void *a, int n, int size, int (*fcmp)(const void *, const void *)){
    int i, j, k, mid=n/2;
    void * temp = (void *)malloc(n*size);

    for(i=0, j=mid, k=0; k<n; k++){
        if((i<mid)&&(j>=  n)){
            memcpy(temp+(k*size), a+i*size, size);
            i++;
        }
        else if((i<mid)&&(fcmp(a + i*size, a+j*size) <= 0)){
            memcpy(temp+(k*size), a+j*size, size);
            j++;
        }
    }

    for(i=0, j=0; j<n; i++, j++)
        memcpy(a+(j*size),temp+(i*size),size);
    free(temp);
}

The trailing loop should be a single memcpy() operation, but what's there will work.

You have a single array, a, with a total of n elements of the given size. It must be treated as two sub-arrays, one of elements [0..mid), the LHS, and the other of elements [mid..n), the RHS. The ranges include the lower bound and exclude the upper bound.

The first condition inside the loop says 'if there is an element left in LHS and nothing left in RHS, copy the LHS element to the output'. The second condition says 'if there is an element left in the LHS (and, by elimination, there is an element in the RHS too), and the LHS compares smaller than the RHS, then copy the RHS element to the output'.

There are different and ultimately equivalent ways to write the merge process, but normally the easiest to understand is:

while (item left in LHS and item left in RHS)
{
    if (item in LHS is smaller than item in RHS)
        copy LHS to result
    else
        copy RHS to result
}
while (item left in LHS)
    copy item to result
while (item left in RHS)
    copy item to result

The loop implemented does not come close to implementing that logic, or one of its equivalents.

Working code

Here's my diagnostic version of your code. The memset() at the top of merge() should not matter; you should be copying to temp and writing over all the X's. In practice, you are not.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node node;
struct node
{
    long stdno;
    char name[20];
};

static
void genswap(void *v1, void *v2, size_t size)
{
    char v3[size];
    memmove(v3, v1, size);
    memmove(v1, v2, size);
    memmove(v2, v3, size);
}

static
void print_node(const char *tag, node a[], int n)
{
    printf("%s\n", tag);
    for (int i = 0; i < n; i++)
        printf("%2d: %p %2ld %s\n", i, &a[i], a[i].stdno, a[i].name);
}

static
void merge(void *a, int n, int size, int (*fcmp)(const void *, const void *))
{
    int i, j, k, mid = n/2;
    void *temp = (void *)malloc(n*size);
    memset(temp, 'X', n*size);

    printf("-->> %s\n", __func__);
    print_node("Before Merge", (node *)a, n);
    for (i = 0, j = mid, k = 0; k < n; k++)
    {
        if ((i < mid) && (j >= n))
        {
            memcpy(temp+(k*size), a+i*size, size);
            i++;
        }
        else if ((i < mid) && (fcmp(a + i*size, a+j*size) <= 0))
        {
            memcpy(temp+(k*size), a+j*size, size);
            j++;
        }
    }
    print_node("Mid Merge", (node *)temp, n);

    for (i = 0, j = 0; j < n; i++, j++)
        memcpy(a+(j*size), temp+(i*size), size);
    free(temp);
    print_node("After Merge", (node *)a, n);
    printf("<<-- %s\n", __func__);
}

static
void genmsort(void *a, int n, int size, int (*fcmp)(const void *, const void *))
{
    if (n > 1)
    {
        genmsort(a, n/2, size, fcmp);
        genmsort(a+(n/2)*size, n-n/2, size, fcmp);
        merge(a, n, size, fcmp);
    }
}

static
int compnode(const void *v1, const void *v2)
{
    const node *a = v1;
    const node *b = v2;
    printf("%s: (%ld:%s) vs (%ld:%s)\n", __func__, a->stdno, a->name, b->stdno, b->name);
    return(strcmp(a->name, b->name));
}

static
void init_node(node a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        a[i].stdno = i+1;
        sprintf(a[i].name, "%li", a[i].stdno);
    }
    srand(8);
    for (int i = 0; i < n; i++)
        genswap(a+i, a+(rand()%n), sizeof(node));
}

int main(void)
{
    int n = 10;
    node *b = (node *)malloc(n*sizeof(node));

    init_node(b, n);
    print_node("Before:", b, n);
    genmsort(b, n, sizeof(node), compnode);
    print_node("After:", b, n);
    free(b);

    return 0;
}

Upvotes: 2

WhozCraig
WhozCraig

Reputation: 66194

The latitude of things in this code are copious. Some are show-stoppers, but ultimately it is your merge function. A typical merge algorithm moves one item into the target buffer with each iteration until such time as one list or the other is exhausted. Once that happens the remaining items in the remaining list are bulk-copied into place and the algorithm terminates.

You have a fundamental flaw, and we'll cover that now. Your main loop runs k all the way through to n, and at least that is right. But, look at your first expressions in your if-else-if conditions:

    if((i<mid)&&(j>=  n))
    {
        memcpy(temp+(k*size), a+i*size, size);
        i++;
    }
    else if((i<mid)&&(fcmp(a + i*size, a+j*size) <= 0))
    {
        memcpy(temp+(k*size), a+j*size, size);
        j++;
    }

They both have i<mid, so this could be simplified to be:

    if (i<mid)
    {
        if (j>=n)
        {
            memcpy(temp+(k*size), a+i*size, size);
            i++;
        }
        else if (fcmp(a + i*size, a+j*size) <= 0))
        {
            memcpy(temp+(k*size), a+j*size, size);
            j++;
        }
    }

which means if your i-side is ever exhausted before your j-side, you simply do nothing from that point on, just incrementing k until it reaches n. The rest of the j-side of the split-list is completely ignored. Then, at the end of the function you copy uninitialized data right over the top of your original array.

Some things to consider. First, typedef your comparator function requirements and stick to it. It is the responsibility of the comparator to adhere to the requirements of the callback-requestor; not the other way around.

typedef int (*fn_cmp)(const void*, const void*);

and use this correctly by implementing your callback to that standard.

// compare two nodes.
int compare_node(const void* lhs, const void* rhs)
{
    const node* lhn = lhs;
    const node* rhn = rhs;
    return (strcmp(lhn->name, rhn->name));
}

This also makes your generic mergesort much cleaner:

// generic mergesort algorithm
void genmsort(void *src, unsigned int len, unsigned int size, fn_cmp fcmp)
{
    if (len < 2)
        return;

    unsigned int mid = len/2;
    genmsort(src, mid, size, fcmp);
    genmsort((unsigned char*)src+(mid*size), len - mid, size, fcmp);
    merge(src, mid, len-mid, size, fcmp);
}

Readability aside, the biggest difference between the following merge and yours is the addition of the second length parameter (the fact that this one works is considered a bonus). You're code inferred this value from the single length originally passed in; something you did in an entirely separate place in your code when calculating your recursive partition sizes Those same sizes need to be passed here as well, for multiple reasons that include consistency and usability).

Consider the following please. If it is possible to annotate this algorithm better, or make it clearer, I'm at a loss to see how:

// merges two lists back to back in a single sequence.
void merge(void *src,
           unsigned int alen, // note parition size.
           unsigned int blen, // and again here.
           unsigned int size,
           fn_cmp fcmp)
{
    void *bsrc = (unsigned char*)src + alen * size;
    void *dst = malloc((alen + blen)*size);
    unsigned int a = 0, b = 0, k = 0;

    for (k=0; k<(alen+blen); ++k)
    {
        // still got a's ?
        if (a < alen)
        {
            // still got b's ?
            if (b < blen)
            {
                // get "lesser" of the two.
                if (fcmp((const unsigned char*)src + a*size,
                         (const unsigned char*)bsrc + b*size) <= 0)
                {
                    // a is less. move it in.
                    memcpy((unsigned char *)dst + k*size,
                           (const unsigned char*)src + a++*size, size);
                }
                else
                {   // b is less. move it in.
                    memcpy((unsigned char *)dst + k*size,
                           (const unsigned char*)bsrc + b++*size, size);
                }
            }
            else
            {   // no more b's. move the rest of the a's
                // into the target and leave.
                memcpy((unsigned char *)dst + k*size,
                       (const unsigned char*)src + a*size, (alen - a)*size);
                k += (alen-a);
            }
        }
        else
        {   // else no a's. move the rest of the b's into
            //  the target and leave.
            memcpy((unsigned char *)dst + k*size,
                   (const unsigned char*)bsrc + b*size, (blen - b)*size);
            k += (blen-b);
        }
    }

    // copy final output.
    memcpy(src, dst, (alen+blen)*size);
    free(dst);
}

Finally, this codes does not require any compiler extensions such as the standard-violating incremental void* you so-heavily exploited in your code. I strongly advise you stay clear of such extensions.

The following is the full test program used to verify the algorithm above and its interface. Read it carefully.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#include <time.h>

// simple node definition.
typedef struct node
{
    char name[32];
    int id;
} node;

// compare two nodes.
int compare_node_names(const void* lhs, const void* rhs)
{
    const node* lhn = lhs;
    const node* rhn = rhs;
    return (strcmp(lhn->name, rhn->name));
}

// compare two nodes.
int compare_node_ids(const void* lhs, const void* rhs)
{
    const node* lhn = lhs;
    const node* rhn = rhs;
    return (lhn->id  - rhn->id);
}

// comparator requirements.
typedef int (*fn_cmp)(const void*, const void*);

// merges two lists back to back in a single sequence.
void merge(void *src,
           unsigned int alen, // note parition size.
           unsigned int blen, // and again here.
           unsigned int size,
           fn_cmp fcmp)
{
    void *bsrc = (unsigned char*)src + alen * size;
    void *dst = malloc((alen + blen)*size);
    unsigned int a = 0, b = 0, k = 0;

    for (k=0; k<(alen+blen); ++k)
    {
        // still got a's ?
        if (a < alen)
        {
            // still got b's ?
            if (b < blen)
            {
                // get "lesser" of the two.
                if (fcmp((const unsigned char*)src + a*size,
                         (const unsigned char*)bsrc + b*size) <= 0)
                {
                    // a is less. move it in.
                    memcpy((unsigned char *)dst + k*size,
                           (const unsigned char*)src + a++*size, size);
                }
                else
                {   // b is less. move it in.
                    memcpy((unsigned char *)dst + k*size,
                           (const unsigned char*)bsrc + b++*size, size);
                }
            }
            else
            {   // no more b's. move the rest of the a's
                // into the target and leave.
                memcpy((unsigned char *)dst + k*size,
                       (const unsigned char*)src + a*size, (alen - a)*size);
                k += (alen-a);
            }
        }
        else
        {   // else no a's. move the rest of the b's into
            //  the target and leave.
            memcpy((unsigned char *)dst + k*size,
                   (const unsigned char*)bsrc + b*size, (blen - b)*size);
            k += (blen-b);
        }
    }

    // copy final output.
    memcpy(src, dst, (alen+blen)*size);
    free(dst);
}

// generic mergesort algorithm
void genmsort(void *src, unsigned int len, unsigned int size, fn_cmp fcmp)
{
    if (len < 2)
        return;

    unsigned int mid = len/2;
    genmsort(src, mid, size, fcmp);
    genmsort((unsigned char*)src+(mid*size), len - mid, size, fcmp);
    merge(src, mid, len-mid, size, fcmp);
}

int main()
{
    static const unsigned int N = 50;
    node *data = malloc(N * sizeof(*data));
    int i=0;

    srand((unsigned)time(NULL));
    for (i=0;i<N;++i)
    {
        data[i].id = i+1;
        sprintf(data[i].name, "String%.3d", 1 + rand() % 999);
    }

    // sort on names.
    genmsort(data, N, sizeof(data[0]), compare_node_names);
    for (i=0;i<N;++i)
        printf("%s : %u\n", data[i].name, data[i].id);
    printf("\n");

    // use a different comparator, this time by id.
    genmsort(data, N, sizeof(data[0]), compare_node_ids);
    for (i=0;i<N;++i)
        printf("%s : %u\n", data[i].name, data[i].id);
    printf("\n");

    free(data);

    return 0;
}

Output

String053 : 49
String097 : 38
String104 : 46
String122 : 41
String129 : 8
String139 : 3
String168 : 30
String184 : 22
String222 : 16
String230 : 28
String249 : 4
String265 : 34
String285 : 44
String295 : 20
String298 : 47
String300 : 19
String321 : 2
String375 : 37
String396 : 50
String408 : 13
String430 : 31
String466 : 35
String483 : 24
String484 : 27
String491 : 25
String494 : 39
String507 : 10
String513 : 7
String514 : 11
String539 : 5
String556 : 29
String570 : 43
String583 : 33
String584 : 42
String620 : 15
String632 : 12
String671 : 21
String705 : 23
String710 : 14
String714 : 45
String724 : 18
String733 : 9
String755 : 48
String805 : 36
String814 : 6
String847 : 32
String876 : 40
String893 : 26
String906 : 17
String972 : 1

String972 : 1
String321 : 2
String139 : 3
String249 : 4
String539 : 5
String814 : 6
String513 : 7
String129 : 8
String733 : 9
String507 : 10
String514 : 11
String632 : 12
String408 : 13
String710 : 14
String620 : 15
String222 : 16
String906 : 17
String724 : 18
String300 : 19
String295 : 20
String671 : 21
String184 : 22
String705 : 23
String483 : 24
String491 : 25
String893 : 26
String484 : 27
String230 : 28
String556 : 29
String168 : 30
String430 : 31
String847 : 32
String583 : 33
String265 : 34
String466 : 35
String805 : 36
String375 : 37
String097 : 38
String494 : 39
String876 : 40
String122 : 41
String584 : 42
String570 : 43
String285 : 44
String714 : 45
String104 : 46
String298 : 47
String755 : 48
String053 : 49
String396 : 50

Upvotes: 2

Related Questions