Sort Array By Parity

Question

The task is taken from leetcode

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

Input: [3,1,2,4]

Output: [2,4,3,1]

The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

1 <= A.length <= 5000

0 <= A[i] <= 5000

My functional solution 1

const sortArrayByParity = A => A.reduce((acc, x) => {
        if (x % 2 === 0) { acc.unshift(x); }
        else { acc.push(x); }
        return acc;
    }, []);

My functional solution 2

const sortArrayByParity = A => A.reduce((acc, x) => x % 2 === 0 ? [x, ...acc] : [...acc, x]);

My imperative solution

function sortArrayByParity2(A) {
  const odd = [];
  const even = [];
  for (const a of A) {
    if (a % 2 === 0) {
      even.push(a);
    } else {
      odd.push(a);
    }
  }
  return [...even, ...odd];
};

Answer 1

Bug

Your second functional solution does not run. You forgot to add the second argument to A.reduce. I will assume you wanted an array as the last argument.

Why functional sucks

This example clearly illustrates the problem with some functional solutions that involve data manipulation. The requirement of no side effects forces the solution to copy the whole dataset even when you manipulate only a single item. This is particularly noticeable in your second functional solution. See performance results below.

Code and Style

Some minor points...

• function () {}; the trailing semicolon is not needed.

• Swap the conditions.

  You have if(a % 2 === 0) { /*even*/ } else { /*odd*/ } ...

  can be if(a % 2) { /*odd*/ } else { /*even*/ }

• Compact code. Try to avoid sprawling code. It may not matter for small segments of code, but source code can very long and reading code there spans pages is not as easy as having it all in one view.

• Before a newline it is either } or ;. There are two exceptions. The } that closes an object literal should have a closing ; eg const a = {};. And multi line statements and expressions.

Know the language.

You do a lot of code examples, many of them are rather trivial. Of late many of your posts contain bugs or incomplete code (may be a sign of boredom? or a lack of challenge (engagement)) . I do not believe in the classical closed book assessment examination, it does not reflect the real world. However a good memory of the field makes you a more productive coder.

There are many subtle tricks in JavaScript that can catch you out if unaware. Testing your knowledge improves your understanding of the language making you a better coder.

This is a example JavaScript Web Development Quiz picked at random from a web search "javascript quiz"

It is good practice to do one of these every now and then.

_{^{I did not get 100% 😶}}

Example A

Compacting the function.

function sortByParity(arr) {
    const odd = [], even = [];
    for (const val of arr) {
        if (val % 2) { odd.push(val) }
        else { even.push(val) }
    }
    return [...even, ...odd];
}

Performance

The second functional example was so slow I had to push the other best time down to the timer resolution cutoff 0.2ms or it would have taken forever to complete the test.

The functions as tested

function sortByParity_I1(A) {
    const odd = [], even = [];
    for (const a of A) {
        if (a % 2 === 0) { even.push(a) }
        else { odd.push(a) }
    }
    return [...even, ...odd];
}
const sortByParity_F2 = A => A.reduce((acc, x) => x % 2 === 0 ? [x, ...acc] : [...acc, x], []);
const sortByParity_F1 = A => A.reduce((acc, x) => {
        if (x % 2 === 0) { acc.unshift(x) }
        else { acc.push(x) }
        return acc;
    }, []);

Benchmarks

Mean time per call to the function in 1/1,000,000 second. OPS is operations per second. % is relative performance of best.

For array of 1000 random integers

sortByParity_I1:    20.709µs OPS  48,287 100%
sortByParity_F1:   133.933µs OPS   7,466  15%
sortByParity_F2: 3,514.830µs OPS     284   1%

For array of 100 random integers

sortByParity_I1:     2.049µs OPS 488,148 100%
sortByParity_F1:    10.005µs OPS  99,947  20%
sortByParity_F2:    46.679µs OPS  21,422   4%

Note that the results for the functional solution do not have a linear relationship with the size of the array.

Improving performance

I will drop the slow functional and add an improved imperative function that pre allocates the result array. This avoids the overhead of allocation when you grow the arrays. As there is one array the overhead of joining the two arrays is avoided as well. This almost doubles the performance.

function sortByParity_I2(A) {
    const res = new Array(A.length);
    var top = res.length - 1, bot = 0;
    for (const a of A) { res[a % 2 ? top-- : bot ++] = a }
    return res;
}

10000 items
sortByParity_I2:   119.851µs OPS     8,343 100%
sortByParity_I1:   223.468µs OPS     4,474  54%
sortByParity_F1: 5,092.816µs OPS       196   2%

1000 items
sortByParity_I2:    13.094µs OPS    76,372 100%
sortByParity_I1:    23.731µs OPS    42,138  55%
sortByParity_F1:   123.381µs OPS     8,104  11%

100 items
sortByParity_I2:     0.900µs OPS 1,110,691 100%
sortByParity_I1:     2.245µs OPS   445,398  40%
sortByParity_F1:     9.520µs OPS   105,039   9%

_{^{Test on Win10 Chrome 73 CPU i7 1.5Ghz}}