qsort (C)

• Complexity of Quicksort
• Complexity of sorting algorithms
• Simulation of Quicksort

You can find an implementation of quicksort here.

#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)