Thread: Having trouble sorting an array of strings using a generic quicksort

Yes, that's exactly how the byteswap works.

As for the integer sorting problem, if I copy the code from post one (leaving the compare function, which of course works for small integers just fine) and make changes only to main like this:

Code:

int main()
{
    unsigned int i;
    int a[] = {5, 3, 1, 7, 2};       // int array
 
    size_t numberOfElements = sizeof(a)/sizeof(a[0]);
 
    if(numberOfElements > 1)
    {
        quickSort(a, numberOfElements, sizeof(int), cmp);  // sizeof(int)
    }
 
    for(i = 0; i < numberOfElements; i++)
    {
        printf("%d ", a[i]);      // %d format spec.
    }
 
    return 0;
}

It gives the result: 2 3 1 5 7

Well I made some modifications to my code like removing my is_sorted function for the moment. That might be what is causing the problem because at the end it would not sort it completely because is_sorted would the sorted array before quick sort does and not update it. So I'm probably going to move that function outside or before I call quicksort_r.

Originally Posted by deathslice

Well I made some modifications to my code like removing my is_sorted function for the moment. That might be what is causing the problem because at the end it would not sort it completely because is_sorted would the sorted array before quick sort does and not update it. So I'm probably going to move that function outside or before I call quicksort_r.

That was it. Removing the is_sorted function fixes the problem. Although it looks like whiteflags has spotted the problem!

BTW, an alternative to the byteswap is to use essentially your original routine, but malloc the swap buffer once in the function that calls it, pass the buffer into the swap for it to use, and free the buffer once when the calling function is finished with the swap function. That avoids all the extra malloc's and free's.

I explained why the code crashes in my post. You simply wrote the call incorrectly. Refer again to post #17 for details.

Whiteflags, I said in my previous post(more than likely you read it before I edited it) that you didn't need to explain why it crashed. At this moment I would to like to know how qsort deals with arrays of different dimensions simply because that cmp function only works for 2D arrays not 1D.

It's not a 2D array. It's a 1D array of pointers, similar to the 1D array of integers except that in the case of the integers you're interested in the value of the integers, whereas in the case of the pointers you're not interested in the value of the pointers themselves but in what they are pointing to (for comparison purposes, although you move the pointers around for sorting purposes).

Code:

.   Element Type
*(  const char *   *)a
*(  const int      *)a

Guys I'm having trouble implementing my generic insertion sort. That first thing I noticed was that I was comparing negative numbers because I was using a char ptr which obviously could not point to numbers that are huge. So then I opted for a void * but even that was not enough.

Here are the three main functions in question.

Code:

void insertion_sort(void *base, size_t nitems, size_t memSize, int (*cmp)(const void *, const void *))
{
    char *carray = (char *)base;
    void *tmp;
    unsigned int i;


    for(i = 1; i < nitems; i++)
    {
        int j;


        tmp = &carray[i * memSize];


        for(j = i; j >= 1 && cmp(&carray[(j - 1) * memSize], tmp) > 0; j--)
        {
            Swap(&carray[(j - 1) * memSize], tmp, memSize);
        }
    }
}

int cmp(const void *a, const void *b)
{
   const int *A = a, *B = b;
   printf("%d %d\n", *A, *B);
   return (*A > *B) - (*A < *B);
}


void Swap(void *a, void *b, size_t memSize)
{
    char tmp;
    char *aa = a, *bb = b;


    do
    {
        tmp = *aa;
        *aa++ = *bb;
        *bb++ = tmp;
    }
    while(--memSize > 0);
}

tmp always points to the same place, even after the element has been moved out of that position.

It's inefficient to constantly swap the members when looking for the final position of carray[i*memSize]. Instead, you could save that element and simply move the other elements until the final position is found, then copy the saved element there. No swaps are needed.

Other points:

Since nitems is a size_t you should make i a size_t also (otherwise, even though they are both unsigned, the unsigned int may be shorter than the size_t).

You can typedef your comparison function:

Code:

typedef int (*CmpFunc)(const void *, const void *);
void insertion_sort(void *base, size_t nitems, size_t memSize, CmpFunc cmp);