Javascript array sort not working right when many equal elements

Question

I'm trying to sort an array with a custom comparer function.

The comparer function only cares about the order between two specific elements.

In the example below you'd expect 'a' to appear before 'b' after sorting, but it's not.

var ar = ["b", "c", "d", "a"];

ar.sort(function(x, y) {
  if (x == 'a' && y == 'b') { return -1; }
  if (x == 'b' && y == 'a') { return 1; }
  return 0; // only the order between 'a' and 'b' matters.
});

console.log(ar);

// ar is still ["b", "c", "d", "a"];

So why isn't 'a' before 'b'? Is there a workaround?

Ned Batchelder · Accepted Answer · 2012-07-19 01:32:33Z

4

Think about your comparator being called on the successive pairs of your list:

"b", "c" --> 0
"c", "d" --> 0
"d", "a" --> 0

Your comparator says all the pairs are equal, so the order doesn't need to be changed at all.

Since you don't care what order the other elements appear in (is this right?) then make your comparator say "a" is less than anything, and "b" is greater than anything:

ar.sort(function(x, y) {
  if (x == 'a' || y == "b") { return -1; }
  if (x == 'b' || y == 'a') { return 1; }
  return 0; // only the order between 'a' and 'b' matters.
});

answered Jul 19, 2012 at 1:32

Ned Batchelder

378k77 gold badges583 silver badges675 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Apoteks Salmiak Over a year ago

I did not care the order of other elements in the example. In the real scenario where this issue came up, there CAN be more than one pairings where the order matters.

Apoteks Salmiak Over a year ago

I was trying to z-sort sprites. When they are intersecting, I could determine which should be on top. If the sprites were not intersecting, I was returning 0 from the comparer.

Ariel · Accepted Answer · 2012-07-19 01:34:21Z

0

If 'a' = 'c', and 'b' = 'c' - which according to your function it is, then 'a' also equals 'b'.

answered Jul 19, 2012 at 1:34

Ariel

26.8k5 gold badges62 silver badges71 bronze badges

1 Comment

Apoteks Salmiak Over a year ago

Yeah that's what must be happening here.

Larry Battle · Accepted Answer · 2012-07-19 01:41:31Z

0

Think of the Array.prototype.sort function like this...

Array.prototype.sort = function( sortFunc ){
    if( typeof sortFunc !== "function" ){
        sortFunc = function(a,b){
            return a-b;
        }
    }
    var arr = [];
    for(var i = 0, len = arr.length; i <= len; i++ ){
        sortFunc( arr[i], arr[i+1] );
    }
    return arr;
}

As you can see Array.prototype.sort only supplies the sortFunc functions with elements that are only one unit apart.

So sortFunc( "b", "a" ) won't happen because their indexes are not 1 unit apart.

answered Jul 19, 2012 at 1:41

Larry Battle

9,1985 gold badges43 silver badges55 bronze badges

Collectives™ on Stack Overflow

Javascript array sort not working right when many equal elements

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related