I don't actually need to code this anywhere. I just was thinking about how an algorithm to sort a circular list of unit vectors to be in a clockwise order would work.

Conditions

After sorting, it doesn't matter what unit vector is first in the list as long as each adjacent unit vector in the list is clockwise to the last without any other unit vector between them

The list is circular, so the first vector in the list follows the last vector.

My own restriction here, but no trig functions allowed (Eg no atan2, atan ect) Use dot products or cross products instead

I have already come up with an algorithm that kinda looks like a bubble sort but has the draw back of being O(n^2) complexity. Any O(n log n) solutions?

Edit:

Just after posting I realized that this could be solved pretty trivially by using any sort function with simple comparison function that checks the sign of the x component and sorts on the y. I guess I could also add the restriction that they aren't unit vectors and you aren't allowed to normalize them to make the problem more difficult again.

The solution, with unit vectors, is as simple as making a sort function

unitVectors.sort((a, b) => {
    if (a.y > 0.0f) {
        if (b.y > 0.0f) {
            return b.x - a.x;
        } else {
            return -1;
        }
    } else if (a.y == 0.0) {
       if (a.x > 0) {
           return a.x - b.x;
       } else {
            if (b.y > 0.0f) {
                return 1;
            } else if (b.y == 0.0f) {
                return b.x - a.x;
            } else {
                return -1;
            }
       }
    } else {
       if (b.y < 0.0f) {
           return a.x - b.x;
       } else {
           return 1;
       }
    }
});

Not a very elegant solution and it assumes the vectors are unit vectors, but it gets the job done. I'm still curious if there is a method that can sort vectors without trig or without normalizing them.

bool compare(a,b)
{
return a.x*b.y + a.y*b.x < 0
}

a is less than b, if dot(a, perpendicular(b)) < 0

EDIT:

Uh... assuming a number line that wraps around (you dont have an absolute ordering in such a space)

First youd use this to split the space in two along a unit vector of your choice, then sort those using the same function, then join the halves.