qsort in C


Reading time: 30 minutes | Coding time: 10 minutes

qsort in C is an in-built function for sorting array of any data types including structs. It, internally, uses a variant o Quick Sort and performs well in real data and should be used. It is a part of the stdlib.h header file in C. We have demonstrated how to use qsort with different data types like int, strings and struct in C.

To use it, include the stdlib.h header file as:

#include <stdlib.h>

Following it, to use qsort, use the following syntax:

qsort( array, number_of_elements, size_of_each_element, comparison_function)

where:

  • array is an array of any data type
  • number_of_elements is the number of elements in the array or the number of elements (from beginning) that you want to sort
  • size_of_each_element is the size of each element/ size of the data type
  • comparison_function is the custom comparison function for the data type

The syntax of the comparison function is as follows:

int compare (const void * a, const void * b)
{
  // do compare a and b
  // return -1 (or any negative number) if a < b
  // return 0 if a == b
  // return 1 (or any positive number) if a > b
}

We will understand this in detail with examples.

qsort in C for Integers

In this example, we will explore how we can use qsort for an array of integers in C.

Consider the following example:

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

int compare (const void * a, const void * b)
{
  int data1 = *(int *)a, data2 = *(int *)b;
  if(data1 < data2) // a < b
    return -1;
  else if(data1 == data2) // a == b
    return 0;
  else 
    return 1;  // a > b
}

int main ()
{
  int i = 0, numbers = 5;
  int data[] = {3, 40, 2, 1, 10};
  qsort (data, numbers, sizeof(int), compare);
  for (i=0; i < numbers; i++)
     printf ("%d ", data[i]);
  return 0;
}

Output:

1 2 3 10 40

An alternative approach is to modify the comparison function. The idea is that if we return the difference of the two integers, it will work as the absolute value does not matter. Only negative, positive and zero holds significance.

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

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

int main ()
{
  int i = 0, numbers = 5;
  int data[] = {3, 40, 2, 1, 10};
  qsort (data, numbers, sizeof(int), compare);
  for (i=0; i < numbers; i++)
     printf ("%d ", data[i]);
  return 0;
}

Output:

1 2 3 10 40

qsort in C for Strings

To use qsort with array of strings, we need to customize the compare function. This can be done using strcmp function to compare strings in C. Note strings are array of characters in C.

Consider this C code example:

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

int compare(const void *a, const void *b) 
{ 
    const char **str_a = (const char **)a;
    const char **str_b = (const char **)b;
    return strcmp(*str_a, *str_b);
} 

int main ()
{
    int i = 0, numbers = 5;
    char* array[] = {"opengenus", "github", "opensource", "cs", "internship"};
    qsort (array, numbers, sizeof(char*), compare);
    for (i=0; i < numbers; i++)
         printf ("%s \n", array[i]);          
    return 0;
}

Output:

cs 
github 
internship 
opengenus 
opensource 

qsort in C for struct

In this example, we will create a structure with two fields data1 and data2 as follows:

typedef struct 
{
    int data1;
    int data2;
} data;

To use qsort with this struct, we need a custom comparison function as follows:

int compare (const void * a, const void * b)
{
  data *data_1 = (data *)a;
  data *data_2 = (data *)b;
  return ( data_1->data1 - data_2->data1 );
}

Consider this example where we sort struct based on the first field that is data1:

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

typedef struct 
{
    int data1;
    int data2;
} data;

int compare (const void * a, const void * b)
{
  data *data_1 = (data *)a;
  data *data_2 = (data *)b;
  return ( data_1->data1 - data_2->data1 );
}

int main ()
{
    int i = 0, numbers = 5;
    data array[numbers];
    
    printf("Before sorting\n");
    for(i=0; i < numbers; i++)
    { 
        array[i].data1 = rand()%5;
        array[i].data2 = rand()%5; 
        printf ("data1 = %d data2 = %d\n", array[i].data1, array[i].data2);           
    }
    printf("After sorting\n");
    qsort (array, numbers, sizeof(data), compare);
    for (i=0; i < numbers; i++)
         printf ("data1 = %d data2 = %d\n", array[i].data1, array[i].data2);          
    return 0;
}

Output:

Before sorting
data1 = 3 data2 = 1
data1 = 2 data2 = 0
data1 = 3 data2 = 0
data1 = 1 data2 = 2
data1 = 4 data2 = 1
After sorting
data1 = 1 data2 = 2
data1 = 2 data2 = 0
data1 = 3 data2 = 1
data1 = 3 data2 = 0
data1 = 4 data2 = 1

Now, we will modify the comparison function so that the comparison is based on the first data that is data1 and if data1 is same, then, it goes to compare data2. Consider this comparison function:

int compare (const void * a, const void * b)
{
  data *data_1 = (data *)a;
  data *data_2 = (data *)b;
  if( data_1->data1 == data_2->data1)
  {
      return data_1->data2 - data_2->data2;
  }
  else if( data_1->data1 < data_2->data1)
    return -1;
  else
    return 1;
}

Consider this C code and focus on the comparison function:

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

typedef struct 
{
    int data1;
    int data2;
} data;

int compare (const void * a, const void * b)
{
  data *data_1 = (data *)a;
  data *data_2 = (data *)b;
  if( data_1->data1 == data_2->data1)
  {
      return data_1->data2 - data_2->data2;
  }
  else if( data_1->data1 < data_2->data1)
    return -1;
  else
    return 1;
}

int main ()
{
    int i = 0, numbers = 5;
    data array[numbers];
    
    printf("Before sorting\n");
    for(i=0; i < numbers; i++)
    { 
        array[i].data1 = rand()%5;
        array[i].data2 = rand()%5; 
        printf ("data1 = %d data2 = %d\n", array[i].data1, array[i].data2);           
    }
    printf("After sorting\n");
    int n;
    qsort (array, numbers, sizeof(data), compare);
    for (i=0; i < numbers; i++)
         printf ("data1 = %d data2 = %d\n", array[i].data1, array[i].data2);          
    return 0;
}

Consider this output:

Before sorting
data1 = 3 data2 = 1
data1 = 2 data2 = 0
data1 = 3 data2 = 0
data1 = 1 data2 = 2
data1 = 4 data2 = 1
After sorting
data1 = 1 data2 = 2
data1 = 2 data2 = 0
data1 = 3 data2 = 0
data1 = 3 data2 = 1
data1 = 4 data2 = 1

With this, you have complete knowledge of using qsort() in C with any array of data.