quicksort algorithm issue

Unity Engine
1

Hi everybody;

For the last couple of weeks I’ve been working on a pathfinding script based on waypoints.
But I’ve found some problems when I get all the waypoints from the scene and trying to sort them.

Here is a portion of my code:

// taget to follow:
var target : Transform;

// store candidates to be evaluated:
var stack : Array = new Array();

// path needs to be found using waypoints:
var waypoints : Transform = GameObject.Find("Waypoints").transform;
            
// add all waypoints to the stack:
for (var node : Transform in waypoints) stack.Push(node);

// sort array of waypoints using quicksort algorithm
SortStack(0, stack.length - 1);

and here is the quicksort algorithm:

function Swap(a : float, b : float)
{
    var foo = stack[a];
    stack[a] = b;
    stack[b] = foo;
}

function Distance(foo : Transform)
{
    return Vector3.Distance(target.position, foo.position);
}

function Hoare(e : float, d : float)
{
    var x = stack[e];
    while(true)
    {
        while (Distance(stack[d--]) > Distance(x));
        while (Distance(stack[e++]) < Distance(x));
        if (e >= d) return d;
        Swap(e,d);
    }
}

function SortStack(e : float, d : float)
{
    if (e < d)
    {
        var hoare = Hoare(e,d);
        SortStack(e, hoare);
        SortStack(hoare+1, d);
    }
}

So when I execute the game, Unity stops working and pops up and error (asking me if I want to send Apple the message error and all this stuff).

I’m sure the problem is with the sorting algorithm because if I remove it, it works fine (with the array not being sorted, of course).

Maybe are those recursive calls at SortStack not supported by Unity? So maybe I should change the algorithm to Mergesort. Should I?

Thanks in advice

2

Can you log how many recursions happen? Although it doesn’t appear to be the case my guess would be there is a way you can get stuck calling SortStack.

If the editor crashes on me it’s always a stack overflow.

3
  1. Why are e and d floats and not int? array indices will NEVER be float nor do you have half-elements :wink:
  2. If you are that performance interested that you use “QuickSort” you should not use the Array class but class[ ]*arrays.
  3. Any reason you hate .Sort?
  4. Took me a while to spot that but the main problem is that your Hoare is just incorrect.
    You are missing core requirements for quick sort in there, like the d > e check within the loop that increments and decrements the indices. Doing the check afterwards is incorrect and like the cause for the problem here. As d > e is a requirement and fundamental condition and termination criteria for QuickSort, you can at worst reach the point where d will decrement until it hits -1 and throws an exception, or e increments until its equal to the array length and throws an exception, a thing that by design and definition of quicksort can not happen as the higher index can never be equal or smaller to the smaller index and vice versa (so the outcome of hoare always must be part of the interval [e,d], which your code does not guarantee correctly. You just return a completely incorrect value for the index when you detect that your while loops fucked up)

Here QuickSort Algorithm using Generics in C# 2.0 - CodeProject is an example of a working quicksort implementation that shows how quicksort is meant to look on the “find indices” function (Hoare)

I know thats not the point here but: You might potentially want to look into heap / priority queue / list instead of quicksort. That way you can safe the time of sorting and instead insert them in the correct order (by their distance) right from the start and whenever you take a point out for processing, these ADTs will auto update themself without any effort at all.
Also it does not require multiple evaluations of the same distance (which you should not do either by the way. If you decide to go with quicksort, I would recommend to store Distance(x) once before the loop and just use that stored value. It won’t change anyway. Actually I would store the distance(stack[e]) in x right from the start as you don’t use x for anything but distance x anyway

4

Thanks for the answers! So as dreamora said, I’ll try to implement priority_queues instead of sorting the vector. I owe you one guys!