CODEWITHSUNDEEP
cquicksort
JMS
JMS

Reputation: 281

Quicksort implementation in c

I have a quicksort program which executes as shown. But the last element is not getting sorted. Can anyone tell me how to modify the program to obtain the correct result.

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

static void swap(void *x, void *y, size_t l)
{
    char *a = x, *b = y, c;
    while(l--)
    {
        c = *a;
        *a++ = *b;
        *b++ = c;
    }
}

static void sort(char *array, size_t size, int (*cmp)(void*,void*), int begin, int end)
{
    if (end > begin)
    {
        void *pivot = array + begin;
        int l = begin + size;
        int r = end;
        while(l < r)
        {
            if (cmp(array+l,pivot) <= 0)
            {
                l += size;
            }
            else if ( cmp(array+r, pivot) > 0 )
            {
                r -= size;
            }
            else if ( l < r )
            {
                swap(array+l, array+r, size);
            }
        }
        l -= size;
        swap(array+begin, array+l, size);
        sort(array, size, cmp, begin, l);
        sort(array, size, cmp, r, end);
    }
}

void qsort(void *array, size_t nitems, size_t size, int (*cmp)(void*,void*))
{
    sort(array, size, cmp, 0, (nitems-1)*size);
}

typedef int type;

int type_cmp(void *a, void *b){ return (*(type*)a)-(*(type*)b); }

int main(void)
{ /* simple test case for type=int */
    int num_list[]={5,4,3,2,1};
    int len=sizeof(num_list)/sizeof(type);
    char *sep="";
    int i;
    qsort(num_list,len,sizeof(type),type_cmp);
    printf("sorted_num_list={");
    for(i=0; i<len; i++){
        printf("%s%d",sep,num_list[i]);
        sep=", ";
    }
    printf("};\n");
    return 0;
}

Result:

sorted_num_list={2, 3, 4, 5, 1};

Why?

I tried doing (nitems)*size. But when I try the same for strings, it gives me error

Upvotes: 0

Views: 537

Answers (2)

Jeegar Patel
Jeegar Patel

Reputation: 27210

2 mistakes here...

First change qsort() function names to qsort_user() or any other name then the qsort() because qsort() is the standard function defined in stdlib.h

Then change this line

  sort(array, size, cmp, 0, (nitems-1)*size);

to

  sort(array, size, cmp, 0, (nitems)*size);

Upvotes: 0

tcollart
tcollart

Reputation: 1062

The problem comes from this line:

sort(array, size, cmp, 0, (nitems-1)*size);

nitems is your number of items, here 5, you're substracting one so your quick sort will only sort the 4 first elements. Remove the -1 and it will work.

sort(array, size, cmp, 0, nitems*size);

Upvotes: 2

Related Questions