Glibc: Using Qsort From Stdlib

Few years back I had to write a program in python as an assignment, which will generate one million random integers and will sort them without using any built in function. The logic was simple you divide the list into the smaller ones, and sort them simultaneously, then merge them together.

While working on that I looked into the python’s implementation of sort() function. Now in Python, the default sort() function implements timsort which is a hybrid sort. Timsort works phenomenally well on the list of one million integers. As it is implemented in C thus there is no “interpretation” involved when the sort function is called. This function just takes the input which is a iterable, and iterates over it, thus this is much faster than any other implementation of sort function written in python. Even java uses Timsort for objects and Dual-Pivot Quicksort for primitive data types.

Since then I wanted to see how sorting is implemented in standard c library. So I looked at the Glibc doc.

The prototype for qsort is there in stdlib.h and the prototype is void qsort (void *array, size_t count, size_t size, comparison_fn_t compare). The qsort function takes four arguments, a pointer to array, count of the elements in that array, each of which is of size size and the compare function. This function is called with two pointer arguments and should return an integer less than, equal to, or greater than zero corresponding to whether its first argument is considered less than, equal to, or greater than its second argument.

Following is the example to generate an array of random integers of whatever size user inputs and sort it using qsort().

#include<time.h>
#include<stdio.h>
#include<stdlib.h>

int compare_int (const void *a, const void *b)
{
  const int *da = (const int *) a;
  const int *db = (const int *) b;

  return (*da > *db) - (*da < *db); // return if a > b;
}


int main(int arg, char* args[]){

    int input = atoi(args[1]); // get the size of array.

    printf("%d, str: %d", arg, input);
    int *arr = malloc(input*sizeof(int)); // allocate memory for that array
    

    srand(time(NULL)); // set the seed for random generator.
    int min =0;
    int max = 100;
    

    printf("\nGenerating Random\n");
    printf("\n------------------------------------------------\n");


    for(int i;i <input; i++){
        arr[i] = min +(rand() % (max - min + 1)); //generate a new random int.
    }

    printf("\nSorting the list\n");
    printf("\n------------------------------------------------\n");

    qsort (arr, input, sizeof(int), compare_int); // sort the array.

    printf("\nSorting Done\n");

    for(int i=0; i<input; i++){
        printf("\n%d", arr[i]);
    }

    printf("\n------------------------------------------------\n");
    return 0;
}