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

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.