Quicksort

Sorting is something most programs have to do on some occasion. Quicksort is accepted as the best in-practice general purpose sorting algorithm available today. Standard C offers a built in Quicksort under the function name qsort(), with the following prototype:

void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *));

Now while it may be built in, each C library implements it differently. Also, it's designed to work with any kind of type/structure, however one can generally optimize it a bit more for the kind that they're dealing with. Since sorting is important, and can take a while with many items, one generally wants their sorting to be optimized as much as possible.

I've looked at several implementations for various C libraries out there, however they all have one thing in common - messy. One I looked at didn't even implement Quicksort, but a Shakersort.

I'm wondering perhaps if some of the clever people who read this blog can come up with a clean but fast implementation.

To start off, here's a mostly unoptimized simple implementation of the standard qsort():

static void swap_internal(char *a, char *b, size_t size)
{
  if (a != b)
  {
    char t;
    while (size--)
    {
      t = *a;
      *a++ = *b;
      *b++ = t;
    }
  }
}

static void qsort_internal(char *begin, char *end, size_t size, int(*compar)(const void *, const void *))
{
  if (end > begin)
  {
    char *pivot = begin;
    char *l = begin + size, *r = end;

    while (l < r)
    {
      if (compar(l, pivot) <= 0)
      {
        l += size;
      }
      else
      {
        r -= size;
        swap_internal(l, r, size);
      }
    }
    l -= size;
    swap_internal(begin, l, size);
    qsort_internal(begin, l, size, compar);
    qsort_internal(r, end, size, compar);
  }
}

void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *))
{
  qsort_internal((char *)base, (char *)base+nmemb*size, size, compar);
}

Note, this implementation is ~40 lines and can be improved. It can be improved with a better pivot selection, removing the recursion, and throwing in an insertion sort for certain cases.

I'm challenging my readers to give me a good clean implementation, which is under 80 lines (bad indentation doesn't count, I'll be running submitted code through my formatter), compliant, and isn't a total wreck. Creating some helper functions to make it clearer is a good idea too. Almost every implementation I've seen makes use of gotos to all over the place, and has returns smack in the middle of the function.

It'd be nice to bring something so useful into the new millennium, instead of using messy or slow implementations from the 70s.

If I get some nice implementations in, I'll do another piece on how to optimize Quicksort for sorting certain types/structures.