## Sort an array of integers into odd, then even

I have a problem I found on an algorithm forum elsewhere.

I have an array with random numbers (for example, `[5, 2, 7, 9, 2, 3, 8, 4]`

) which should be returned to me sorted by odd then even. The order of the odds/evens is not important so in the example it would probably be `[5, 7, 9, 3, 2, 2, 8, 4]`

.

My first thought was to use a `.reduce()`

function to just push them into two different arrays and then join them together, but there are some added complexities to this task.

The added rules of the task are that the sort should maintain a constant extra space, and modify the array in place. It should also use an algorithm which scales consistently with the size of the array.

**Which algorithm?**

Judging by Wikipedia's list, there are a number of algorithms which scale consistently and use a constant amount of space. I also found this website which has a nice bubble sort to use (also posted below), which seems stable and follows my rules *(I think?)*.

I'm not sure if this is the right algorithm to use, or how to approach this part of the task at all.

**Bubble:**

```
function comparator(a, b) {
return a - b;
}
/**
* Bubble sort algorithm.<br><br>
* Complexity: O(N^2).
*
* @example
* var sort = require('path-to-algorithms/src/' +
* 'sorting/bubblesort').bubbleSort;
* console.log(sort([2, 5, 1, 0, 4])); // [ 0, 1, 2, 4, 5 ]
*
* @public
* @module sorting/bubblesort
* @param {Array} array Input array.
* @param {Function} cmp Optional. A function that defines an
* alternative sort order. The function should return a negative,
* zero, or positive value, depending on the arguments.
* @return {Array} Sorted array.
*/
function bubbleSort(array, cmp) {
cmp = cmp || comparator;
var temp;
for (var i = 0; i < array.length; i += 1) {
for (var j = i; j > 0; j -= 1) {
if (cmp(array[j], array[j - 1]) < 0) {
temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
}
}
}
return array;
}
```

Show source

## Answers ( 10 )

Try using simple sorting, it gives what you expect

Yes, your first idea to compute odd then even numbers was fine:

No comparison sort will scale linearly. Fortunately, you can do this with two indexes in the array. Here's the basic idea.

Given an array,

`a`

, that's already populated.So, given your example array:

First time through the loop it finds that the '2' at index 1 is even. Then it searches backwards from the end and finds the '3' at index 5. It swaps them:

The next time through the loop,

`startIndex`

will be 2 and`endIndex`

will 4.`startIndex`

is incremented past the '7' and '9', at which point`startIndex`

is equal to`endIndex`

and you break out of the loop.For a similar problem and similar algorithm, see the Dutch national flag problem.

You can sort the array in place in constant space by using a similar methodology to popular sorting algorithms.

Have a variable to mark the indexes of the currently sorted portions of the array, and then work through the items in between either leaving them in place (in the case that they're odd - in place is already sorted), or moving them to the end if they're even.

This algorithm is

`O(n)`

and the space requirement is the size of the array. Both of these scale linearly with the size of the array.If you accept to duplicate the memory, You can do this with plain old JavaScript functions, since you don't want the subarrays sorted themselves:

Just by a single index conditionally yielding simple swaps, in O(n) time in O(1) space you can do as follows. Note that I have used array destructuring to swap. One might choose to use a temporary variable as well.

Edit: So as @Nina Scholz suggested the same algorithm can be implemented in a similar fashion by counting the odds but might look even simpler. (

`e & 1`

is practically the same as`e % 2`

for testing the parity. Odds will result a 1 (true) while evens will result a 0 (false))Start one pointer from the front which stops at even values and another one from the last which stops at odd values. Swap the two values and continue until both the pointers cross each other.

Also, this algorithm has complexity O(n).

This is a proposal which looks for continuing pairs of even and uneven numbers. When found, then the pair swaps.

The algorithm

keeps the orderof the groups of odd and even numbers.Basically it uses an index counter and a while loop with a back tracking mechanism if a pair is found, then the index is, if greater than zero, decremented.

For example this is the walk through of an array:

This is basically the same, but with less iterations for already visited items.

According to me, this is the simplest way - if you need an explanation, read the answer by @Dinesh Verma

It's single pass and use just 3 variables as extra storage

Plenty of implementations already posted, so I'd like to point out how this problem is already solved in basically any infrastructure out there.

When attacking this question, it's instructive to look at quicksort. Or not quicksort exactly, but quicksort's "partition" suboperation, which is solving essentially the same problem.

The "partition" suboperation accomplishes the following task: Given a sequence of numbers and a pivot, in-place permute the elements of the sequence such that all numbers less than the pivot are on the left side of the sequence, and all numbers greater than the pivot are on the right side of the sequence. (Numbers equal to the pivot end up in the middle, but unless you're trying real real hard to get it wrong, this will just happen automatically.)

That's almost

exactlywhat we're trying to do here: In-place permute the elements such that they're separated into two sides based on a binary test. For quicksort that's less-than; for this problem, it's is-odd.So if you're looking at a problem of this nature (in-place partition based on a binary predicate) the most convenient way to attack it is to copy-paste your codebase's partition operation. The only relevant consideration is that there's no pivot here, so keep in mind where quicksort has moved it to, and don't skip that index.