qsort (C)

You can find an implementation of quicksort here.

qsort.c

#include <stdlib.h>
/* stdlib has quicksort implemented as a generic function. The prototype is : */
/*  void qsort(void *base, size_t nmemb, size_t size,
            int(*compar)(const void *, const void *));                       */

/* Because qsort is generic, we need to inform her of what kind of data we */
/* manipulate. Moreover, we need to pass as a last parameter, a function that */
/* how the comparisson of the elements to be sorted is going to be done. We pass */
/* the function by its pointer. A function is located in memory and as result */
/* can be pointed. So, a function pointer is nothing more that a pointer to first */
/* block of memory the function is located to.*/

/**
 * Defines how the comparisson is going to be done.
 * @param first_arg The first element.
 * @param second_arg The second element.
 * @return -1 if the first is less than the 2nd,
 * 0 is they are equal, 1 if else.
 */
int int_sorter( const void *first_arg, const void *second_arg )
{
    int first = *(int*)first_arg;
    int second = *(int*)second_arg;
    if ( first < second )
    {
        return -1;
    }
    else if ( first == second )
    {
        return 0;
    }
    else
    {
        return 1;
    }
}

/**
 * Defines how the comparison is going to be done.
 * Warning: This works with signed numbers. With unsigned numbers,
 * if their difference is greater than 2^31, then the result will 
 * be incorrect, since the function returns an int.
 * @param a The first element.
 * @param b The second element.
 * @return negative number if the first is less than the 2nd,
 * 0 is they are equal, positive number if else.
 */
int compar(const void* a, const void* b)
{
    return *(int*)a - *(int*)b;
}

int main(void)
{
    int i, array[10];
    /* Fill array */
    for (i = 0 ; i < 10 ; i++)
        array[ i ] = 10 - i;
    
    /* The array to be sorted, how many elements
     * the size of every element and the function
     * to compare.                              */
    qsort(array, 10 , sizeof( int ), compar);
    /* qsort(array, 10 , sizeof( int ), int_sorter);*/
    for (i = 0 ; i < 10 ; i++)
        printf ( "%d\n" ,array[ i ]);
    
    return 0;
}

This code was developed by me, G. Samaras.

In order to sort strings, here is a code borrowed from another site.

/* "qsort" is declared in stdlib.h. */
#include <stdlib.h>
#include <stdio.h>
/* string.h declares "strcmp". */
#include <string.h>

/* "array" is an unsorted shopping list. */

const char * array[] = {
    "Samaras",
    "Philiopoulos",
    "Dimitriadis",
    "Vergis",
    "Manthos",
    "Tsafos"
};

/* n_array is the number of elements in the array. */

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

/* Compare the strings. */

static 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);
}

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

More on function pointers.
Have questions about this code? Comments? Did you find a bug? Let me know!😀
Page created by G. (George) Samaras (DIT)

3 thoughts on “qsort (C)

  1. I prefer the other comparison. qsort does not define the order in which it passes arguments to your function pointer, so using tricks like subtraction can lead to unexpected results.

  2. @whiteflags: Thank you for the comment! Can you please provide some code that demonstrates that? Or can you describe what can go wrong?🙂 If posting code in a comment does not seem ok, sent me a pm at the forum!

  3. A member of C board forum commented something remarkable about the way compar function works:
    Actually, I wouldn’t.
    The quick and dirty hack of returning (left – right) returns the wrong value in some cases. e.g. 2billion and -2billion.
    When you subtract you get 4billion which of course is not representable as a signed 32-bit int, and instead becomes negative, placing them in the wrong order.
    It can also fail for the same reason that abs(-2147483648) = -2147483648.

    There is a branchless way of comparing them, but that isn’t it. IIRC it’s this, not that I suggest using it as it’s clearly non-portable, relying on two-s complement representation etc:
    Code:
    return((unsigned(*a) ^ 0x80000000U) – (unsigned(*b) ^ 0x80000000U));

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s