Namespaces
Variants
Views
Actions

Difference between revisions of "c/algorithm/qsort"

From cppreference.com
< c‎ | algorithm
(damage control for qsort_s)
m (fmt. IMO, eventually the whole site including C pages should be formatted uniformly.)
 
(35 intermediate revisions by 16 users not shown)
Line 2: Line 2:
 
{{c/algorithm/navbar}}
 
{{c/algorithm/navbar}}
 
{{dcl begin}}
 
{{dcl begin}}
−
{{dcl header | stdlib.h}}
+
{{dcl header|stdlib.h}}
−
{{dcl |
+
{{dcl|num=1|
−
void qsort( void *ptr, size_t count, size_t size,
+
void qsort( void* ptr, size_t count, size_t size,
−
             int (*comp)(const void *, const void *) );
+
             int (*comp)(const void*, const void*) );
 
}}
 
}}
−
{{dcl | since=c11 |
+
{{dcl|num =2|since=c11|
−
errno_t qsort_s( void *ptr, rsize_t count, rsize_t size,
+
errno_t qsort_s( void* ptr, rsize_t count, rsize_t size,
−
                 int (*comp)(const void *, const void *, void *),
+
                 int (*comp)(const void*, const void*, void*),
−
                 void *context );
+
                 void* context );
 
}}
 
}}
 
{{dcl end}}
 
{{dcl end}}
  
−
@1@ Sorts the given array pointed to by {{tt|ptr}} in ascending order. The array contains {{tt|count}} elements of {{tt|size}} bytes. Function pointed to by {{tt|comp}} is used for object comparison.  
+
@1@ Sorts the given array pointed to by {{c|ptr}} in ascending order. The array contains {{c|count}} elements of {{c|size}} bytes. Function pointed to by {{c|comp}} is used for object comparison.
−
@2@ Same as {{v|1}}, except that the additional context parameter {{tt|context}} is passed to {{tt|comp}} and that that the following errors are detected at runtime and call the currently installed [[c/error/set_constraint_handler_s|constraint handler]] function:
+
@2@ Same as {{v|1}}, except that the additional context parameter {{c|context}} is passed to {{c|comp}} and that the following errors are detected at runtime and call the currently installed [[c/error/set_constraint_handler_s|constraint handler]] function:
−
:* {{tt|count}} or {{tt|size}} is greater than {{lc|RSIZE_MAX}}
+
:* {{c|count}} or {{c|size}} is greater than {{lc|RSIZE_MAX}}
−
:* {{tt|ptr}} or {{tt|compar}} is a null pointer (unless {{tt|count}} is zero)
+
:* {{c|ptr}} or {{c|comp}} is a null pointer (unless {{c|count}} is zero)
−
:As all bounds-checked functions, {{tt|qsort_s}} is only guaranteed to be available if {{c|__STDC_LIB_EXT1__}} is defined by the implementation and if the user defines {{c|__STDC_WANT_LIB_EXT1__}} to the integer constant {{c|1}} before including {{tt|stdlib.h}}.
+
:{{c/ext1 availability|qsort_s}}
  
−
If {{tt|comp}} indicates two elements as equivalent, their order in the resulting sorted array is undefined.
+
If {{c|comp}} indicates two elements as equivalent, their order in the resulting sorted array is unspecified.
  
 
===Parameters===
 
===Parameters===
 
{{par begin}}
 
{{par begin}}
−
{{par | ptr | pointer to the array to sort}}
+
{{par|ptr|pointer to the array to sort}}
−
{{par | count | number of element in the array}}
+
{{par|count|number of elements in the array}}
−
{{par | size | size of each element in the array in bytes}}
+
{{par|size|size of each element in the array in bytes}}
−
{{par ccmp | comp }}
+
{{par ccmp|comp}}
−
{{par | context | additional information (e.g., collating sequence), passed to {{tt|comp}} as the third argument}}
+
{{par|context|additional information (e.g., collating sequence), passed to {{c|comp}} as the third argument}}
 
{{par end}}
 
{{par end}}
  
Line 36: Line 36:
  
 
===Notes===
 
===Notes===
 +
