qsort 比较函数总是 return 非零值吗？

Question

qsort 和 bsearch 在 int 数组上的升序排序回调函数可能如下所示：

int ascending(const void *o1, const void *o2) {
    int a = *(const int *)o1;
    int b = *(const int *)o2;
    return a < b ? -1 : 1;
}

然而这个函数似乎违反了 C 标准中对 compar 函数的约束：

7.22.5.2 The qsort function

Synopsis
#include <stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));
Description
The qsort function sorts an array of nmemb objects, the initial element of which is pointed to by base. The size of each object is specified by size.

The contents of the array are sorted into ascending order according to a comparison function pointed to by compar, which is called with two arguments that point to the objects being compared. The function shall return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second.

If two elements compare as equal, their order in the resulting sorted array is unspecified.

这个比较函数可以吗还是会导致未定义的行为？

Answer 1

C 2018 7.22.5 4 说：

When the same objects (consisting of size bytes, irrespective of their current positions in the array) are passed more than once to the comparison function, the results shall be consistent with one another. That is, for qsort they shall define a total ordering on the array, and for bsearch the same object shall always compare the same way with the key.

A total order 要求 a = a。（从维基百科页面的定义中可以看出这一点：Connexity 说，对于任何 a 和 b，a ≤ b 或 b ≤ a。代入 a 对于 b 给出 a ≤ a 或 a ≤ a. 所以 a ≤ a. 那么反对称的条件满足：我们有 a ≤ a 并且 a ≤ a, 所以 a = a.)

Answer 2

至少在 bsearch 中使用这样的函数会导致未定义的行为。

这是一个演示程序。

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

int ascending(const void *o1, const void *o2) {
    int a = *(const int *)o1;
    int b = *(const int *)o2;
    return a < b ? -1 : 1;
}

int ascending1(const void *o1, const void *o2) {
    int a = *(const int *)o1;
    int b = *(const int *)o2;

    return ( b < a ) - ( a < b );
}

int main(void) 
{
    int a[] = { 2, 2, 1, 1, 0, 0 };
    const size_t N = sizeof( a ) / sizeof( *a );
    
    qsort( a, N, sizeof( int ), ascending );
    
    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );
    
    int key = 1;

    int *p = bsearch( &key, a, N, sizeof( int ), ascending );
    
    if ( p ) printf("*p = %d, p - a = %zu\n", *p, ( size_t )( p - a ) );
    else puts( "Oops!" );

    p = bsearch( &key, a, N, sizeof( int ), ascending1 );
    
    if ( p ) printf("*p = %d, p - a = %zu\n", *p, ( size_t )( p - a ) );
    else puts( "Oops!" );
    
    return 0;
}

程序输出为

0 0 1 1 2 2 
Oops!
*p = 1, p - a = 3

qsort 可以根据其内部实现工作。

但是无论如何你都有未定义的行为，因为比较函数不满足要求。

qsort 比较函数总是 return 非零值吗？

Can the qsort comparison function always return a non-zero value?

c

sorting

language-lawyer

qsort