sort an array by relative position

Question

Give a array which has negative and positive integers,implement a algorithm that costs O(n) time and O(1) spaces to make all negative integers in front of all positive integers, and keep the relative position. for example:{1,7,-5,9,-12,15} -----> {-5,-12,1,7,9,15}

do you have any ideas?

Answer 1

You are asking for a stable in-place partition function.

The paper Stable Minimum Space Partitioning in Linear Time (1992) claims to have such an algorithm, but some other SO questions have raised doubts about its feasibility.

Answer 2

my idea for an algorithm:

have a pivot point similar to in partition based general selection. http://en.wikipedia.org/wiki/Selection_algorithm

Revolve around the pivot swapping values until all negative numbers are in one partition of the array (with all the positive numbers after it.. or perhaps surrounding it)

However this swapping will have slightly affected the ordering. I'll explain how to correct the ordering of the negative numbers (and you do the same to correct the ordering of the positive numbers).

Each time you swapped two numbers .. change the sign of the number.

this means if you through the partition of negative numbers, all the ones that are positive are negative numbers that were swapped. That means all the negative numbers between a positive number and the next positive number should be before the first positive number. go through and swap them all (there shouldn't be too many in a row so you should get O(N))

negs = -4,-5,-6
pos = 1,2,3
ans = -4,-5,-6,1,2,3

1,2,-4,-5,3,-6

i->-4  j->-5
-4 and -5 are both negative.. decrease i by one

1,2,-4,-5,3,-6
i->2 j->-5
swap.

1,5,-4,-2,3,-6
i->1 j->3
1 and 3 are both positive, increase j by one (take turns at changing i,j)

1,5,-4,-2,3,-6
i->1 j->-6
swap.

6,5,-4,-2,3,-1

#now we have negs at start, pos at end of array.
#now do corrections using signs as notification of what was swapped
#we had a counter that told us there were 3 negs.and 3 pos.
#fix first 3 negs.. 6,5,-4 should go to -4,-5,-6
(can tell order by. non swapped negs always come before swapped negs..in the order they are in.. negs are in reverse order)
i'll leave you to implement algorithm for it.