hur.st's bl.aagh

BSD, Ruby, Rust, Rambling

pqsort

Fast partial quicksort

[c]

pqsort is the sorting library I wrote for Newzbin's custom search engine - it's a lightly modified quicksort capable of partitioning and sorting only part of a list.

Quicksort lends itself very well to this kind of use due to how it works - it naturally partitions the list based on a pivot, and so it's trivial to simply ignore any pivot side which cannot contain the desired results.

#include <stdio.h>
#include "pqsort.h"

static inline int IntCmp(const int a, const int b) {
    return (a - b);
}

define_pqsort(my_int, int, IntCmp);

#define DUMP()  printf("{ "); \
    for (int i = 0; i < nvalues; i++)  \
        printf("%d, ", values[i]); \
    printf("}\n");

int main(void) {
    int values[] = { 42, 98, 56, 23, 45, 63, 56, 80, 102, 2 };
    int nvalues = sizeof(values) / sizeof(values[0]);

    // partition the list in two
    my_int_pqsort(values, nvalues, 5, 0);
    DUMP(); // => { 23, 2, 42, 45, 56, 80, 102, 98, 63, 56, }

    // sort the first half
    my_int_pqsort(values, nvalues, 0, 5);
    DUMP(); // => { 2, 23, 42, 45, 56, 102, 98, 63, 80, 56, }

    // sort the rest
    my_int_pqsort(values + 5, nvalues - 5, 0, nvalues);
    DUMP(); // => { 2, 23, 42, 45, 56, 56, 63, 80, 98, 102, }

    return 0;
}