5

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?

1

4 Answers 4

5

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.

1
  • 1
    Citation from the paper: "Moreover, we assume that a constant number of extra storage locations, each capable for storing a word of O(log2n) bits, is available". I don't know why they call that O(1) extra space. Mar 12, 2012 at 12:26
1

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.
9
  • (1,2,-4,-5,3,-6) ---> (-4,2,1,-5,3,-6) ---> (-4,-5,1,-2,3,-6) ---> (-4,-5,-6,-2,3,-1) ---> (-4,-5,-6,2,1,3) after 5 steps, 1 and 2 are not in right order. is there something wrong with me ? Mar 13, 2012 at 3:12
  • Can you see how to change 6,5,-4 into -4,-5,-6? -4 should go first because it hasn't been swapped. 6,5 come after the -4 in reverse order (because the swapping flips them). So your algorithm just needs to go through the list from left to right, swapping flipped ones to the end and decreasing the end by 1 each time it does that. And moving the non flipped ones to the front in their place..
    – Rusty Rob
    Mar 13, 2012 at 3:28
  • non swapped negs always come before swapped negs.. i don't think so, for example 1,-4,2,-5,3,-6 -->(i=2,j=-5,swap to[1,-4,5,-2,3,-6]) --> (i=-4,j=3,then increase j by one and decrease i by one, i=1,j=-6,swap to[6,-4,5,-2,3,-1]), then fix 3 negs [6,-4,5] --->(i=6,j=-4,swap to[4,-6,5],then to[-4,-6,-5]). so non swapped and swapped are mixed, how can you fix to right result? by the way, this algorithm will be O(nlogn), not O(n), because you should traverse all left numbers very time,T(2n)=2T(n)+n=nlogn. Mar 14, 2012 at 4:35
  • The part of my algorithm that gets you to [6,-4,5] is O(N). Now you need to move the negative numbers to the front and reverse the positive numbers and move them to the back to get [-4,5,6] which is the answer. I claim this last step can be done in O(N) also in place. I was working on it at the end of my code but didn't get time to finish working out how to do it.
    – Rusty Rob
    Mar 14, 2012 at 6:27
  • 1
    Well i have to say thank you. you are not only give your idea bu also implement your idea. that is what i have learned from you, to be serious. it was a nice discussion with you. Mar 16, 2012 at 3:57
0

This code is most of the way there.. I just haven't done the part where it reverses the swapped values between x,j and between j,y. (you can reverse in place.. i didnt do that yet).

Anyway.. I don't have time to complete it i'm afraid, but hopefully you can:

def brute_force(nums):
    neg = [i for i in nums if i<0]
    pos = [i for i in nums if i>=0]
    return neg+pos

def in_place(nums,i,j,depth):
    x,y = i,j
    print 'running on ',nums[i:j+1]
    if j-i==1:
        a,b = nums[i],nums[j]
        if a>=0 and b<0:
            nums[i],nums[j] = b,a
        return None
    #print i,j
    while i<j:
        a,b = nums[i],nums[j]
        if (a<0 and b>=0):
            i+=1
            j-=1
        elif (a>=0 and b<0):
            nums[i],nums[j]=-b,-a
            i+=1
            j-=1
        elif a<0:
            i+=1
        else:
            j-=1
    print "changed1 to ", nums
    print nums[x:j+1],nums[j+1:y+1]
    start = (i for i in reversed(nums[x:j+1]) if i>=0)
    for i in range(x,j):
        if nums[i]>=0:
            nums[i]=next(start)
    print "changed2 to ", nums
    end = (i for i in reversed(nums[j+1:y+1]) if i<0)
    for i in range(j+1,y+1):
        if nums[i]<0:
            nums[i]=next(end)
    print "changed3 to ", nums
    if depth == 0:
        in_place(nums,0,j,depth+1)
        in_place(nums,j+1,len(nums)-1,depth+1)







nums = [1,2,-4,-5,3,-6]

print brute_force(nums)
in_place(nums,0,len(nums)-1,0)
print nums
print "going z"
#z = [-2,3,-1]
#in_place(z,0,2,0)
#print z

Further example:

_list = [1,-4,2,-5,3,-6]

def in_place(nums,i,j,depth):
    x,y = i,j
    print 'running on ',nums[i:j+1]
    if j-i==1:
        a,b = nums[i],nums[j]
        if a>=0 and b<0:
            nums[i],nums[j] = b,a
        return None
    #print i,j
    while i<j:
        a,b = nums[i],nums[j]
        if (a<0 and b>=0):
            i+=1
            j-=1
        elif (a>=0 and b<0):
            nums[i],nums[j]=-b,-a
            i+=1
            j-=1
        elif a<0:
            i+=1
        else:
            j-=1
    print "changed1 to ", nums

in_place(_list,0,len(_list)-1,0)

>>>
running on  [1, -4, 2, -5, 3, -6]
changed1 to  [6, -4, 5, -2, 3, -1]
0

This can be done by altering merge function in merge sort algorithm.

Input: int[] A, int low, int mid, int high

Loop in-variance before start: A[low] to A[mid] has -ve numbers following by +ve numbers and has numbers that were originally present in A[low] to A[mid].
Above condition holds for A[mid+1] to A[high]

Merging steps:

  1. skip all elements between low to mid that are -ve, save the starting point of +ve numbers say in variable j.
  2. copy remaining elements that are +ve before mid to temporary array
  3. copy all -ve elements in range mid+1 to high starting from A[j] while incrementing j
  4. copy the elements stored in temporary array back to A continuing from j
  5. +ve elements in the second half of A are already in place, so no need to do anything

    public static void rearrange(int[] a){
        merge_arrange(a, 0, a.length-1);
    }
    
    public static void merge_arrange(int[] a, int low, int high){
        if(low < high){
            int mid = (low+high)/2;
            merge_arrange(a, low, mid);
            merge_arrange(a, mid+1, high);
    
            merge(a, low, mid, high);
        }
    }
    
    public static void merge(int[] a, int low, int mid, int high){
        ArrayList<Integer> temp = new ArrayList<Integer>();
    
        int i;
        for(i=low;i<=mid && a[i]<0;i++);
    
        int j=i;
        while(i<=mid){
            temp.add(a[i++]);
        }
    
        int k;
        for(k=mid+1;k<=high && a[k]<0;k++){
            a[j] = a[k];
            j++;
        }
    
        for(int num:temp){
            a[j] = num;
            j++;
        }
    }
    

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.