[llvm-bugs] [Bug 26269] New: Quick sort return false result

[via llvm-bugs]

https://llvm.org/bugs/show_bug.cgi?id=26269

            Bug ID: 26269
           Summary: Quick sort return false result
           Product: libc++
           Version: 3.8
          Hardware: Macintosh
                OS: MacOS X
            Status: NEW
          Severity: normal
          Priority: P
         Component: All Bugs
          Assignee: unassignedclangbugs at nondot.org
          Reporter: tegusi at live.cn
                CC: llvm-bugs at lists.llvm.org, mclow.lists at gmail.com
    Classification: Unclassified

I wrote a code like that:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define x first
#define y second
#define mk make_pair
using namespace std;
const int SIZE = 1010;
const double Eps = 1e-6;
typedef pair<double, double>II;
II orig;
II data[SIZE];
int N;
void Read() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        scanf("%lf%lf", &data[i].x, &data[i].y);
}
II operator -(II A, II B){return mk(A.x - B.x, A.y - B.y);}
II operator +(II A, II B){return mk(A.x + B.x, A.y + B.y);}
II operator *(II A, double k){return mk(A.x * k, A.y * k);}
double calc_length(II A){return sqrt(A.x * A.x + A.y * A.y);}
double pd(double x) {
    if (x > Eps)        return 1;
    if (x < -Eps)       return -1;
    return 0;
}
int Get_quadrant(II A) {
    if (pd(A.x) > 0 && pd(A.y) >= 0)    return 1;   //[0, 90)
    if (pd(A.x) <= 0 && pd(A.y) > 0)    return 2;   //[90, 180)
    if (pd(A.x) < 0 && pd(A.y) <= 0)    return 3;   //[180, 270)
    if (pd(A.x) >= 0 && pd(A.y) < 0)    return 4;   //[270, 360)
    return 0;
}
double cross(II p0, II p1, II p2) {
    return (p1.x - p0.x) * (p2.y - p0.y) -
    (p2.x - p0.x) * (p1.y - p0.y);
}
bool polar_angle_cmp(II A, II B) {
    if (pd(A.x - orig.x) == 0 && pd(A.y - orig.y) == 0)     return true;
    if (pd(B.x - orig.x) == 0 && pd(B.y - orig.y) == 0)     return false;

    int t1 = Get_quadrant(A - orig);
    int t2 = Get_quadrant(B - orig);
    if (t1 != t2)       return t1 < t2;

    double sum = cross(orig, A, B);
    if (pd(sum) != 0)       return (pd(sum) > 0);
    return calc_length(A - orig) < calc_length(B - orig);
}
bool cmp2(const int &A, const int &B) {
    return A <= B;
}
int main() {
    //freopen("t.in", "r", stdin);
    //freopen("t.out", "w", stdout);
    Read();
    orig.x = orig.y = 0;
    sort(data + 1, data + 1 + N, polar_angle_cmp);

    for (int i = 1; i <= N; i++)
        printf("%lf %lf\n", data[i].x, data[i].y);

    return 0;
}

My input is as followed:

21
6 3
8 4
0 3
0 6
0 0
-1 3
-3 1
0 0
-2 0
0 0
-3 -2
-1 -3
0 -3
2 -3
0 0
3 -3
1 0
0 0
0 0
5 2
4 2

My ideal output should be:

0.000000 0.000000
0.000000 0.000000
0.000000 0.000000
0.000000 0.000000
0.000000 0.000000
0.000000 0.000000
1.000000 0.000000
5.000000 2.000000
4.000000 2.000000
6.000000 3.000000
8.000000 4.000000
0.000000 3.000000
0.000000 6.000000
-1.000000 3.000000
-3.000000 1.000000
-2.000000 0.000000
-3.000000 -2.000000
-1.000000 -3.000000
0.000000 -3.000000
2.000000 -3.000000
3.000000 -3.000000

1.000000 0.000000 is after 0.000000 0.000000,
however, I got this when I compiled with libc++:

0.000000 0.000000
0.000000 0.000000
0.000000 0.000000
0.000000 0.000000
0.000000 0.000000
1.000000 0.000000 //strange line
0.000000 0.000000 
5.000000 2.000000
4.000000 2.000000
6.000000 3.000000
8.000000 4.000000
0.000000 3.000000
0.000000 6.000000
-1.000000 3.000000
-3.000000 1.000000
-2.000000 0.000000
-3.000000 -2.000000
-1.000000 -3.000000
0.000000 -3.000000
2.000000 -3.000000
3.000000 -3.000000

Could you please fix it?

Thank you.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20160123/2ea6c919/attachment-0001.html>