diff options
Diffstat (limited to 'devdocs/c/algorithm%2Fqsort.html')
| -rw-r--r-- | devdocs/c/algorithm%2Fqsort.html | 85 |
1 files changed, 85 insertions, 0 deletions
diff --git a/devdocs/c/algorithm%2Fqsort.html b/devdocs/c/algorithm%2Fqsort.html new file mode 100644 index 00000000..f1006ea4 --- /dev/null +++ b/devdocs/c/algorithm%2Fqsort.html @@ -0,0 +1,85 @@ + <h1 id="firstHeading" class="firstHeading">qsort, qsort_s</h1> <table class="t-dcl-begin"> <tr class="t-dsc-header"> <th> Defined in header <code><stdlib.h></code> </th> <th> </th> <th> </th> </tr> <tr class="t-dcl"> <td> <pre data-language="c">void qsort( void *ptr, size_t count, size_t size, + int (*comp)(const void *, const void *) );</pre> +</td> <td> (1) </td> <td class="t-dcl-nopad"> </td> </tr> <tr class="t-dcl t-since-c11"> <td> <pre data-language="c">errno_t qsort_s( void *ptr, rsize_t count, rsize_t size, + int (*comp)(const void *, const void *, void *), + void *context );</pre> +</td> <td> (2) </td> <td> <span class="t-mark-rev t-since-c11">(since C11)</span> </td> </tr> </table> <div class="t-li1"> +<span class="t-li">1)</span> Sorts the given array pointed to by <code>ptr</code> in ascending order. The array contains <code>count</code> elements of <code>size</code> bytes. Function pointed to by <code>comp</code> is used for object comparison. </div> <div class="t-li1"> +<span class="t-li">2)</span> Same as <span class="t-v">(1)</span>, except that the additional context parameter <code>context</code> is passed to <code>comp</code> and that the following errors are detected at runtime and call the currently installed <a href="../error/set_constraint_handler_s" title="c/error/set constraint handler s">constraint handler</a> function: <dl> +<dd> +<ul> +<li> <code>count</code> or <code>size</code> is greater than <code>RSIZE_MAX</code> </li> +<li> <code>ptr</code> or <code>comp</code> is a null pointer (unless <code>count</code> is zero) </li> +</ul> </dd> +<dd>As with all bounds-checked functions, <code>qsort_s</code> only guaranteed to be available if <code>__STDC_LIB_EXT1__</code> is defined by the implementation and if the user defines <code>__STDC_WANT_LIB_EXT1__</code> to the integer constant <code>1</code> before including <a href="../program" title="c/program"><code><stdlib.h></code></a>.</dd> +</dl> +</div> <p>If <code>comp</code> indicates two elements as equivalent, their order in the resulting sorted array is unspecified.</p> +<h3 id="Parameters"> Parameters</h3> <table class="t-par-begin"> <tr class="t-par"> <td> ptr </td> <td> - </td> <td> pointer to the array to sort </td> +</tr> <tr class="t-par"> <td> count </td> <td> - </td> <td> number of elements in the array </td> +</tr> <tr class="t-par"> <td> size </td> <td> - </td> <td> size of each element in the array in bytes </td> +</tr> <tr class="t-par"> <td> comp </td> <td> - </td> <td> comparison function which returns a negative integer value if the first argument is <i>less</i> than the second, a positive integer value if the first argument is <i>greater</i> than the second and zero if the arguments are equivalent.<br> <p>The signature of the comparison function should be equivalent to the following:</p> +<p><span class="t-cc"> <span class="kw4">int</span> cmp<span class="br0">(</span><span class="kw4">const</span> <span class="kw4">void</span> <span class="sy2">*</span>a, <span class="kw4">const</span> <span class="kw4">void</span> <span class="sy2">*</span>b<span class="br0">)</span><span class="sy4">;</span></span></p> +<p>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.</p> +<p></p> +</td> +</tr> <tr class="t-par"> <td> context </td> <td> - </td> <td> additional information (e.g., collating sequence), passed to <code>comp</code> as the third argument </td> +</tr> +</table> <h3 id="Return_value"> Return value</h3> <div class="t-li1"> +<span class="t-li">1)</span> (none)</div> <div class="t-li1"> +<span class="t-li">2)</span> zero on success, non-zero if a runtime constraints violation was detected</div> <h3 id="Notes"> Notes</h3> <p>Despite the name, neither C nor POSIX standards require this function to be implemented using <a href="https://en.wikipedia.org/wiki/Quicksort" class="extiw" title="enwiki:Quicksort">quicksort</a> or make any complexity or stability guarantees.</p> +<p>Unlike other bounds-checked functions, <code>qsort_s</code> 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 <code>bsearch_s</code>).</p> +<p>Until <code>qsort_s</code>, users of <code>qsort</code> often used global variables to pass additional context to the comparison function.</p> +<h3 id="Example"> Example</h3> <div class="t-example"> <div class="c source-c"><pre data-language="c">#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 (fails if INT_MIN is present) +} + +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"); +}</pre></div> <p>Output:</p> +<div class="text source-text"><pre data-language="c">-2147483648 -743 -2 0 2 4 99</pre></div> </div> <h3 id="References"> References</h3> <ul> +<li> C17 standard (ISO/IEC 9899:2018): </li> +<ul> +<li> 7.22.5.2 The qsort function (p: 258-259) </li> +<li> K.3.6.3.2 The qsort_s function (p: 442-443) </li> +</ul> +<li> C11 standard (ISO/IEC 9899:2011): </li> +<ul> +<li> 7.22.5.2 The qsort function (p: 355-356) </li> +<li> K.3.6.3.2 The qsort_s function (p: 609) </li> +</ul> +<li> C99 standard (ISO/IEC 9899:1999): </li> +<ul><li> 7.20.5.2 The qsort function (p: 319) </li></ul> +<li> C89/C90 standard (ISO/IEC 9899:1990): </li> +<ul><li> 4.10.5.2 The qsort function </li></ul> +</ul> <h3 id="See_also"> See also</h3> <table class="t-dsc-begin"> <tr class="t-dsc"> <td> <div><a href="bsearch" title="c/algorithm/bsearch"> <span class="t-lines"><span>bsearch</span><span>bsearch_s</span></span></a></div> +<div><span class="t-lines"><span><span class="t-mark-rev t-since-c11">(C11)</span></span></span></div> </td> <td> searches an array for an element of unspecified type <br> <span class="t-mark">(function)</span> </td> +</tr> <tr class="t-dsc"> <td colspan="2"> <span><a href="https://en.cppreference.com/w/cpp/algorithm/qsort" title="cpp/algorithm/qsort">C++ documentation</a></span> for <code>qsort</code> </td> +</tr> </table> <div class="_attribution"> + <p class="_attribution-p"> + © cppreference.com<br>Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.<br> + <a href="https://en.cppreference.com/w/c/algorithm/qsort" class="_attribution-link">https://en.cppreference.com/w/c/algorithm/qsort</a> + </p> +</div> |