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

So I've been trying to implement a generic quick sort for educational purposes and so far my quick sort has been able able to sort any array of integers just fine but it does not work with an array of strings. My only guess is that maybe I'm not offsetting the correct amount of bytes since I'm dealing with void pointers

Code

Code:

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

void quickSort(void *, size_t, size_t, int (*cmp)(const void *, const void *));
void quickSort_r(void *, int, int, size_t, int (*cmp)(const void *, const void *));
int qSortPartition(void *, int, int, size_t, int (*cmp)(const void *, const void *));
int is_sorted(void *, size_t, size_t, int (*cmp)(const void *, const void *));
int cmp(const void *, const void *);
void Swap(void *, void *, size_t);

int main()
{
    unsigned int i;
    char *a[] = {"Luis", "Daniel", "Alfredo", "Salvador", "Bruno"};

    size_t numberOfElements = sizeof(a)/sizeof(a[0]);

    if(numberOfElements > 1)
    {
        quickSort(a, numberOfElements, sizeof(char *), cmp);
    }

    for(i = 0; i < numberOfElements; i++)
    {
        printf("%s ", a[i]);
    }

    return 0;
}

void quickSort(void *base, size_t nitems, size_t memSize, int (*cmp)(const void *, const void *))
{
     quickSort_r(base, 0, nitems - 1, memSize, cmp);
}

void quickSort_r(void *base, int first, int last, size_t memSize, int (*cmp)(const void *, const void *))
{
   if(first < last)
   {
       int pivot;

       if(is_sorted(base, last + 1, memSize, cmp))
       {
           return ;
       }

       pivot = qSortPartition(base, first, last, memSize, cmp);

       quickSort_r(base, first, pivot - 1, memSize, cmp);
       quickSort_r(base, pivot + 1, last, memSize, cmp);
   }
}


int qSortPartition(void *base, int first, int last, size_t memSize, int (*cmp)(const void *, const void *))
{
    char *carray = (char *)base;

    int pivot, mid = (first + last) / 2;

    pivot = cmp(&carray[first * memSize], &carray[mid * memSize]) >= 1 ? first : mid;

    if(cmp(&carray[pivot * memSize], &carray[last * memSize]) >= 1)
    {
        pivot = last;
    }

    Swap(&carray[pivot * memSize], &carray[first * memSize], memSize);
    pivot = first;

    while(first < last)
    {
      if(cmp(&carray[first * memSize], &carray[last * memSize]) <= 0)
      {
          Swap(&carray[pivot * memSize], &carray[first * memSize], memSize);
          pivot++;
      }

      first++;
    }

    Swap(&carray[pivot * memSize], &carray[last * memSize], memSize);

    return pivot;
}


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

  for(i = 0; i < nitems - 1; i++)
  {
     if(cmp(&carray[i * memSize], &carray[i + 1 * memSize]) >= 1)
     {
         return 0;
     }
  }

  return 1;
}


int cmp(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}

void Swap(void *a, void *b, size_t memSize)
{
    void *temp = malloc(memSize);
    memcpy(temp, a, memSize);
    memcpy(a, b, memSize);
    memcpy(b, temp, memSize);
    free(temp);
}

You're still comparing ints in your compare function. And you're not actually doing that correctly, either. Consider if 'a' is INT_MIN and 'b' is positive.

BTW, your swap function is very expensive: a malloc and a free and three memcpy's, for every single swap. That's insane. A bytewise copy would be better (with a single temp char).

I don't see how you can sort strings without comparing the strings. For example, with the standard qsort function, your comparison function might be:

Code:

int cmp(const void *a, const void *b) {
    return strcmp(a, b);
}

Code:

int cmp(const void *a, const void *b){
    return strcmp((*(const char **)a), (*(const char **)b));
}

Originally Posted by deathslice

Wouldn't it just be const char *? why are you casting it to a double ptr and deferencing it to a single ptr?

That's not how qsort() does it and I don't think any other re-implementation will be different, either.

When you have a flat array of strings, it's really a 2d array of chars, so you will mostly be treating the data like that. Point into two different rows (each row being a string) and pass those into compare() or whatever it may be called.

For qsort, at least, the two ways you might write the compare function depend on whether it's an array of pointers, like yours is, or an array of strings. I wrote my example compare function for an array of strings. whiteflag's example is correct for an array of pointers to strings.

Code:

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

int cmpa(const void *a, const void *b) {
    return strcmp(*(const char**)a, *(const char **)b);
}

int cmpb(const void *a, const void *b) {
    return strcmp(a, b);
}

int main(void) {
    char *a[] = {"one", "two", "three", "four", "five"};
    char b[][100] = {"one", "two", "three", "four", "five"};

    int lena = sizeof a / sizeof *a;
    qsort(a, lena, sizeof *a, cmpa);
    for (int i = 0; i < lena; i++)
        printf("%s\n", a[i]);

    printf("----\n");

    int lenb = sizeof b / sizeof *b;
    qsort(b, lenb, sizeof *b, cmpb);
    for (int i = 0; i < lenb; i++)
        printf("%s\n", b[i]);

    return 0;
}

Try printing stuff from your compare routine:

Code:

int cmp(const void *a, const void *b) {
    const char *aa = *(const char **)a, *bb = *(const char **)b;
    fprintf(stderr, "comparing: [%s] [%s]\n", aa, bb);
    int ret = strcmp(aa, bb);
    fprintf(stderr, "   result: %d\n", ret);
    return ret;
}

Alright I figured out my problem. The problem was that once my array was finally sorted before calling the final quick sort, the changes did not stick and so the output was not fully sorted. Plus once I took whiteflags advice, it finally worked. Can you please explain why it had to be like this

Code:

return strcmp(*(const char **)a, *(const char **)b);

and why

Code:

return strcmp((const char *)a, (const char *)b);

is wrong. Maybe a picture would help illustrate your point better(no pun intended ).

That is weird. I used the comparison function in post 3 and it sorted it just fine.

I'm assuming that what your byteswap function does is tmp holds one byte of information from aa, bb transfer one byte to aa, and then tmp gives one byte of information to bb. This cycle repeats until each byte has been swapped correct?