0

Given an array of positive and negative integers, re-arrange it so that you have positive integers on one end and negative integers on other, but retain their order of appearance in the original array.

For example given: arr = [2, -12, 4, 46, -20, -1] The answer should be: arr = [-12, -20, -1, 2, 4, 46]

How can I arrange the array this way in JavaScript?

Thanks.

momo
  • 47
  • 5

2 Answers2

3

You can use reduce() to create one object of positive and negative values and then join those values in one array.

var arr = [2, -12, 4, 46, -20, -1];
var o = arr.reduce(function(r, e) {
  return e < 0 ? r.n.push(e) : r.p.push(e), r
}, {p: [], n: []})

var result = [...o.n, ...o.p]
console.log(result)
Nenad Vracar
  • 118,580
  • 15
  • 151
  • 176
  • It seems pretty clear here that you reopened this ***clear*** duplicate *just* to be able to post your answer. Please do not do that again; it is abuse of your privileges. – Matt May 23 '17 at 12:07
  • @Matt♦ Got it. Just one question, if i vote to reopen some duplicate question that i think is not duplicate does that reopen that question instantly or some more users also need to vote to reopen that question. – Nenad Vracar May 23 '17 at 12:21
  • It depends if you're a gold badge holder in one of the question's tags. If you are, it'll reopen instantly. If not, you'll have to wait for other user(s) to vote as well. See https://meta.stackexchange.com/questions/230865/increase-close-vote-weight-for-gold-tag-badge-holders – Matt May 27 '17 at 11:48
0

You could reach the desired result with Array#reduce function. If iterated element is less or equal to 0, add it at the beginning of the result array. If not - push it to the end. 

var arr = [2, -12, 4, 46, -20, -1],
    res = arr.reduce(function(s,a) {
      a <= 0 ? s.unshift(a) : s.push(a);
      return s;
    }, []);
    
    console.log(res);
kind user
  • 40,029
  • 7
  • 67
  • 77
  • Do you not realise that just sorting the array already does this "negative at the start, positive at the end" thing? XD – Niet the Dark Absol Apr 30 '17 at 21:26
  • @NiettheDarkAbsol Damn, got mind-farted xd – kind user Apr 30 '17 at 21:28
  • A more interesting "hack" would be `arr.sort(function(a,b) {return a/0 - b/0;})` - it kind of abuses the fact that `NaN` is considered neither positive nor negative for sorting :D – Niet the Dark Absol Apr 30 '17 at 21:34
  • @NiettheDarkAbsol This is sweet hack, but if we already use `sort` function, why to complicate it instead of simple `a-b`? ;d – kind user Apr 30 '17 at 21:41
  • Because my understanding of the question is that the sort should be stable, leaving the negative numbers in the order they appeared. – Niet the Dark Absol Apr 30 '17 at 21:42
  • @NiettheDarkAbsol Now it makes sense. – kind user Apr 30 '17 at 21:46
  • You could use `sort( (a,b) => (a < 0) - (b < 0) )`: but it has *O(nlogn)* time complexity. – trincot Apr 30 '17 at 22:00
  • The algorithm given here runs with *O(n²)* average time-complexity, since `unshift` needs to reassign each element in the array, so in theory sorting with `sort` will be faster. However, there are algorithms which run in *O(n)*. – trincot Apr 30 '17 at 22:12
  • @trincot Then which solution is actually better? Reduce or your sort? – kind user Apr 30 '17 at 23:02
  • @Kinduser, if we order solutions by their time complexity and then by their space complexity, in decreasing order (worse to better) we get: this reduce solution (time: *O(n²)*, space: *O(n)*), the sort-solution mentioned above (time: *O(nlogn)*, space: *O(1)*), [Nenad's solution](http://stackoverflow.com/a/43711541/5459839) (time: *O(n)*, space: *O(n)*) and finally [this solution in the duplicate question](http://stackoverflow.com/questions/4897280/given-an-array-of-positive-and-negative-integers-re-arrange-it-so-that-you-have/43711760#43711760) (time: *O(n)*, space: *O(1)*). – trincot May 01 '17 at 06:01
  • @trincot Do you know any source from which I could learn something about this *time complexity*? Without any knowledge about it, I just guess that the best solution atm is yours from the dupe question, isn't it? – kind user May 01 '17 at 11:16
  • Yes, the best solution would be the one in the dupe. BTW, that does not mean that it will always run faster, just that there exists an input size above which it will *always* have a better "worst-case" run time. So the positive effect might only become relevant for large arrays. But then it will be an effect that becomes greater and greater for increasing array sizes. In this [Q&A](http://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) you'll find some useful info and links on the subject. – trincot May 01 '17 at 18:19
  • @trincot Thank you. But I gotta tell you, I'm very surprised that `unshift` method has higher time complexity than `push`. They look... pretty the same, which a slight difference that `push` pushes the element on the back and `unshift` adds it at the beginning. This is very interesting. – kind user May 01 '17 at 18:28
  • That is because `push` just adds an index entry to an array -- leaving all the existing elements in place, while with `unshift`, every value already in the array needs to be placed at another index. This means work has to be done for each of them. – trincot May 01 '17 at 18:32
  • @trincot It makes sense. Thanks mate. – kind user May 01 '17 at 18:34