0

Quite a few months ago, I tried to find a way to place an element in the middle of an array of 3 items using the javascript sort function. It looked like there was no clever way of achieving that result.

However, I recently found a working solution to this problem. I then tried to generalize this solution to a bigger array of (5, 7, 9, ...) items. But, it seems to break when the size of the array exceeds 10 items.

Since I found the solution through trial and error rather than pure thinking, I hope someone is able to explain to me why everything seems to work fine until this seemingly arbitrary number.

Here is Codepen demo I created to illustrate the issue : https://codepen.io/TMLN/pen/PBoKgR?editors=0011

You can edit the line ReactDOM.render(<Example items={example1} />... and replace the prop example1 by example2, example3, ... You'll see that everything starts breaking from example5 but I really can't figure out why...

PS : this works on Chrome but for those using Edge, you might encounter a bug due to the way the browser handles the sort function.

Thomas Milan
  • 289
  • 1
  • 5
  • 14
  • 1
    `but for those using Edge`. Which nobody does on SO :D – Chris Jul 15 '18 at 20:40
  • please add some arrays and the wanted outcome as well. please add the code, you tried to the question, too. – Nina Scholz Jul 15 '18 at 20:40
  • 4
    Why use `sort` for this? If you just need to arbitrarily place an item in the middle of an array, that's what `splice` is for. – Jules Jul 15 '18 at 20:42
  • 1
    is it something like [this question](https://stackoverflow.com/questions/45325624/sort-an-array-with-item-closest-to-two-in-middle-and-other-extremes-on-other-sid), you want? – Nina Scholz Jul 15 '18 at 20:43
  • Using `sort` with a call to `indexOf` in its compare-callback is like giving your algorithm a *O(n²logn)* time complexity, while you can put an element in the middle of an array in *O(n)*. So yes, why do you insist on a really bad performing algorithm? – trincot Jul 15 '18 at 21:03

1 Answers1

2

Your sort callback function returns 0 when neither of the compared values is equal to the value to be moved. You probably intended to indicate with this zero that the relative position of a and b (the two compared values) should not change, but actually the zero means that the sort implementation should consider the two values equal, and so it is actually free to swap their positions. Only when the implementation is (what is called) stable can you be sure that the relative position of the two values will not change.

Others have found that in Chrome the sort function is not stable, which explains the erratic behaviour you notice. See this Q&A for the situation, with regard to a stable implementation, in different browsers.

To make it work on all JavaScript engines you should change your code, and return a non-zero value for all pairs you compare, based on the index they currently occupy.

Final note: using sort for this task is a bad choice: a good sorting algorithm has O(nlogn) time complexity, but if you need to find indexes of values inside the sort callback you actually add a factor n to that, making it O(n²logn). To get an element out of an array and injecting it elsewhere is an operation that can be done in O(n) time. You can use Array#splice (twice) to do just that.

trincot
  • 317,000
  • 35
  • 244
  • 286
  • Amazing answer, thanks a lot ! In my previous implementation, I actually used splice to achieve the desired result but mainly because of convenience rather than execution speed. However, thanks to your informations and my curiosity being satisfied I can now choose wisely :) – Thomas Milan Jul 15 '18 at 22:02