Despite the name, neither C nor POSIX standards require this function to be implemented using [[enwiki:Quicksort|quicksort]] or make any complexity or stability guarantees.
 +
 
Unlike other bounds-checked functions, {{tt|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 {{lc|bsearch_s}}).
 
Unlike other bounds-checked functions, {{tt|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 {{lc|bsearch_s}}).
  
−
Until {{tt|qsort_s}}, users of {{tt|qsort}} often used global variables to pass additional context to the comparison function.
+
The implementation of {{tt|qsort_s}} in the [https://learn.microsoft.com/en-us/cpp/c-runtime-library/reference/qsort-s Windows CRT] is incompatible with the C standard. The Microsoft's version
 +
is declared as:
 +
{{c multi|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 {{c|context}} is passed first.
  
 
===Example===
 
===Example===
 
{{example
 
{{example
−
| The following code sorts an array of integers using {{tt|qsort()}}
+
|code=
−
| code=
+
#include <limits.h>
 
#include <stdio.h>
 
#include <stdio.h>
 
#include <stdlib.h>
 
#include <stdlib.h>
Line 55: Line 61:
 
     if (arg1 > arg2) return 1;
 
     if (arg1 > arg2) return 1;
 
     return 0;
 
     return 0;
 +
 +
    // return (arg1 > arg2) - (arg1 < arg2); // possible shortcut
 +
 +
    // return arg1 - arg2; // erroneous shortcut: undefined behavior in case of
 +
                          // integer overflow, such as with INT_MIN here
 
}
 
}
 
   
 
   
 
int main(void)
 
int main(void)
 
{
 
{
−
    int i;
+
     int ints[] = {-2, 99, 0, -743, 2, INT_MIN, 4};
−
     int ints[] = { -2, 99, 0, -743, 2, 3, 4 };
+
 
     int size = sizeof ints / sizeof *ints;
 
     int size = sizeof ints / sizeof *ints;
 
   
 
   
 
     qsort(ints, size, sizeof(int), compare_ints);
 
     qsort(ints, size, sizeof(int), compare_ints);
 
   
 
   
−
     for (i = 0; i < size; i++) {
+
     for (int i = 0; i < size; i++)
 
         printf("%d ", ints[i]);
 
         printf("%d ", ints[i]);
−
    }
 
  
 
     printf("\n");
 
     printf("\n");
−
 
−
    return EXIT_SUCCESS;
 
 
}
 
}
−
| output=
+
|output=
−
-743 -2 0 2 3 4 99
+
-2147483648 -743 -2 0 2 4 99
 
}}
 
}}
  
 
===References===
 
===References===
 +
{{ref std c23}}
 +
{{ref std|section=7.22.5.2|title=The qsort function|p=TBD}}
 +
{{ref std|section=K.3.6.3.2|title=The qsort_s function|p=TBD}}
 +
{{ref std end}}
 +
{{ref std c17}}
 +
{{ref std|section=7.22.5.2|title=The qsort function|p=258-259}}
 +
{{ref std|section=K.3.6.3.2|title=The qsort_s function|p=442-443}}
 +
{{ref std end}}
 
{{ref std c11}}
 
{{ref std c11}}
−
{{ref std | section=7.22.5.2 | title=The qsort function | p=355-356}}
+
{{ref std|section=7.22.5.2|title=The qsort function|p=355-356}}
−
{{ref std | section=K.3.6.3.2 | title=The qsort_s function | p=609}}
+
{{ref std|section=K.3.6.3.2|title=The qsort_s function|p=609}}
 +
{{ref std end}}
 
{{ref std c99}}
 
{{ref std c99}}
−
{{ref std | section=7.20.5.2 | title=The qsort function | p=319}}
+
{{ref std|section=7.20.5.2|title=The qsort function|p=319}}
 +
{{ref std end}}
 
{{ref std c89}}
 
{{ref std c89}}
−
{{ref std | section=4.10.5.2 | title=The qsort function}}
+
{{ref std|section=4.10.5.2|title=The qsort function}}
 
{{ref std end}}
 
{{ref std end}}
  
 
===See also===
 
===See also===
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc inc | c/algorithm/dsc bsearch}}
+
{{dsc inc|c/algorithm/dsc bsearch}}
−
{{dsc see cpp | cpp/algorithm/qsort}}
+
{{dsc see cpp|cpp/algorithm/qsort}}
 
{{dsc end}}
 
{{dsc end}}
  
−
[[ar:c/algorithm/qsort]]
+
{{langlinks|ar|cs|de|es|fr|it|ja|ko|pl|pt|ru|tr|zh}}
−
[[cs:c/algorithm/qsort]]
+
−
[[de:c/algorithm/qsort]]
+
−
[[es:c/algorithm/qsort]]
+
−
[[fr:c/algorithm/qsort]]
+
−
[[it:c/algorithm/qsort]]
+
−
[[ja:c/algorithm/qsort]]
+
−
[[ko:c/algorithm/qsort]]
+
−
[[pl:c/algorithm/qsort]]
+
−
[[pt:c/algorithm/qsort]]
+
−
[[ru:c/algorithm/qsort]]
+
−
[[tr:c/algorithm/qsort]]
+
−
[[zh:c/algorithm/qsort]]
+

Latest revision as of 03:19, 22 January 2024

 
C
 
Algorithms
qsortqsort_s
(C11)
(C11)
 
Defined in header <stdlib.h>
void qsort( void* ptr, size_t count, size_t size,
            int (*comp)(const void*, const void*) );
 (1)
errno_t qsort_s( void* ptr, rsize_t count, rsize_t size,

                 int (*comp)(const void*, const void*, void*),

                 void* context );
 (2) (since C11)
1) Sorts the given array pointed to by ptr in ascending order. The array contains count elements of size bytes. Function pointed to by comp is used for object comparison.
2) Same as (1), except that the additional context parameter context is passed to comp and that the following errors are detected at runtime and call the currently installed constraint handler function:
  • count or size is greater than RSIZE_MAX
  • ptr or comp is a null pointer (unless count is zero)
