JS: problem sorting an array of objects

[Peter Kahrel]

Strange things happen when I try to sort an array of two-item objects on both properties. I'll explain below.

Peter

[Peter Kahrel]

I don't understand what's going on while sorting an array of two-place objects. Take this script:

obj = [
    {prefix: 'c', num: 'b'},
    {prefix: 'b', num: 'c'},
    {prefix: 'c', num: 'c'},
    {prefix: 'a', num: 'c'},
    {prefix: 'b', num: 'b'},
    {prefix: 'c', num: 'a'},
    {prefix: 'a', num: 'a'},
    {prefix: 'b', num: 'a'},
    {prefix: 'a', num: 'b'}
    ];
obj = obj.sort (objSort_1)
// obj = obj.sort (objSort_2)
for (i in obj) {
    $.writeln (obj.prefix + "-" + obj.num)
}
//------------------------------------------------
function objSort_1 (a, b){
    return a.prefix > b.prefix
}
function objSort_2 (a, b){
    return (a.prefix == b.prefix) && (a.num > b.num)
}

With obj = obj.sort (objSort_2) disabled, it sorts the array as expected only on the first property:

a-c

a-a

a-b

b-b

b-c

b-a

c-a

c-c

c-b

With obj = obj.sort (objSort_2) enabled, I would have expected the following:

a-a

a-b

a-c

b-a

b-b

b-c

c-a

c-b

c-c

but that doesn't happen: instead, I get this:

a-a

a-b

b-a

b-b

b-c

c-a

c-b

c-c

a-c

with a-c out of place at the end of the sorted list. Now when I add somewhere in the middle of the array an object with another letter as the first propert, e.g. {prefix: 'q', num: 'x'}, I get this output:

a-a

a-b

b-a

b-b

b-c

c-a

c-b

c-c

q-x

a-c

with a-c still out of place at the end of the sorted list. But when I add an item that should come at the beginning of the list, such as {prefix: '1', num: 'x'}, then I get this output:

a-a

a-b

a-c

b-a

b-b

b-c

c-a

c-b

c-c

1-x

