CODEWITHSUNDEEP
javascriptgoogle-chromesorting
vicnoob
vicnoob

Reputation: 1183

Sort undefined value in javascript works incorrectly

I have an array of object like:

var arr = [{index: 1, key: undefined}, {index: 2, key: undefined},{index: 3, key: undefined},{index: 4, key: undefined},{index: 5, key: undefined},{index: 6, key: undefined},{index: 7, key: undefined},{index: 8, key: undefined},{index: 9, key: undefined},{index: 10, key: undefined},{index: 11, key: undefined},{index: 12, key: undefined},{index: 13, key: undefined},{index: 14, key: undefined},{index: 15, key: undefined},{index: 16, key: undefined},{index: 17, key: undefined},{index: 18, key: undefined},{index: 19, key: undefined} ]

I want to sort array arr by key - here is all undefined value. The return value should be the same as arr. But when i execute:

arr.sort(function(a,b){return a.key - b.key})

The result is not the same as i expected, the array order is changed. Any idea on this problem?

My result: https://i.sstatic.net/ksCQ5.jpg

Update: Tested with another array:

var b = [{index: 1, key: 10}, {index: 2, key: 10},{index: 3, key: 10},{index: 4, key: 10},{index: 5, key: 10},{index: 6, key: 10},{index: 7, key: 10},{index: 8, key: 10},{index: 9, key: 10},{index: 10, key: 10},{index: 11, key: 10},{index: 12, key: 10},{index: 13, key: 10},{index: 14, key: 10},{index: 15, key: 10},{index: 16, key: 10},{index: 17, key: 10},{index: 18, key: 10},{index: 19, key: 10} ]

Every key has same value, but when sort function is call: https://i.sstatic.net/Usar5.jpg

IE and Firefox is work OK, the problem happens in Chrome. I guess something go wrong with the case return 0.

Upvotes: 0

Views: 5966

Answers (3)

Carloluis
Carloluis

Reputation: 4320

The problem is related with the stability of algorithms used inside array.sort implementation which depends on the engine used to execute your javascript code.

Chrome uses Google’s V8 engine. V8's sort algorithm use a combination of insertion-sort and quick-sort. Check the actual implementation here.

Insertion-sort is used when the array is small (array.length <= 10), otherwise quick-sort is used. The second sorting algorithm is unstable, and don't provide any guarantee about preserving order of equivalent elements.

As conclusion, I include two tests (both using your initial comparison function). Chrome's results:

  • the first sort is performed on 10 elements array (therefore, original order is preserved)
  • the second sort is performed on your original array with 19 elements (in this case there is no certainty about keeping original order, and that's why the array order is changed)

const small = [
  {index: 1, key: undefined}, 
  {index: 2, key: undefined},
  {index: 3, key: undefined},
  {index: 4, key: undefined},
  {index: 5, key: undefined},
  {index: 6, key: undefined},
  {index: 7, key: undefined},
  {index: 8, key: undefined},
  {index: 9, key: undefined},
  {index: 10, key: undefined}
];

// stable sort
small.sort(function(a,b){return a.key - b.key});
console.log(small);

var arr = [
  ...small,
  {index: 11, key: undefined},
  {index: 12, key: undefined},
  {index: 13, key: undefined},
  {index: 14, key: undefined},
  {index: 15, key: undefined},
  {index: 16, key: undefined},
  {index: 17, key: undefined},
  {index: 18, key: undefined},
  {index: 19, key: undefined}
];

// unstable sort
arr.sort(function(a,b){return a.key - b.key});
console.log(arr);

Probably you need to implement a stable sorting algorithm to ensure your code will behave the same despite the environment in which will be executed. The most common stable algorithms are bubble-sort, insertion-sort and merge-sort.

Read more about stability in sorting algorithms

Check chromium bug: V8 doesn't stable sort

Javascript engines. More.

Upvotes: 2

roomcayz
roomcayz

Reputation: 2564

What you are trying to do is to subtract undefined from undefined, and the result is NaN.

NaN < 0
> false

NaN > 0
> false

NaN is not -1 neither is 1, and it is not greater nor lesser than 0, so it seems to be treated as 0.

I'm not sure if the above sentence is true.

According to MDN:

If compareFunction(a, b) returns 0, leave a and b unchanged with respect to each other, but sorted with respect to all different elements. Note: the ECMAscript standard does not guarantee this behaviour, and thus not all browsers (e.g. Mozilla versions dating back to at least 2003) respect this.

So I've tested this in Firefox and the order stay unchanged. But doing the same in Chrome reproduced your problem.

Upvotes: 1

Rohit Tirmanwar
Rohit Tirmanwar

Reputation: 159

Do the following....

arr.sort(function(a,b){return (!a || !b)? 0 : (a.key - b.key) })

Upvotes: 2

Related Questions