CareerCup

This can be done in just a single pass. Iterate through the list and keep two variables. One denoting the index which needs to be changed and the other a boolean which specifies whether a positive number is required or negative.

public static void reArrangeArray(int[] input) {
      boolean currIsPositive; 
      int indexToChange = 1;
      if (input[0] < 0) currIsPositive = false; else currIsPositive = true;
      for (int i = 1; i < input.length; i++) {
            if (currIsPositive && input[i] < 0) {
                 // swap input[i] with input[indexToChange]
                 if (i - indexToChange > 0) indexToChange += 2;
                 else currIsPositive = false; indexToChange += 1;
            }
            else if (!currIsPositive && input[i] >= 0) {
                 // swap input[i] with input[indexToChange]
                 if (i - indexToChange > 0) indexToChange += 2;
                 else currIsPositive = true; indexToChange += 1;
             }
             else { 
                //Do Nothing 
             } 

      }
}

does the original order need to be maintained?

Here's an algo which does the trick. The algo find the next element where the sign changes, moves all the elements in the array starting from current index to the index of the sign change by shifting them right by 1. And then puts the sign change at the next element.

public static void arrangeAlternate ( int [] a){
		int i = 0;
		int j = 1;
		
		while ( i < a.length - 2){ 
			
			while ( j < a.length-1 && isSameSign (a[i], a[j])){
				j++;
			}
			
			if ( j == a.length-1){
				break; //since we've moved out of the array and didn't find the next sign
			}
			
			//now store the jth element
			int jThElemenet = a[j];
			
			//move elements from i+1 to jThElement
			moveAllElements(a, i+1, j);
			
			//add that jth element at the correct place
			a[i+1] = jThElemenet;
			
			i++;
			
		}
	}

This can be done in O(n). Just simply go through each element. Maintain two indexes. One for next positive and another one for next negative number.
Go through the array and any time we need a different sign number, get it from the indexes and swap. Trick is to make sure that the pointers always start from the index we are scanning. Pos and Neg index go linearly and so in worst case it is O(n) [for scan] + O(n) [for pos index scan] + O(n) [for neg index scan] ~ O(n)

int negPos=1, posPos = 1, curVal = 0;
bool found = true;
for(int index=0; index < count ; index++)
{
   int swappos = 0;
   if(index%2 == 0) //We need a negative number
   {
     if(arr[index] > 0) //This is positive number. Get a negative and swap.
     {
       if(negPos < index) 
          negPos = index+1;
  
       while(arr[negPos] < 0)
       {
          negPos++;
           if(negPos > count)
               found = false;
           else
              swappos = negPos;
        }
     }
    }
    else //Need a positive number here.
    {
      if(arr[index] > 0) //This is positive number. Get a negative and swap.
     {
       if(posPos < index) 
          posPos = index+1;
  
       while(arr[posPos] < 0)
       {
          posPos++;
           if(posPos > count)
               found = false;
            else
              swappos = negPos;
        }
     }
    }
     if(found == false)
        break;
        swapvalues(index, swappos);
 
}

