YouTipC Function Qsort
# C Library Function - qsort()
The `qsort()` function is a built-in utility provided by the C Standard Library to sort arrays of any data type. Defined in the `` header, it implements a highly efficient sorting algorithm (typically Quicksort, though the exact implementation details are compiler-dependent).
With an average time complexity of **O(n log n)**, `qsort()` is a versatile tool because it uses generic pointers (`void *`) and a user-defined comparison function to handle integers, floats, strings, or custom structures.
---
## Syntax and Declaration
To use `qsort()`, you must include the `` header:
```c
#include
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void *));
```
### Parameters
* **`base`**: A pointer to the first element of the array to be sorted. It is of type `void *`, allowing any array type to be passed.
* **`nitems`**: The number of elements in the array (of type `size_t`).
* **`size`**: The size in bytes of each element in the array (of type `size_t`). This is typically determined using the `sizeof` operator.
* **`compar`**: A pointer to a comparison function that you define. `qsort` repeatedly calls this function to compare two elements.
### The Comparison Function
The comparison function must match the following signature:
```c
int compar(const void *a, const void *b);
```
It must cast the `const void *` arguments back to the actual data type being sorted and return an integer based on the comparison:
| Return Value | Meaning |
| :--- | :--- |
| **Negative integer (`< 0`)** | The element pointed to by `a` should go before the element pointed to by `b` (Ascending order: `a < b`). |
| **Zero (`0`)** | The elements pointed to by `a` and `b` are equivalent. Their relative order is undefined. |
| **Positive integer (`> 0`)** | The element pointed to by `a` should go after the element pointed to by `b` (Ascending order: `a > b`). |
---
## Return Value
The `qsort()` function does not return any value (`void`). It sorts the array **in-place**, modifying the original array passed to it.
---
## Code Examples
### Example 1: Sorting an Array of Integers (Ascending Order)
The following example demonstrates how to sort an array of five integers in ascending order.
```c
#include
#include
// An array of 5 integers
int values[] = { 88, 56, 100, 2, 25 };
// Comparison function to sort integers in ascending order
int cmpfunc (const void * a, const void * b)
{
// Cast the void pointers to int pointers and dereference them
return ( *(int*)a - *(int*)b );
}
int main()
{
int n;
// Print the array before sorting
printf("List before sorting:\n");
for( n = 0 ; n < 5; n++ ) {
printf("%d ", values);
}
// Sort the array using qsort
qsort(values, 5, sizeof(int), cmpfunc);
// Print the array after sorting
printf("\nList after sorting:\n");
for( n = 0 ; n < 5; n++ ) {
printf("%d ", values);
}
printf("\n");
return 0;
}
```
#### Output
```text
List before sorting:
88 56 100 2 25
List after sorting:
2 25 56 88 100
```
---
### Example 2: Sorting an Array of Strings (Alphabetical Order)
You can also use `qsort()` to sort strings. Since strings are arrays of characters (or pointers to characters), we can use the standard library function `strcmp` inside our comparison function.
```c
#include
#include
#include
// Comparison function for strings
int compare_strings(const void *a, const void *b)
{
// Since we are sorting an array of string pointers (char *),
// the arguments passed to this function are pointers to those pointers (char **).
return strcmp(*(const char **)a, *(const char **)b);
}
int main()
{
const char *arr[] = {"Cherry", "Apple", "Banana", "Date"};
int n = sizeof(arr) / sizeof(arr);
printf("Before sorting:\n");
for (int i = 0; i < n; i++) {
printf("%s ", arr);
}
qsort(arr, n, sizeof(char *), compare_strings);
printf("\nAfter sorting:\n");
for (int i = 0; i < n; i++) {
printf("%s ", arr);
}
printf("\n");
return 0;
}
```
#### Output
```text
Before sorting:
Cherry Apple Banana Date
After sorting:
Apple Banana Cherry Date
```
---
## Key Considerations & Best Practices
### 1. Integer Overflow in Comparison Functions
In Example 1, the subtraction `*(int*)a - *(int*)b` is used for simplicity. However, this can cause **integer overflow** if the array contains extreme values (e.g., a very large positive number and a very large negative number).
To write a safer comparison function, use explicit conditional checks:
```c
int safe_cmp(const void *a, const void *b) {
int val_a = *(const int *)a;
int val_b = *(const int *)b;
if (val_a < val_b) return -1;
if (val_a > val_b) return 1;
return 0;
}
```
### 2. Sorting in Descending Order
To sort an array in descending order, simply reverse the logic of your comparison function. For example:
```c
int compare_descending(const void *a, const void *b) {
return ( *(int*)b - *(int*)a ); // b - a instead of a - b
}
```
### 3. Unstable Sorting
`qsort()` is **not guaranteed to be a stable sort**. If two elements are equal according to the comparison function, their relative order in the sorted array is not preserved and can change. If stability is required, you must incorporate the elements' original indices into the comparison logic.