Sort an array of integers into odd, then even

Question

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;
  }

Answer 1

The simplest and easiest in this case is by using 'bitwise operands' to access the least significant bit of each array element together with the sort method:

function sortArray(array) {
let safe = [];
let mysort = Array.prototype.sort;
let mysplice = Array.prototype.splice;
 function zipit(arg){return arg[0];}
array.forEach(function(e){safe.push(e & 1);}); 
let odds = array.filter(function(e){
return (e & 1);}).sort(function(a,b){return a-b;});
let evens = array.filter(function(e){
return !(e & 1);}).sort(function(a,b){return b-a;});
let res = safe.map(function(ele,x){ return ( ele ) ? zipit(mysplice.call(odds,0,1)) : zipit(mysplice.call(evens,0,1));});
return res;
}

console.log(sortArray([2,3,2,1,5,6,7,8]));

and that's it. You get an perfectly ordered & sorted array of odds,...even.

Answer 2

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.

function sortByParity(a){
  var ec = 0; // Even count
  for (var i = 0; i < a.length; i++){
    a[i] & 1 ? [a[i],a[i-ec]] = [a[i-ec],a[i]] // If odd then swap accordingly
             : ec++;                           // If even increment even count
  }
  return a;
}

var arr = [5,2,7,9,2,3,8,1,6,4],
    brr = [0,2,4,6,8,1,3,5,7,9],
    crr = [1,2,3,4,5,6,7,8,9,0];
console.log(JSON.stringify(sortByParity(arr)));
console.log(JSON.stringify(sortByParity(brr)));
console.log(JSON.stringify(sortByParity(crr)));

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))

function sortByParity(arr){
  var oc = 0;
  arr.forEach((e,i,a) => e & 1 && ([a[i], a[oc++]] = [a[oc], a[i]]));
  return arr;
}
              
var arr = [5,2,7,9,2,3,8,1,6,4],
    brr = [0,2,4,6,8,1,3,5,7,9],
    crr = [1,2,3,4,5,6,7,8,9,0];
console.log(JSON.stringify(sortByParity(arr)));
console.log(JSON.stringify(sortByParity(brr)));
console.log(JSON.stringify(sortByParity(crr)));

Answer 3

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).

function SortThisArray(arr) {

  var startIndex = 0;
  var endIndex = arr.length - 1;

  while(startIndex < endIndex) {

    if(arr[startIndex] % 2 == 0 && arr[endIndex] % 2 == 1) {
      var temp = arr[startIndex];
      arr[startIndex] = arr[endIndex];
      arr[endIndex] = temp;
    }

    if(arr[startIndex] % 2 == 1) 
      startIndex++;      

    if(arr[endIndex] % 2 == 0)
      endIndex--;
  }

  return arr;
}

Answer 4

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

The algorithm keeps the order of 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:

        array                        comment
---------------------    --------------------------------
5 7 2 8 7 9 2 1 4 6 8    found even odd couple at index 3
      ^ ^                swap items, decrement index by 1
5 7 2 7 8 9 2 1 4 6 8    found even odd couple at index 2
    ^ ^
5 7 7 2 8 9 2 1 4 6 8    found even odd couple at index 4
        ^ ^
5 7 7 2 9 8 2 1 4 6 8    found even odd couple at index 3
      ^ ^
5 7 7 9 2 8 2 1 4 6 8    found even odd couple at index 6
            ^ ^
5 7 7 9 2 8 1 2 4 6 8    found even odd couple at index 5
          ^ ^
5 7 7 9 2 1 8 2 4 6 8    found even odd couple at index 4
        ^ ^
5 7 7 9 1 2 8 2 4 6 8    final result

var a = [5, 2, 7, 8, 7, 9, 2, 1, 4, 6, 8],
    i = 0,
    temp;

while (i < a.length - 1) {
    if (!(a[i] % 2) && a[i + 1] % 2) {
        temp = a[i];      
        a[i] = a[i + 1];
        a[i + 1] = temp;
        i && i--;
        continue;
    }
    i++;
}

console.log(a); // [5, 7, 7, 9, 1, 2, 8, 2, 4, 6, 8]

.as-console-wrapper { max-height: 100% !important; top: 0; }

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

var a = [0, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 1],
    i = 0,
    j,
    temp;

while (i < a.length - 1) {
    j = i;
    while (!(a[j] % 2) && a[j + 1] % 2) {
        temp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = temp;
        if (!j) {
            break;
        }
        j--;
    }
    i++;
}

console.log(a);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 5

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:

var res = [];
for(var i = 0; i < input.length; ++i)
  If (input [i] % 2)
      res.unshift (input[i])
  else
      res.push(input [i])

Answer 6

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 exactly what 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.

Answer 7

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

function sort(list)
{
  var bottom=0
  var top=list.length-1
  var swap
  while(bottom < top)
  {
    if (list[bottom] % 2 == 1) 
      ++bottom
    else if (list[top] % 2 == 0)
      --top
    else {
      swap = list[bottom]
      list[bottom] = list[top]
      list[top] = swap

    }
  }
  return list 
}

Answer 8

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

var input = [5, 2, 7, 9, 2, 3, 8, 4];
var result = input.filter(x => x%2).sort().concat(input.filter(x => x%2 === 0).sort());
console.log(result);

Answer 9

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.

var data = [5, 2, 7, 9, 2, 3, 8, 4];

// end holds the position of the last unsorted number
var end = data.length - 1;
// start holds the position of the first unsorted number
var start = 0;
// position is the current index of the number which is of interest 
var position = start;

// while the two sorted halves have not met
while (start < end) {
  var subject = data[position];
  if (subject % 2 === 1) {
    // it's odd, it's already in the correct half of the array
    // so move to the next number, and increase start, marking this
    // number as sorted
    position++;
    start++;
  } else {
    // it's even, move it to the even sorted section. The means that
    // the number in "position" has not been looked at yet, so do not
    // increase "position", but there's an extra sorted number at the
    // end, so decrease "end"
    var temp = data[end];
    data[end] = subject;
    data[position] = temp;
    end--;
  }
}

console.log(data);

Answer 10

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.

startIndex = 0
endIndex = a.length - 1
while (startIndex < endIndex)
{
    // Skip over odd numbers at the front of the array
    while (startIndex < endIndex && (a[startIndex] % 2) != 0)
        ++startIndex;
    if (startIndex >= endIndex)
        break;
    // startIndex points to an even number
    // now look for the first odd number at the end of the array
    while (startIndex < endIndex && (a[endIndex] % 2) == 0)
        --endIndex;
    if (startIndex >= endIndex)
        break;
    // swap the two items, placing the even number
    // towards the end of the array, and the odd number
    // towards the front.
    temp = a[startIndex];
    a[startIndex] = a[endIndex];
    a[endIndex] = temp;
    // and adjust the indexes
    ++startIndex;
    --endIndex;
}

So, given your example array:

[5, 2, 7, 9, 2, 3, 8, 4]

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:

[5, 3, 7, 9, 2, 2, 8, 4]

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.

Answer 11

Try using simple sorting, it gives what you expect

var data = [5, 2, 7, 9, 2, 3, 8, 4];
data.sort(function(a, b) {
  return b % 2 - a % 2
});
console.log(data);
// [5, 7, 9, 3, 2, 2, 8, 4]

// % is mod, 5 % 2 = 1; 2 % 2 = 0;