How to partition array of integers to even and odd?

Question

I want to partition an array (eg [1,2,3,4,5,6,7,8]), first partition should keep even values, second odd values (example result: [2,4,6,8,1,3,5,7]).

I managed to resolve this problem twice with built-in Array.prototype methods. First solution uses map and sort, second only sort.

I would like to make a third solution which uses a sorting algorithm, but I don't know what algorithms are used to partition lists. I'm thinking about bubble sort, but I think it is used in my second solution (array.sort((el1, el2)=>(el1 % 2 - el2 % 2)))... I looked at quicksort, but I don't know where to apply a check if an integer is even or odd...

What is the best (linear scaling with array grow) algorithm to perform such task in-place with keeping order of elements?

Any sort is at best `O(nlogn)`, so if you want linear scaling, those aren't the best option — frozen, Jul 14 '17 at 23:40
@T.J.Crowder in-place, I think only purpose is to make it harder (my question is a homework) — Marecky, Jul 15 '17 at 18:46

Jim Mischel · Answer 1 · 2017-07-15T00:37:35.023

2

You can do this in-place in O(n) time pretty easily. Start the even index at the front, and the odd index at the back. Then, go through the array, skipping over the first block of even numbers.

When you hit an odd number, move backwards from the end to find the first even number. Then swap the even and odd numbers.

The code looks something like this:

var i;
var odd = n-1;
for(i = 0; i < odd; i++)
{
    if(arr[i] % 2 == 1)
    {
        // move the odd index backwards until you find the first even number.
        while (odd > i && arr[odd] % 2 == 1)
        {
            odd--;
        }
        if (odd > i)
        {
            var temp = arr[i];
            arr[i] = arr[odd];
            arr[odd] = temp;
        }
    }
}

Pardon any syntax errors. Javascript isn't my strong suit.

Note that this won't keep the same relative order. That is, if you gave it the array [1,2,7,3,6,8], then the result would be [8,2,6,3,7,1]. The array is partitioned, but the odd numbers aren't in the same relative order as in the original array.

edited Jul 15 '17 at 00:37

answered Jul 15 '17 at 00:18

Jim Mischel

131,090
20
188
351

1

While this is efficient, I thought part of the objective was to make it a stable partition, since the OP specified in the example that the output should maintain the same order as the input within each of the partitions. – Patrick Roberts Jul 15 '17 at 00:21
1

@PatrickRoberts: I don't see where OP specifically says that the output should be stable. His example shows a stable arrangement, but there's nothing that says it must be stable. Point taken, though: this is not stable. I'll update my answer with that information. – Jim Mischel Jul 15 '17 at 00:24
@PatrickRoberts, thanks, It should keep partition order like You say. Sorry Jim I didn't write it explicitly. – Marecky Jul 16 '17 at 11:30

Bergi · Accepted Answer · 2017-07-15T01:33:24.970

0

If you are insisting on an in-place approach instead of the trivial standard return [arr.filter(predicate), arr.filter(notPredicate)] approach, that can be easily and efficiently achieved using two indices, running from both sides of the array and swapping where necessary:

function partitionInplace(arr, predicate) {
    var i=0, j=arr.length;
    while (i<j) {
        while (predicate(arr[i]) && ++i<j);
        if (i==j) break;
        while (i<--j && !predicate(arr[j]));
        if (i==j) break;
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++;
    }
    return i; // the index of the first element not to fulfil the predicate
}

edited Jul 15 '17 at 01:33

answered Jul 15 '17 at 01:21

Bergi

630,263
148
957
1,375

1

Isn't this the same logic as my answer? Won't this change the relative order of items in the partitions? That is, if given [1,3,2,4], the resulting array will be [4,2,3,1]? – Jim Mischel Jul 16 '17 at 12:17
@JimMischel Yes, it's the same idea, only my implementation works with arbitrary predicates, returns the position at which the array is partitioned, and has therefore much more complicated code :-) Indeed the swap change the relative order, but I'm pretty sure that there is no algorithm that does achieve a stable reordering in `O(n)` time and `O(1)` space complexity. – Bergi Jul 16 '17 at 12:38
I think you're right that there isn't an O(n), O(1) solution that's stable. Reminds me of the joke(?): Fast, Cheap, Good: pick two. – Jim Mischel Jul 16 '17 at 20:04

frozen · Answer 3 · 2017-07-14T23:45:23.467

-1

let evens = arr.filter(i=> i%2==0);
let odds = arr.filter(i=> i%2==1);
let result = evens.concat(odds);

I believe that's O(n). Have fun.

EDIT: Or if you really care about efficiency:

let evens, odds = []
arr.forEach(i=> {
if(i%2==0) evens.push(i); else odds.push(i);
});
let result = evens.concat(odds);

edited Jul 14 '17 at 23:45

answered Jul 14 '17 at 23:42

frozen

2,114
14
33

Meh, we can cut half that overhead. (Nor is this in-place, see the end of the answer.) – T.J. Crowder Jul 14 '17 at 23:43
2

Still not in-place, as the question clearly calls for. Still produces two temporary arrays in addition to the third final one. *(not my dv; I understand it, but wouldn't do it)* – T.J. Crowder Jul 14 '17 at 23:45
@T.J.Crowder `i` is a reserved keyword for `index`, isn't it? – kind user Jul 14 '17 at 23:49
2

@kind: No, not at all. It can be whatever you want it to be. – T.J. Crowder Jul 14 '17 at 23:50

Mehmet Otkun · Answer 4 · 2017-07-15T00:42:17.947

-2

Array.prototype.getEvenOdd= function (arr) {
    var result = {even:[],odd:[]};
    if(arr.length){
      for(var i = 0; i < arr.length; i++){
        if(arr[i] % 2 = 0)
            result.odd.push(arr[i]);
        else
            result.even.push(arr[i]);
      }
    }
    return result ;
};

edited Jul 15 '17 at 00:42

answered Jul 14 '17 at 23:47

Mehmet Otkun

1,374
9
22

How to partition array of integers to even and odd?

4 Answers4

Linked

Related