# C quicksort

I have written quicksort in the past mostly to learn how it works and to play with optimization. (Because most of the time... I just want to call the system sort.)

Sometimes, knowing how this works helps with other problems, like sorting vectors, where we can do better than a full comparison on each step.

All of the other sorts I have written have been in a language that has at least some generic support. This time, though, it is in C, using void *'s.

And it wasn't that bad. This code is not fit for a system library, or anything like that, but it was fun(?) to write and test.

The code stops quicksorting when the subfile gets shorter than 10 lines, and it uses a median-of-three pivot selection.

In the testing I did, an iterative version of this algorithm showed no improvement.

```void q4(void   *array,
size_t  length,
size_t  size,
int(*compare)(const void *, const void *))
{
if(length < 10) {
for(void *a = array + size; a < array + size*length; a += size) {
for(void *b = a;
b > array && compare(b, b-size) < 0;
b -= size) {
swap(b, b-size, size);
}
}
} else {
void *middle = array + (length / 2) * size;
void *outer = array + (length-1) * size;
void *pivot = array + (length-2) * size;
swap(middle, pivot, size);
median_of_three(array, pivot, outer, size, compare);

void *a = array - size;
void * b = pivot;

while(a < b) {
a += size;
for(;a < b && compare(a, pivot) < 0; a += size){}
b -= size;
for(;a < b && compare(pivot, b) < 0; b -= size){}
if(a < b) {
swap(a, b, size);
}
}

assert(compare(a, pivot) >= 0);
swap(a, pivot, size);
q4(array, (a-array)/size, size, compare);
q4(a + size, length - (a-array)/size-1, size, compare);
}
}
```

The median of three code leaves the smallest value at a, the middle at b, and the largest at c.

```void median_of_three(void *a, void*b, void*c, size_t size,
int (*compare)(const void*, const void*)) {
if(compare(a, b) > 0) { swap(a, b, size); }
if(compare(b, c) > 0) {
swap(b, c, size);
if(compare(a, b) > 0) { swap(a, b, size); }
}
assert(compare(a, b) <= 0);
assert(compare(b, c) <= 0);
}
```

And the swap is not efficiency minded...

```void swap(char *a, char *b, int size) {
while(size > 0) {
char t = *a;
*a = *b;
*b = t;
++a, ++b, --size;
}
}
```

In most cases, the system qsort on my machine crushes this code.