public static int[] processArray(int[] in){
boolean nextIsPositive = false;
if(in[0]<0){
nextIsPositive = true;
}
int i=0, j=1, temp;
for(i=1;i<in.length;i++){
if(j<=i && in[i]<0 && !nextIsPositive && in[j]>=0){
temp = in[i];
in[i] = in[j];
in[j] = temp;
nextIsPositive = true;
j++;
}else if(j<=i && in[i]>0 && nextIsPositive && in[j]<=0){
temp = in[i];
in[i] = in[j];
in[j] = temp;
nextIsPositive = false;
j++;
}else if(!nextIsPositive && in[j]<0){
j++;
nextIsPositive = true;
} else if(nextIsPositive && in[j]>0){
j++;
nextIsPositive = false;
}

}
return in;

Do a 0-1 sort, so that all -ve numbers come first and then all positive numbers.
Now take two pointer pointing to positive and negative numbers starting position in array. Keep swapping positive with negative and increment pointer by 2

int[] array = { -1, -2, 4, 5, 6, -3, 9, -8, 7 };
int[] pos = new int[array.length], neg = new int[array.length];
int posPos = 0;
int negPos = 0;
for (int i = 0; i < array.length; i++){
	if (array[i] < 0){
		neg[negPos] = array[i];
		negPos++;
	}else {
		pos[posPos] = array[i];
		posPos++;
	}
}
for (int i = 0; i < posPos + negPos; i++) {
	if (i < posPos)
		System.out.print(pos[i] + ", ");
	if (i < negPos)
		System.out.print(neg[i] + ", ");
}

I would use next index in array with alternate sign for swapping...

<pre lang="" line="1" title="CodeMonkey24083" class="run-this">#include<stdio.h>
#include<stdlib.h>
void swap(int *a,int *b){
int temp = *a;
*a = *b;
*b = temp;
}
main(){
int a[9] = {-1 ,-2 ,4 ,5 ,6 ,-3, 9, -8, 7};
int symbol = 1;//postive = 0 , negative = 1
int posindex=0;
while(posindex<9 && a[posindex]<0){
posindex++;
break;
}
int negindex=0;
while(negindex<9 && a[negindex]>=0){
negindex++;
break;
}
int pos=0;
int i = 0;
while(pos < 9){
if(posindex == 9 && negindex ==9 )
break;
else if(symbol == 0 && a[pos] <0 ){
posindex = pos+1;
while(posindex<9 && a[posindex]<0)
posindex++;
if(posindex<9 ) swap(&a[pos],&a[posindex]);
symbol = 1;
pos++;
}
else if(symbol == 1 && a[pos] >= 0 ){
negindex = pos+1;
while(negindex<9 && a[posindex]>0)
negindex++;
if(negindex<9 ) swap(&a[pos],&a[negindex]);
symbol = 0;
pos++;
}
else {
pos++;
if(symbol==0) symbol = 1;
else symbol = 0;
}
}
for(i=0;i<9;i++)
printf("%d ",a[i]);
printf("\n");
system("pause");
}
</pre><pre title="CodeMonkey24083" input="yes">
</pre>

i = -1;
for (j=0;j<n;j++) {
if (a[j]<0) {
i=i+1;
exchange a[i] <---> a[j];
}
}

#include<stdio.h>
#include<conio.h>
void swap(int ,int );
int a[]={1,-2,-3,-4,-5,1,2,3,4};
void main()
{
int needed,current;
int i=0,j=1;
clrscr();
if(a[0]>0)
{
needed=-1;
current=0;
}
else
{
needed=0;
current=-1;
}
while(j<9)
{
if(a[j]>0)
current=0;
else
current=-1;
if(needed==current)
{
swap(i+1,j);
needed=~needed;
i++;
j=i+1;
}
else
j++;
}
for(i=0;i<9;i++)
printf(" %3d",a[i]);
getch();
}

void swap(int i,int j)
{
int c,k;
c=a[j];
for(k=j;k>i;k--)
a[k]=a[k-1];
a[i]=c;
}

void arrange(int arr[],int len)
{
int i;
int posIndex=0;
int negIndex=0;
int cur;
for (i=0; i<len; i++)
{
if( ((i % 2) == 0) && (arr[i]>0)) //looking for negative number
{
if (negIndex > i)
cur=negIndex+1;
else
cur =i+1;

while(cur<len && arr[cur]>0)
cur++;

if (cur == len)
break;
else
{
negIndex=cur;
int tmp=arr[i];
arr[i]=arr[cur];
arr[cur]=tmp;
}
}
else if ( ((i % 2) == 1) && (arr[i]<0)) //looking for pos number
{
if (posIndex > i)
cur=posIndex+1;
else
cur =i+1;

while(cur<len && arr[cur]<0)
cur++;

if (cur == len)
break;
else
{
posIndex=cur;
int tmp=arr[i];
arr[i]=arr[cur];
arr[cur]=tmp;
}
}
}
}

public class AlternateSign {

	static int negative;
	static int positive;
	
	private static void alter(int[] a,int index){
		
		if(index>=a.length)
			return;
		
		if(a[index]<0 && a[index+1]>0)
		{
			negative--;
			positive--;
			alter(a,index+2);
		}
		else
		{
			if(negative==0 || positive==0)
				return;
			
			else{
				for(int i=index+2;i<a.length;i++){
					
					if(a[index]<0 && a[index+1]>0)
						break;
					
				if(a[index]>0 && a[i]<0)
				{
					int t=a[i];
					a[i]=a[index];
					a[index]=t;
				}
				
				if(a[index+1]<0 && a[i]>0)
				{
					int t=a[i];
					a[i]=a[index+1];
					a[index+1]=t;
				}
				
				}
				negative--;
				positive--;

				alter(a,index+2);
			}
		}		
	}
	
	public static void main(String[] args){
		int[] ar=new int[]{-1,-2,4,-2,-6,5,6,-3,9,-8,-5,};
		
		for(int i=0;i<ar.length;i++)
		{
			if(ar[i]<0)
				negative++;
			else
				positive++;
		}
		
		alter(ar,0);
		
		for(int i=0;i<ar.length;i++)
			System.out.print(ar[i]+" ");
	}
}

public class ArrayRearrange {
static void rotate(int a[], int i, int j) {
int k, m;
m = a[j];
for (k = j; k > i; k--)
a[k] = a[k - 1];
a[i] = m;
return;
}

static void rearrange(int a[], int n) {
int i, j;
for (i = 0; i < n; i++) {
if (i % 2 == 0) {
if (a[i] < 0)
continue;
else {
j = i;
while (j <= n && a[j] >= 0)
j++;
if (j == n + 1)
break;
rotate(a, i, j);
}
} else {
if (a[i] >= 0)
continue;
else {
j = i;
while (j <= n && a[j] < 0)
j++;
if (j == n + 1)
break;
rotate(a, i, j);
}
}
}
return;
}

public static void main(String args[]) {
int i;
int a[] = { -1, -3, -6, -7,-4, 8, 1, 3, 4, 5, 9, 10 };
System.out.println("Array before Rearangment");
for (int j = 0; j < a.length; j++){
System.out.print(" " +a[j]);
}
rearrange(a, a.length - 1);
System.out.println(" \nArray After Rearangment");
for (i = 0; i < a.length; i++){
System.out.print(" " +a[i]);
}

}

}