Sorting function for lists required

[torsten]

Dear XVR crew,

have you ever thought about a quicksort function for arrays? I have an application sorting a few hundred (and maybe much more in the future) object positions by distance in every frame. Implementing this in a scripting language is not only cumbersome but very inefficient. A built-in function would be much more peformant.

I'd suggest the following signature:
function asort(thearray, comp)
comp would be the name of the user-defined comparison function as a string. It would work like this:

var positions= {...};  // Unsorted positions

function compareDistance(a, b)
{
    return Modulus(a) > Modulus(b);
}

asort(positions, "compareDistance");
outputln("Sorted array = ", positions);

What do you think?

Torsten

[sankazim]

Dear Torsten,

you can try this small but flexible qsort.

Usage:

#include "qsort.s3d"

class AbsComparer
{
    less(x,y);
};

function AbsComparer::less(x,y)
{
    return abs(x) < abs(y);
}

function mycmp(x,y)
{
    return abs(x) < abs(y);
}

function OnInit()
{
    var a = {1,2,10,30,40,50,-20,-30};
    Outputln(qsort(a));
    Outputln(qsort(a,"mycmp"));
    Outputln(qsort(a,AbsComparer()));
     
    a = [1,2,10,30,40,50,-20,-30];
    Outputln(qsort(a));
    Outputln(qsort(a,"mycmp"));
    Outputln(qsort(a,AbsComparer()));
   
    Outputln(qsort("alsostring"));
}


Emanuele

[torsten]

Dear Emanuele,

this helps for my application, sorting only about 200 position values and probably for many others. I appreciate your help.

The performance is not satisfying for more complex applications. I have just benchmarked sorting 1000 position vectors and got the following results:

Code:

-----------------------------------------------------------------------
 Function                    Count    Time (msec)     %     Func+Child
-----------------------------------------------------------------------
 _OUTPUTLN                       2          98.69  44.3          98.69
 _SCENEBEGIN                   449          20.43   9.2          20.43
 DRAWGRID                      449          19.50   8.8          45.87
 _GLVERTEX                   19756          17.68   7.9          17.68
 QSORT                        1321          16.56   7.4           2.21
 _CALLBACK                   10372          14.64   6.6          22.74
 COMPAREVECTOR3              10372           8.10   3.6           8.10

Doing a litte math, you find that you can sort an array of 1000 positions 60 times per second. That would eat up the whole simulation time for an interactive application. So my argument stands: We need this to be integrated as a native function (in C++) to be efficient enough for large arrays at high framerates.

Again many thanks for your help,

Torsten