As with all bounds-checked functions, qsort_s is only guaranteed to be available if __STDC_LIB_EXT1__ is defined by the implementation and if the user defines __STDC_WANT_LIB_EXT1__ to the integer constant 1 before including <stdlib.h>.

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

Contents

[edit] Parameters

ptr - pointer to the array to sort
count - number of elements in the array
size - size of each element in the array in bytes
comp - comparison function which returns ​a negative integer value if the first argument is less than the second, a positive integer value if the first argument is greater than the second and zero if the arguments are equivalent.

The signature of the comparison function should be equivalent to the following:

 int cmp(const void *a, const void *b);

The function must not modify the objects passed to it and must return consistent results when called for the same objects, regardless of their positions in the array.

​

context - additional information (e.g., collating sequence), passed to comp as the third argument

[edit] Return value

1) (none)
2) zero on success, non-zero if a runtime constraints violation was detected

[edit] 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).

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.

[edit] Example

Run this code
#include <limits.h>
#include <stdio.h>
#include <stdlib.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: undefined behavior in case of
                           // integer overflow, such as with INT_MIN here
}
 
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");
}

Output: 

-2147483648 -743 -2 0 2 4 99

[edit] References

  • C23 standard (ISO/IEC 9899:2024):
  • 7.22.5.2 The qsort function (p: TBD)
  • K.3.6.3.2 The qsort_s function (p: TBD)
  • C17 standard (ISO/IEC 9899:2018):
  • 7.22.5.2 The qsort function (p: 258-259)
  • K.3.6.3.2 The qsort_s function (p: 442-443)
  • C11 standard (ISO/IEC 9899:2011):
  • 7.22.5.2 The qsort function (p: 355-356)
  • K.3.6.3.2 The qsort_s function (p: 609)
  • C99 standard (ISO/IEC 9899:1999):
  • 7.20.5.2 The qsort function (p: 319)
  • C89/C90 standard (ISO/IEC 9899:1990):
  • 4.10.5.2 The qsort function

[edit] See also

(C11)
 searches an array for an element of unspecified type
(function) [edit]
C++ documentation for qsort
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=c/algorithm/qsort&oldid=168864"