Difference between revisions of "c/algorithm/qsort"

Revision as of 14:41, 21 January 2024

If comp indicates two elements as equivalent, their order in the resulting sorted array is unspecified.

Parameters

Return value

Notes

Despite the name, neither C nor POSIX standards require this function to be implemented using quicksort or make any complexity or stability guarantees.

Unlike other bounds-checked functions, qsort_s does not treat arrays of zero size as a runtime constraint violation and instead returns successfully without altering the array (the other function that accepts arrays of zero size is bsearch_s).

Until qsort_s, users of qsort often used global variables to pass additional context to the comparison function.

The implementation of qsort_s in the Windows CRT is incompatible with the C standard. The Microsoft's version is declared as: void qsort_s (void *base, size_t num, size_t width, int (*compare )(void *, const void *, const void *), void * context); It does not return a value, and the comparison function has a reversed parameter order with regard to the standard: the context is passed first.

Example

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
int compare_ints(const void* a, const void* b)
{
    int arg1 = *(const int*)a;
    int arg2 = *(const int*)b;
 
    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;
    return 0;
 
    // return (arg1 > arg2) - (arg1 < arg2); // possible shortcut
    // return arg1 - arg2; // erroneous shortcut (triggers undefined behavior in case of integer overflow)
}
 
int main(void)
{
    int ints[] = { -2, 99, 0, -743, 2, INT_MIN, 4 };
    int size = sizeof ints / sizeof *ints;
 
    qsort(ints, size, sizeof(int), compare_ints);
 
    for (int i = 0; i < size; i++) {
        printf("%d ", ints[i]);
    }
 
    printf("\n");
}

-2147483648 -743 -2 0 2 4 99

References

See also