Rearranging an array such that positive and negative elements are at alternate positions
Worst case

Picturing the worst case helps understanding the problem.
The test failing probably uses an array of size n containing n/2 positive numbers followed by n/2 negative numbers (or vice-versa).

Current implementation

Note that when you find an element out of place, you are iterating twice through the indices, until you find the correct element: one time two found its position, another to move all elements in between.
You can combine both operations into one. Still this algorithm resembles the insertion sort. It will be quadratic in the worst case that I described (more specifically, (n/2)^2).

Using extra space

One efficient way to solve this is to build the correct array from the beginning. This requires O(1) of extra space.
You create 3 arrays: one to buffer positive numbers, other to buffer negative numbers, and a 3rd one with the final result.

When reading from stdin:


Place the number in the 3rd array if it matches the position, otherwise store it in the appropriate array;
If the number matches, try to use numbers stored in the positive/negative numbers arrays to keep filing the 3rd array (using FIFO).


What we are doing is essentially merging 3 sorted arrays: stdin, the array with positive numbers and the array with negative numbers.

This should run linearly, requiring 2 writes per number out of place.