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
You'll have an easier time debugging things if you use the same random seed every time (rather than time(NULL)). — Tom
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
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__

Antti Haapala Antti Haapala · Accepted Answer · 2018-12-17T19:11:37

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

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

1 Answers