An example of an inline qsort

This is an example C program demonstrating an inline qsort. The qsort comes from Michael Tokarev's inline qsort. The code for the qsort is also available at this site.

#include <stdio.h>
#include <string.h>
#include "qsort.h"

const char * array[] = {
    "eggs",
    "bacon",
    "cheese",
    "mushrooms",
    "spinach",
    "potatoes",
    "spaghetti",
    "fruit",
    "lemons",
};

static inline int compare (const void * a, const void * b)
{
    /* The pointers point to offsets into "array", so we need to
       dereference them to get at the strings. */
    return (strcmp (*(const char **) a, *(const char **) b) < 0);
}

#define n_array (sizeof(array)/sizeof(const char *))

int main ()
{
    int i;
    QSORT (const char *, array, n_array, compare);
    for (i = 0; i < n_array; i++) {
        printf ("%d: %s.\n", i, array[i]);
    }
    return 0;
}

(download)

The output of the example looks like this:

0: bacon.
1: cheese.
2: eggs.
3: fruit.
4: lemons.
5: mushrooms.
6: potatoes.
7: spaghetti.
8: spinach.

A test using an adapted version of the code found at Performance of qsort vs std::sort?:

#include <iostream>
#include <vector>
#include <algorithm>

#include <cstdlib>
#include <ctime>
#include <cstdio>
#include "qsort.h"

const size_t LARGE_SIZE = 10000000;

struct rnd {
    int operator()() {
        return rand() % LARGE_SIZE;
    }
};

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

#define comp2(a,b) (*( int* )a < *( int* )b)

int ary[LARGE_SIZE];
int ary_copy[LARGE_SIZE];
int ary_mysort[LARGE_SIZE];

int main()
{
    // generate random data
    std::generate( ary, ary + LARGE_SIZE, rnd() );
    std::copy( ary, ary + LARGE_SIZE, ary_copy );
    std::copy( ary, ary + LARGE_SIZE, ary_mysort );
    // get time
    std::time_t start = std::clock();
    // perform quick sort C using function pointer
    std::qsort( ary, LARGE_SIZE, sizeof( int ), comp );
    std::cout << "C quick-sort time elapsed: " << static_cast<double>( clock() - start ) / CLOCKS_PER_SEC << "\n";
    // get time again
    start = std::clock(); 
#define MYSORT(array,c) {                                       \
        int n = sizeof (array)/sizeof (array[0]);               \
        QSORT(typeof (array[0]),array,n,c);                     \
    }
    MYSORT(ary_mysort, comp2);
    std::cout << "Inline C quick-sort time elapsed: " << static_cast<double>( clock() - start ) / CLOCKS_PER_SEC << "\n";
    // get time again
    start = std::clock();
    // perform quick sort C++ using function object
    std::sort( ary_copy, ary_copy + LARGE_SIZE );
    std::cout << "C++ quick-sort time elapsed: " << static_cast<double>( clock() - start ) / CLOCKS_PER_SEC << "\n";
}

(download)

gives a performance

C quick-sort time elapsed: 3.24219
Inline C quick-sort time elapsed: 1.48438
C++ quick-sort time elapsed: 1.3125

It is slightly slower than the C++ library's standard sort but about twice as fast as the plain-C qsort. It may be speculated that the algorithm used in the C++ library is slightly more advanced than the one used in qsort.h.


The code from stackoverflow.com is used under a Creative commons licence. qsort.h is used under the GNU Lesser General Public License. Please see the file for details. For comments, questions, and corrections, please email Ben Bullock (benkasminbullock@gmail.com) or use the discussion group at Google Groups. News about the site. / Privacy / Disclaimer