JavaScript: Re-order an array

Question

I read a few answers on SO about the problems when dealing with splice (including Move an array element from one array position to another) but I was unable to solve my problem.

I am trying to reorder an array in a particular pattern. Let's assume the pattern is that all the negative numbers should be to the left of the array and all the postive numbers should be to the right of the array. The negative and positive numbers should be separated by zeros if any. It is important that the order be maintained

Sample Input   = [3,0,2,-1,0,-3]
Desired Output = [-1,-3,0,0,3,2]

This is the code I wrote

function reorderArray(inputArray) {
origLength = inputArray.length
var indexZero = -1;
  for (var i = 0; i < origLength; i++) {
    if (inputArray[i] > 0) {
        inputArray.push(inputArray[i]);
        inputArray.splice(i, 1);
    } else if (indexZero == -1 && inputArray[i] == 0) {
        indexZero = i;
    } else if (indexZero != -1 && inputArray[i] < 0) {
        inputArray.splice(indexZero, 0, inputArray.splice(i, 1))
        indexZero++;
    }
  }
alert(inputArray);
}

I run into a problem in the first step itself where I attempt to move all positive numbers at the back of the array because of the re-indexing. I can't start from the last index because that would mean losing the order and I can't use the i-- since it would run infinitely.

Any help with how I could make my code work would be appreciated. Additionally, if there is an alternative that is more efficient than splice, that would be welcome too.

Thanks.

Answer 1

var input = [3,0,2,-1,0,-3];

var copy = input.slice(0); // you need an original array copy since you need to
                           // refer to it to maintain the original order

input.sort(function(a, b) {
    var sign_a = Math.sign(a),
        sign_b = Math.sign(b);

    if (sign_a != sign_b) {
        return sign_a - sign_b;
    }

    return copy.indexOf(a) - copy.indexOf(b);
});

console.log(input);

JSFiddle: http://jsfiddle.net/w2g195fy/2/

So you first compare numbers by sign, then you guarantee sort stability by comparing the positions in the original array. The latter is IMPORTANT since Array.prototype.sort() is not guaranteed to be stable.

Another important note: the complexity (from number of comparisons point of view) of this particular implementation is O(N^2 * logN) which may be not acceptable if you have large original array.

Yet another important note: it will not work in case if your input array has duplicate values.

This is a naive implementation that will work with duplicates:

var input = [1, -1, 2, 0, -2, 3, 0, -3, -4, 4, 0];

var groups = input.reduce(function(result, item) {
    result[Math.sign(item)].push(item);
    return result;
}, {'-1': [], 0: [], 1: []});

var result = groups['-1'].concat(groups[0]).concat(groups[1]);

console.log(result)

And here is the most efficient (from both memory and number of comparisons point of view - it's O(N)) solution I can think of:

var input = [1, -4, 2, 0, -2, 3, 0, -3, -4, 4, 0];

var result = [];

for (var sign = -1, len = input.length; sign <= 1; ++sign) {
    for (var i = 0; i < len; ++i) {
        if (Math.sign(input[i]) == sign) {
            result.push(input[i]);
        }
    }
}

console.log(result);

http://jsfiddle.net/pbmw4dtt/

Answer 2

Another way with of doing it with sort:

[3,0,2,-1,0,-3].map(function () { return arguments; }).sort(function (a, b) {
    var aNum = a[0],
        bNum = b[0],
        bothNegative = aNum < 0 && aNum < 0,
        bothPositive = aNum > 0 && bNum > 0;

    if (bothNegative || bothPositive) return a[1] - b[1];
    return aNum - bNum;

}).map(function (arr) { return arr[0]; });

The initial items order is preserved, but they are now segregated in 3 groups. Negatives, zeros and positives.

Answer 3

This can also be a solution:

var input = [3,0,2,-1,0,-3].join('+');
var output = input.match(/-\d+/g).concat( input.match(/0/g) ).concat( input.match(/(^|\+)[1-9]\d*/g) ).map(parseFloat);

And Fiddle.

It is slower than sort because of last array map (which can be omitted), but idea may be useful.