with that added array item at the end of the list (where it doesn't belong: it should be at the beginning), but at least a-c is in the correct place.

Does anyone have an idea what's going on/wrong here?

Thanks,

Peter

[Marc Autret]

Hi Peter,

A compare function used in Array.sort should always return signed numbers (booleans cannot define a total order).

Here are the expected return values of such comparison:

a < b    -->   ret < 0
a == b   -->   ret = 0
a > b    -->   ret > 0

Both your objSort_1 and objSort_2 functions return booleans—which are coerced to 1 (true) or 0 (false)—so your functions never assert:

a < b

Now, objSort_1 seems to work, by chance, because your a==b and a > b assertions are consistant although you have not a total order. In fact, objSort_1 makes no distinction between a < b and a==b, but you don't see that issue because your set does not seem to contain identical items.

objSort_2 is more problematic because (a.prefix == b.prefix) && (a.num > b.num) takes no decision when a.prefix != b.prefix —which often happens, though!

Anyway, you have to provide a full comparison:

function objSort_3(a, b)
    {
    var ax = a.prefix,
        bx = b.prefix,
        ay = a.num,
        by = b.num;
    return ( (ax > bx) - (ax < bx) ) ||
           ( (ay > by) - (ay < by) );
    }

Note that objSort_3 always returns signed numbers (-1, 0, or +1) because any M < N (boolean) is coerced to a number thanks to the subtraction operator.

For example, if ax > bx, then (ax > bx) - (ax < bx) evaluates to +1 (TRUE - FALSE).

Also, in the case where ax == bx, the previous expression evaluates to 0 (FALSE - FALSE), so the second part (below the || operator) is evaluated.

@+

Marc

[-hans-]

Hi,

a month ago I was grabbing my head to do this 'relative' sort to a array of arrays (<-length may not be equal) .

Now, with your input, this seems (!!!) to work:

array = [[4,3,2,1], [1,2,3], [1,3,2,4], [5,8,9,7,6,4,8]];
    array.sort(function(a,b){
        aLength = a.length;
                bLength = b.length;
minLength = Math.min(aLength, bLength);
        myString = '';
        for(var tl = 0; tl < minLength; tl++){
            var tmpString = '' + ((a[tl] > b[tl]) - (a[tl] < b[tl]))
            if (tl != minLength -1){or = '||'}else{or = ''}
            myString = myString + tmpString + or
                        }
                    return eval(myString);
                    }
                )

Great!!

But could you show me a way without using 'string' and eval¿

Looking forward 😉

Hans-Gerd Claßen

[Marc Autret]

Hi Hans,

-hans- wrote:

[…]

But could you show me a way without using 'string' and eval¿

Try this:

array = [[4,3,2,1], [1,2,3], [1,3,2,4], [5,8,9,7,6,4,8], [4,3,2,1,12] ];
array.sort( function fnComp(a,b){
    var aLength = a.length,
        bLength = b.length,
        minLength = Math.min(aLength, bLength),
        i, ai, bi;
    for( i=0 ; i < minLength ; ++i )
        {
        ai = a;
        bi = b;
        if( ai != bi ) return ai-bi;
        }
    return aLength - bLength;
    });
alert( array.join('\r') );
/*
=>    1,2,3
    1,3,2,4
    4,3,2,1
    4,3,2,1,12
    5,8,9,7,6,4,8
*/

Now I have a "killer trick" for you in the case the compared arrays only contains positive integers in the range [0..65535]:

array = [[4,3,2,1], [1,2,3], [1,3,2,4], [5,8,9,7,6,4,8], [4,3,2,1,12] ];
var fChr = String.fromCharCode;
array.sort( function(a,b){
    var sa = fChr.apply(null, a),
        sb = fChr.apply(null, b);
    return (sa > sb) - (sa < sb);
    });
alert( array.join('\r') );

@+

Marc

[Marc Autret]

Last little note. If your code is very performance-sensitive, the following pattern:

+(a > b) || -(a < b)

is usually faster than:

(a > b) - (a < b)

(This slight improvement may matter in huge sorting processes…)

@+

Marc

[-hans-]

Hi marc,

first: sorry for hijacking this thread!

Your answers are more then I hoped for Never mentioned to give several returns in one sort ...

Have to sleep about it and test tomorrow ...

Hans-Gerd Claßen

[-hans-]

Hello Marc,

thx for your input

Haven't used call or apply until now, even forgot how to use ... your  'killer trick' and this explanation gave me a good restart.

I've changed         if( ai != bi ) return ai-bi;

to

if( ai != bi ){ if (ai < bi) return -1}else{return 1}

So I can  use it with arrays of strings too. Hope it's still correct JS 😉

Thx for sharing your time and knowledge!

Hans-Gerd Claßen

[Jongware]

Hans-Gerd, add

return 0;

at the end for *full* compliance. 🙂

[Peter Kahrel]

Marc,

Thanks very much for your explanation. I must confess I still don't understand some things, possibly because I don't think you're entirely correct when you say " In fact, objSort_1 makes no distinction between a < b and a==b, but you don't see that issue because your set does not seem to contain identical items." When I duplicate the object, objSort_1 continues to work properly:

obj = [
    {prefix: 'c', num: 'b'},
    {prefix: 'b', num: 'c'},
    {prefix: 'c', num: 'c'},
    {prefix: 'a', num: 'c'},
    {prefix: 'b', num: 'b'},
    {prefix: 'c', num: 'a'},
    {prefix: 'a', num: 'a'},
    {prefix: 'b', num: 'a'},
    {prefix: 'a', num: 'b'},
    {prefix: 'c', num: 'b'},
    {prefix: 'b', num: 'c'},
    {prefix: 'c', num: 'c'},
    {prefix: 'a', num: 'c'},
    {prefix: 'b', num: 'b'},
    {prefix: 'c', num: 'a'},
    {prefix: 'a', num: 'a'},
    {prefix: 'b', num: 'a'},
    {prefix: 'a', num: 'b'}
    ];
obj = obj.sort (objSort_1)
for (i in obj) {
    $.writeln (obj.prefix + "-" + obj.num);
}
function objSort_1 (a, b){
    return a.prefix > b.prefix;
}

grouping together all prefixes (a's, b's, and c's together). Duplication seems not the problem. Another thing is that "objSort_1 makes no distinction between a < b and a==b" appears not to be a problem. Take the following:

a = [3, 1, 345, 22, 3, 1, 345, 22, 8, 1]
a.sort ( function (a,b) { return Number (a) > Number (b)} )

which produces the correct result. I don't think it's necessary to distinguish a < b and a==b: if a==b or a > b, nothing happens. I could include a==b by saying a >=b, but that seems to be doing unnecessary work in that numbers are exchanged when they're equal. But maybe I've never properly understood sorting!

I can follow your reasoning at your objSort_3, but I'm not sure I understand why it is the case, nor why objSort_1 and objSort2 in tandem don't work. But the fact is that your function works and mine don't! More coffee and brain gymnastics required.

Thanks,

Peter

[Peter Kahrel]

Marc,

These two together work:

function objSort_1 (a, b){
    return a.prefix > b.prefix
}
function objSort_2 (a, b){
    if (a.prefix == b.prefix)
        return a.num > b.num
    return 1;  // or return true
}

But I still need two functions as opposed to your one. Predictably, your approach is the quicker one: when I duplicate obj untill I have about 550 elements, your method is almost twice as quick.

Thanks for the exposé!

Peter

[Marc Autret]

Hi again Peter,

• As the ECMAScript specification (see ECMA-262 §15.4.4.11) makes no assumption  about the inner implementation of Array.sort, it is possible that ExtendScript uses a comparison algorithm (e.g. a "quick sort") so that a simple "X < Y" predicate still works. [AFAIK several ExtendScript components are based on the C++ Boost library, which sounds to provide the quick sort algorithm… Maybe this is the reason.]

• However, we are not supposed to know that and it is not a good thing to teach that. Indeed, as clearly stated by the ECMA spec, "If comparefn is not undefined, it should be a function that accepts two arguments x and y and returns a negative value if x < y, zero if x = y, or a positive value if x > y." Portable JS code should always satisfies this principle—even though we come across many many examples on the Web that violate that rule and use boolean returns, typically: function(x, y){ return x > y; }

I consider such code defective and dangerous anyway. Who knows how ExtendScript will evolve 😉

• Now, you're right that it wasn't entirely correct to say "In fact, objSort_1 makes no distinction between a < b and a==b, but you don't see that issue because your set does not seem to contain identical items." Only the first part of my statement is correct! What remains true is that "objSort_1 makes no distinction between a < b and a==b" You can easily check this:

function objSort_1 (a, b){ return a.prefix > b.prefix }
var X = {prefix:'a'};
var Y = {prefix:'b'};
alert( objSort_1(X, Y) ); // => false
alert( objSort_1(X, X) ); // => false

which shows that a < b and a==b leads to the same result (false). Therefore, objSort_1 makes no distinction between these two cases.

By chance this doesn't impact the resulting sort even with identical items in the set, due to the specific way ExtendScript implements this feature. But you should be aware that this is just a "lucky accident."

@+

Marc

[Peter Kahrel]

Thanks, Marc. I should clearly change some habits!

Peter