Why is there a 0 floating point in my Quicksort algorithm list and how to include a NaN into my Quicksort algorithm?

Question

The following is my code:

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

#define INFINITY std::numeric_limits<float>::infinity()
#define NEGINFINITY -std::numeric_limits<float>::infinity()

int floatcomp(const void* elem1, const void* elem2)
{
    if (*(const float*)elem1 < *(const float*)elem2)
        return -1;
    return *(const float*)elem1 > *(const float*)elem2;
}

int main()
{
    float array[10] = {INFINITY, 3.5f, 144.4f, NAN, 12.4f, NEGINFINITY, 1.4f, -0.0f, 5.9f};
    int i;

    for (i = 0; i < 10; i++)
        printf("%f\n", array[i]);
    printf("\n");

    qsort(array, 10, sizeof(float), floatcomp);

    for (i = 0; i < 10; i++)
        printf("%f\n", array[i]);

    return 0;
}

The quicksort algorithm sorts the numbers entered in the correct order however, there is a 0.00000 always present in the list.

Also while adding the NaN to the array, the NaN is not sorted properly as it should be and I'm not able to correctly add in two different mantissa's for the NaN into my code as a string at the top.

Your comparator doesn't handle NaN correctly -- all comparisons against NaN return false, which causes your comparator to return 0 whenever either of the arguments is NaN. That's not a valid, since if a and b are different non-NaN values, then your comparator will say that a == NaN == b, but either a < b or a > b. — Paul Hankin, Mar 10 '17 at 15:43
You're going to have to sort NaN manually by checking for it with std::isnan and having it float to either the beginning or end based on this. — Donnie, Mar 10 '17 at 16:18

Mike Nakis · Answer 1 · 2017-03-10T19:01:57.087

7

To answer why there is a zero always included, that's because you are declaring an array of 10 elements, but you initialize it with only 9, so the 10th is zero.

As for the NaN, you should explain precisely what your definition of sorting a NaN "properly" is, and how the result differs from what you expected.

edited Mar 10 '17 at 19:01

answered Mar 10 '17 at 15:33

Mike Nakis

56,297
11
110
142

Basically, when I define NaN into a string i make and enter NaN into the array, the program when built and run does not sort NaN as it sorts the other strings of INFINITY and MINUS INFINITY. NaN is sorted randomly in the middle of the array – pollo Mar 10 '17 at 15:40
I tried using both signalling NaNs and Quiet NaNs however with both it gives me an error – pollo Mar 10 '17 at 15:51
2

The 10th value is not garbage, it is guaranteed to be `0`. If you have an array with a smaller initializer list, all other values are initialized to `0`. – mch Mar 10 '17 at 16:27

Malcolm McLean · Answer 2 · 2017-03-10T17:13:02.353

3

Using the normal operator rules for comparing doubles, sorting a list containing Nans is technically undefined behaviour as a < b and b < a may not be consistent. So you have to detect Nan and make it either the highest or lowest value explicitly.

int myisnan(float x)
{
   return (x == x) ? 0 : 1;
}

int floatcomp(const void* elem1, const void* elem2)
{
    int nan1= myisnan( *(const float *) elem1);
    int nan2 = myisnan( *(const float *) elem2);

     if(nan1 && nan2)
        return 0;
     if(nan1 && !nan2)
        return -1;
     if(!nan1 && nan2)
        return 1;
    if (*(const float*)elem1 < *(const float*)elem2)
        return -1;
    return *(const float*)elem1 > *(const float*)elem2;
 }

Use a "my" function to prevent name clashes with other isnan() functions which may or may not have been defined. nans do not equal each other, all operations with them return NaN or false.

edited Mar 10 '17 at 17:13

answered Mar 10 '17 at 15:43

Malcolm McLean

6,258
1
17
18

I just tried doing this but I'm getting error, could you try showing it to me, thanks. – pollo Mar 10 '17 at 15:45
1

`myisnan` has the results the wrong way round -- x==x means x isn't a nan. But this function is already defined in cmath. – Paul Hankin Mar 10 '17 at 16:07
Fixed. Unfortunately some people are still using old compilers. – Malcolm McLean Mar 10 '17 at 16:17
Defining your own `isnan` function isn't advised, see [this answer](http://stackoverflow.com/a/33924955/5987) which is for C but applies to C++ too. Use [`std::isnan`](http://en.cppreference.com/w/cpp/numeric/math/isnan) instead. – Mark Ransom Mar 10 '17 at 16:50
I know. It's a mess. But rather than give a magical isnan() which might not be defined, I thought it better to write the function and at the same time explain how operations on NaNs cause sorts to fail. – Malcolm McLean Mar 10 '17 at 16:53
can you tell me how to include this code into my algorithm please? I can't get it to work – pollo Mar 10 '17 at 16:58
There was a missing semicolon. Replace your old floatcomp with the new one, and try sorting an array including NaNs, which you can generate via sqrt(-1); – Malcolm McLean Mar 10 '17 at 17:15
thanks, that worked. The last problem I am encountering is adding two different types of NaNs, one being the Signalling NaN and the other the Quiet Nan – pollo Mar 10 '17 at 17:59
well, plus one for answering the part that I didn't. – Mike Nakis Mar 10 '17 at 19:05
@pollo you need to be more specific about your remaining problem. As far as anybody is concerned, all NaNs are equivalent and should sort together in a random order. – Mark Ransom Mar 11 '17 at 04:05
what i mean by different NaNs is that i want to put quiet nan and signaling Nan :https://medium.com/engineering-housing/nan-is-not-equal-to-nan-771321379694#.lxo4yhvog – pollo Mar 11 '17 at 11:33
A signalling Nan will signal and abort behaviour the moment you try to use it. Usually the includes sorts. I'm not sure if there is a way (other than bitwise comparison) of achieving what you want. – Malcolm McLean Mar 11 '17 at 14:03

Why is there a 0 floating point in my Quicksort algorithm list and how to include a NaN into my Quicksort algorithm?

2 Answers2

Linked