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

Solution 1

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.

Solution 2

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;

Solution 3

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

Solution 4

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

Solution 5

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.

View more solutions