Possible bug in STD C quicksort. Am i missing something ?

Question

xorshift init: 7731

A: 2064221648 1036493097 633233112 583013546 721278080 -1646392714 -829660162 478401127

E: 583013546 633233112 721278080 1036493097 2064221648 -1646392714 -829660162 478401127

Expected: -1646392714 -829660162 478401127 583013546 633233112 721278080 1036493097 2064221648

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

#define debug (0 || (sz < 50))

int cmpfunc(const void* a, const void* b)
{
    int x = *(int*)a;
    int y = *(int*)b;
    return x-y;
}

unsigned int xorshift32(unsigned int x)
{
    /* Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs" */
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

int
main()
{
    #define sz 8

    int* a = (int*)malloc(4*sz);

    srand(time(NULL));
    unsigned int init = rand();   printf("xorshift init: %lld\n",init);

    int z=0;
    for(int i = sz-1; i>=0;i+=0)
    {
        a[z] = xorshift32(init) % 0xD0000000U; init = a[z];

        z++;
        i--;
    }
    if(debug)
    {
        printf("A:\n");
        for(int i = 0; i<sz;i++)
        {
            printf("%11d\n", a[i]);
        }printf("\n");
    }

    qsort(a,sz,4,cmpfunc);

    printf("E: \n");
    if(debug)
    {
        for(int i = 0; i<sz;i++)
        {
            printf("%11d\n", a[i]);
        }printf("\n");
    }
}

win7_x64 | gcc.exe (x86_64-posix-seh-rev0, Built by MinGW-W64 project) 8.1.0

No optimization or other kind of flags used.

`"xorshift init: %lld\n"` (note `%LLD`) -> `"xorshift init: %11d\n"` — HolyBlackCat, Dec 17 '18 at 19:08
You'll have an easier time debugging things if you use the same random seed every time (rather than `time(NULL)`). — Tom, Dec 17 '18 at 19:10
On the whole, if you have some code you wrote, and a standard library function used by millions of programs over many years, and the combination of the two produces odd results, you're usually much better advised to look for the bug in your own code. — rici, Dec 17 '18 at 19:19
`for(int i = sz-1; i>=0;i+=0) { a[z] = ...; z++; i--; }` This looks suspicious, why not a simple `for(int z = 0; z < sz; z++) { a[z] = ...; }`? — Bob__, Dec 17 '18 at 19:23

Antti Haapala -- Слава Україні · Accepted Answer · 2018-12-17T19:19:23.930

3

Compiled with

gcc sort.c -Wall -Wextra

There was one error about not matching conversion specifier (unsigned int requires %u but you had %lld - possibly typo for %11d but even then it were wrong.

Running, I get sometimes correct output, sometimes not. So I compiled with -fsanitize=undefined, and

sort.c:11:13: runtime error: signed integer overflow: 
    1288106901 - -1003011281 cannot be represented in type 'int'
E: 
  290879035
  591885416
  767444883
 1288106901
 1955087149
-1509681722
-1289472872
-1003011281

I.e. your smart code wasn't too smart there. The correct way to return a value from the comparison function would be

return x < y ? -1 : x > y ? 1 : 0;

or

return (x > y) - (x < y);

as suggested by HolyBlackCat

edited Dec 17 '18 at 19:19

answered Dec 17 '18 at 19:11

Antti Haapala -- Слава Україні

129,958
22
279
321

@HolyBlackCat hmm indeed, godbolt shows that mine causes a branch be generated with GCC while yours doesn't. – Antti Haapala -- Слава Україні Dec 17 '18 at 19:18
Or just `return x < y ? -1 : x > y;`. `... ? 1 : 0` is almost always redundant. – rici Dec 17 '18 at 19:21
@rici indeed, I just made it more explicit. Still, GCC will generate that one branch for that too :/ – Antti Haapala -- Слава Україні Dec 17 '18 at 19:22
@antti: unless you ask to optimise or something radical like that. https://gcc.godbolt.org/z/YiDRha – rici Dec 17 '18 at 19:27
Well, that's wild. It's branch free in clang and in gcc6.3. Maybe they know something we don't know. – rici Dec 17 '18 at 19:34
Actually the compare code was taken from here: [link](https://stackoverflow.com/questions/27284185) which i thought was solid. I guess i have to learn more about gcc's debuging features before rushing to post. – FranG Dec 17 '18 at 22:47
@frantzelasg: thanks for the report.That answer should have been flagged as problematic; I added a comment. But it does underline the fact that free advice is worth what you pay for it. – rici Dec 18 '18 at 02:03
@FrantzelasG you've fallen victim to "million flies" here :D Had you read all answers carefully, you'd seen [the one by AnT](https://stackoverflow.com/a/27284248/918959). – Antti Haapala -- Слава Україні Dec 18 '18 at 04:06
Indeed. Now that i know what i'm looking for i can appreciate the value of less voted answers. Also [cpp](https://en.cppreference.com/w/cpp/algorithm/qsort) includes // return arg1 - arg2; // erroneous shortcut (fails if INT_MIN is present) and the alt. idea is pretty simple we need to extract 2bits of info and map it to 1,0,-1 (x>y) - (x – FranG Dec 18 '18 at 06:39
1

@FrantzelasG btw, the correct page would be https://en.cppreference.com/w/c/algorithm/qsort ;) It too has that info. – Antti Haapala -- Слава Україні Dec 18 '18 at 06:42
@FrantzelasG you might consider accepting my answer ;) – Antti Haapala -- Слава Україні Dec 18 '18 at 07:32

Possible bug in STD C quicksort. Am i missing something ?

1 Answers1

Linked