0

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.

Improve this question
6
  • 1
    Not sure I get it, looks like you're describing a standard Array.sort -> jsfiddle.net/adeneo/5ncfb2uu, but without the order Commented Nov 28, 2014 at 22:22
  • 2
    Or you could do this -> jsfiddle.net/adeneo/5ncfb2uu/1 Commented Nov 28, 2014 at 22:24
  • 3
    As order is important, you may find it easier to filter into 3 separate arrays of -ves,0s,+ves then put them back together Commented Nov 28, 2014 at 22:25
  • I also think it's better to filter values into 3 different arrays. Than in the end, you still can concat those 3 arrays into 1. Commented Nov 28, 2014 at 22:26
  • Thanks everyone. My first approach was 3 separate arrays but I wasn't sure of the space complexity ramifications. Any help on that? Commented Nov 28, 2014 at 22:31

3 Answers 3

Reset to default
2 
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/

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

Thank you. This does work but like you pointed out, the complexity is a problem and it won't work if there are duplicates. Do you suppose I could replace the positive numbers with undefined in my code? And then have a second run to get rid of the undefined?
@Sid: "the complexity is a problem" --- put some constraints into the question then
Sorry about that. There aren't any constraints to start off and I'm terrible at calculating Complexity so I don't even know the probable complexity that my code would eventually have. But I was trying to get to as optimum a solution as possible. Sorry again. The duplicates bit is still a problem though, correct?
@Sid What's the problem with duplicates? How should they be handled?
@plalx: In the order they appear. So if it's [-3, -1, 0, 2, -3], it should output [-3, -1, -3, 0, 2]
|
1

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.

Improve this answer

Comments

0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.