CareerCup

This problem can be solved by modified Dutch National Flag problem.
Instead of '0' we have -ve numbers
Instead of '1' we have 0's(zero).
and for 2 we have +ve Numbers.
------------------------------------------
So modified algo will be

void swap(int *a, int *b)
{
	int c;
	c = *a;
	*a = *b;
	*b = c;
}
void sortNumbers(int *arr, int len)
{
	int low=0,mid=0,high=len-1;
	while(mid <= high)
	{
		if(arr[mid]<0)
			swap(&arr[low++],&arr[mid++]);
		else if(arr[mid]==0)
			mid++;
		else
			swap(&arr[mid], &arr[high--]);
	}	
}

In single parse:

#include <stdio.h>
#include <stdlib.h>

int main()
{
	int *arr, n, i, j, k;
	scanf("%d", &n);
	arr = (int *)malloc(sizeof(int)*n);

	for(i = 0; i < n; i++)
		scanf("%d", &arr[i]);
	
	i = -1;
	k = n;
	
	for(j = 0; j < k; j++)
	{
		if(arr[j] > 0)
		{
			int temp;
			k--;
			temp = arr[j];
			arr[j] = arr[k];
			arr[k] = temp;
			j--;
		}
		else if(arr[j] < 0)
		{
			int temp;
			i++;
			temp = arr[j];
			arr[j] = arr[i];
			arr[i] = temp;
		}
	}

	printf("\n");
	for(i = 0; i < n; i++)
		printf(" %d ", arr[i]);

	return 0;
}

/*
* This has a runtime of O(n).
* Places all the negative no on the left side.
* All the positive no on the right side.
* And all the zeroes in the middle.
*/
public int[] arrangeArray(int[] arr) {
int[] res = new int[arr.length];
int left = 0;
int right = arr.length - 1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) {
res[left] = arr[i];
left++;
} else if (arr[i] > 0) {
res[right] = arr[i];
right--;
}
}
return res;
}

public static void divide_neg_0_pos(int [] test){
int neg_hold=-1;
int pos_hold=test.length;
int current=0;
while(current!=pos_hold){
if(test[current]>0){
exChange(test,current,--pos_hold);
continue;
}
if(test[current]<0){
if(current==neg_hold){
current++;
continue;
}
exChange(test,current,++neg_hold);

}
if(test[current]==0){
current++;
}
}
}

Solution 1:

void swap(int* a, int i, int j)
{
    if (i >= j)
        return;

    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

void print(int * a, int len)
{
    for (int i = 0; i < len; ++i)
        printf("%3d  ", a[i]);
}


    
int main()
{
    int arr[] = {-12, -11, 12, 0, 11, -10, 10, 9, 8, -8, 7, 0, 0 , -9, -7};
    int start = 0;
    int mid = 0;
    int len = sizeof(arr) / sizeof(arr[0]);
    int end = len - 1;

    print(arr, len);
    printf("\n");

    while (mid <= end)
    {
        if (arr[mid] < 0)
            swap(arr, start++, mid++);
        else if (arr[mid] == 0)
            mid++;
        else
            swap(arr, mid, end--);

    }

    print(arr, len);
    printf("\n");
    return 0;
}

Solution 2:

void swap(int* a, int i, int j)
{
    if (i >= j)
        return;

    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

void print(int * a, int len)
{
    for (int i = 0; i < len; ++i)
        printf("%3d  ", a[i]);
}


    
int main()
{
    int arr[] = {-12, -11, 12, 0, 11, -10, 10, 9, 8, -8, 7, 0, 0 , -9, -7};
    int start = 0;
    int len = sizeof(arr) / sizeof(arr[0]);
    int end = len - 1;

    print(arr, len);
    printf("\n");

    while (start < end)
    {
        while (arr[start] < 0)
            ++start;

        while (arr[end] >= 0)
            --end;
    
        swap(arr, start, end);
    }

    print(arr, len);
    printf("\n");
    while (arr[start] >= 0)
        --start;

    ++start;
    end = len - 1;

    while (start < end)
    {
        while (!arr[start])
            ++start;

        while (arr[end] > 0)
            --end;
    
        swap(arr, start, end);
    }
    print(arr, len);
    return 0;
}

Here is my one pass algorithm:
let ptr_left points to the left end of the array a[] and ptr_right points to the right end
let nzero_left is the counts of zero from left sides; nzero_right for right side

nzero_left=0; nzero_right=0;
while (ptr_left<=ptr_right)
{{

if (a[ptr_left]==positive and
a[ptr_right]==negative)
swap a[ptr_left] and a[ptr_right]

if a[ptr_left] is negative
{
if nzero_left>0:
shift 0 toward the center of array by letting
a[ptr_left-nzero_left]= a[ptr_left]; a[ptr_left]=0;
ptr_left++;
}
else if a[ptr_left] is zero
{
increase nzero_left by 1
ptr_left++;
}

similarly,

if a[ptr_right] is positive
{
if nzero_right>0:
shift 0 toward the center of array by letting
a[ptr_right-nzero_right]= a[ptr_right]; a[ptr_right]=0;
ptr_right--;
}
else if a[ptr_right] is zero
{
increase nzero_right by 1
ptr_right--;
}



}}

eventually, ptr_left and ptr_right meet somewhere in middle,

If we could use another array for result, shivam maharshi's code above seems to be doing good. In case we are not allowed to use extra array, following code works fine :


public class testing {

public static void main(String[] args) {
int a[]={-5,6,-9,0,-2,0,4,-3};
sortArray(a);
}

static void sortArray(int[] a)
{
int negativeTracker=0, positiveTracker=a.length-1;

while(negativeTracker<=positiveTracker) {
if(a[negativeTracker] < 0)
negativeTracker++;
else {
if(a[positiveTracker] >= 0)
positiveTracker--;
else {
swap(a, negativeTracker, positiveTracker);
negativeTracker++;
positiveTracker--;
}
}
}

int zeroTracker = 0;
if(positiveTracker < a.length-2) {
zeroTracker = positiveTracker+1;
positiveTracker = a.length-1;

while(zeroTracker<positiveTracker) {
if(a[zeroTracker] == 0)
zeroTracker++;
else {
if(a[positiveTracker] > 0)
positiveTracker--;
else {
swap(a, zeroTracker, positiveTracker);
zeroTracker++;
positiveTracker--;
}
}
}
}

printArray(a);
}

static void swap(int a[], int from, int to)
{
int temp=a[from];
a[from]=a[to];
a[to]=temp;
}


static void printArray(int[] y) {
for(int a:y) {
System.out.print(a + " : ");
}
System.out.println();
}
}

public static void quickPartition(int array[])
    {
        int nPtr=0, pPtr=array.length-1;
        for(int i=0; i<pPtr; i++)
        {
            if(array[i]<0)
            {
                biSwap(array, nPtr, i);
                nPtr++;
            }
            else if(array[i]>0)
            {
                biSwap(array, pPtr, i);
                i--;
                pPtr--;
            }
        }
    }

public void DutchFlag(int[] numbers)
        {
            int low = 0;
            int current = 0;
            int high = numbers.Length - 1;

            while (current <= high)
            {
                if (numbers[current] > 0)
                {
                    swap(numbers, current, high);
                    high--;
                }
                else if (numbers[current] < 0)
                {
                    swap(numbers, current, low);
                    low++;
                    current++;
                }
                else
                {
                    current++;
                }
            }

        }

        public void swap(int[] array, int first, int second)
        {
            int temp;
            temp = array[first];
            array[first] = array[second];
            array[second] = temp;
        }

Use Bucket sort...

#include<stdio.h>
int main()
{
	int arr[20],i,n,j,temp;
	printf("enter value of n");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	scanf("%d",&arr[i]);
	for(i=0;i<n;i++)
	{
		for(j=0;j<n-i-1;j++)
		{
			if(arr[j]>arr[j+1])
			{
				temp=arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=temp;
			}
		}
	}
	for(i=0;i<n;i++)
	printf("%d\t",arr[i]);
	return 0;
}

int main(void)
{
	int a[N] = { 0, 1, -0, 1, 0, -1, -1, 1, 1, -1};
	int i, lo = 0, mid = 0, hi = N-1, tmp;

	while (mid <= hi) {
		if (a[mid] == 1) {
			tmp = a[mid];
			a[mid] = a[hi];
			a[hi] = tmp;
			--hi;
		}
		else if (a[mid] == -1) {
			tmp = a[lo];
			a[lo] = a[mid];
			a[mid] = tmp;
			++lo; ++mid;
		}
		else
			++mid;
	}
}

I gave the following answer (didn't get through, help me figure out if I did something wrong)

void group(int[] arr) {
    int begin = 0, end = arr.length;
    while(begin<end) {
		/* group all positive together at the end*/
		if(arr[begin]>0) {
			int temp = arr[begin];
            arr[begin] = arr[end];
            arr[end] = temp;	
			end--;
        } else {
			begin++;
		}
    }
	/* At the end of previous loop, end will contain the first index of negative number */
	end--; //This will contain the end-index of sub-array where +ve and zeros are mixed
	begin = 0;
    while(begin<end) {
		/* group all zero together at the end*/
		if(arr[begin]==0) {
			int temp = arr[begin];
            arr[begin] = arr[end];
            arr[end] = temp;	
			end--;
        } else {
			begin++;
		}
    }	
}

Sorting is nlog(n), but there's a linear solution. Not sure if this is optimal, but here's a two pass algorithm that first swaps positive/zero numbers from left to right with negative numbers, and then a similar pass for zeros:

void partition(vector<int>& input) {
  int next_to_swap = 0;
  int ix = 1;
  int last_negative = -1;
  while (ix < input.size() && next_to_swap < input.size()) {
    if (input[next_to_swap] < 0) { next_to_swap++; continue; }
    if (input[ix] < 0) {
      std::swap(input[ix], input[next_to_swap]);
      last_negative = next_to_swap;
    }
    ix++;
  }
  next_to_swap = last_negative+1;
  ix = next_to_swap+1;
  while (ix < input.size() && next_to_swap < input.size()) {
    if (input[next_to_swap] == 0) { next_to_swap++; continue; }
    if (input[ix] == 0) std::swap(input[ix], input[next_to_swap]);
    ix++;
  }
}

Here is the a possible solution for this:

void Lineararrange(int X[]){
		this.X=X;
		int i=0,j=0;
		int m=X.length-1,n;
		while(i<X.length){
			//Increase i as long as found negative
			while(X[i]<0 && i<X.length)i++;
			//Set j=i+1
			j=i+1;//X[j] is either 0 or positive
			//increase j as long as another negative is not found
			while(j<X.length && X[j]>=0){j++;}
			//if j=length finish
			if(j>=X.length){
				break;
			}
			//else swap with X[i],increase i
			else{
				int temp=X[i];
				X[i]=X[j];
				X[j]=temp;
			}
		}
		//Now we have all negative to the left of i
		while(m>0){
			//Decrease m as long as found positive
			while(X[m]>0 && m>0)m--;
			//Set n=m-1
			n=m-1;//X[n] is either 0 or negative
			//decrease n as long as another positive is not found
			while(n>=0 && X[n]<=0 ){n--;}
			if(n<=0){
				break;
			}

			//if n=0 finish
			
			//else swap with X[m],decrease m
			else{
				int temp=X[m];
				X[m]=X[n];
				X[n]=temp;
			}
		}
		//Now we have all positive to the right of m
		output();
	}
public void output(){
		for(int i=0;i<X.length;i++){
			System.out.print(X[i]+",");
		}
	}

take zero as pivot element. nd traverse once.compare all elements with zero. anythin less than zero will come to the left and anythin greater than zero will come to the right of zero.. so basically partition around zero.

#include<stdio.h>
#define SIZE 9
void arrange(int[]);
void swap(int[],int,int);
int main()
{
int array1[SIZE]={-3,1,2,3,0,0,-2,-3,0};
arrange(array1);
int i=0;
for(;i<SIZE;i++)
{
printf("%d\t",array1[i]);
}
getchar();
return 0;
}
void arrange(int array1[])
{
int i = 0;
int first = 0,last = SIZE-1;
while(array1[i] <0)
{
i++;
}
while(i<=last)
{
if(array1[i]==0)
{
i++;
}
else
{
if(array1[i]>0)
{
swap(array1,i,last);
last--;
}
else
{
swap(array1,i,first);
first++;
}
}
}
}
void swap(int array1[ ],int first,int second)
{

int temp = array1[first];
array1[first]=array1[second];
array1[second]=temp;

}

int _tmain(int argc, _TCHAR* argv[])
{
int arr[9] = { 0,0,-1,-1,2,2,0,-2,2};
int startIndex =0;
int EndIndex = 8;
int tmp;
int i =0;
while ( startIndex < EndIndex )
{
if (arr[startIndex] < 0)
{
tmp = arr[i];
arr[i++] = arr[startIndex];
arr[startIndex] = tmp;
}
if (arr[startIndex] > 0 )
{
tmp = arr[startIndex];
arr[startIndex] = arr[EndIndex];
arr[EndIndex--] = tmp;
}
if (arr[startIndex] == 0)
{
startIndex++;
}
}
return 0;
}

What about first having 3 variables that will count the no of positive, negative & 0 values once u had that in the second pass u just have to set values in the second pass

well, since it doesn't say we cannot have an extra array. I will just create an extra array with the same size and initialize to 0.
Then I will scan through the given array, if it's less than 0, then put it at the front (say, a counter that starts at 0). If it's greater than 0, then put it at the end (have a counter that starts at n-1).
It should be done after the first pass since it's initialized to 0's already, so the middle ones are all 0's.

public class NegPosArray {
	public static int[] partitionArray(int[] array) {
		int[] result = new int[array.length];
		int leftCount = 0;
		int rightCount = array.length - 1;
		for (int i = 0; i < array.length; i++) {
			if (array[i] < 0) {
				result[leftCount] = array[i];
				leftCount++;
			} else if (array[i] > 0) {
				result[rightCount] = array[i];
				rightCount--;
			}
		}
		return result;
	}

	public static void main(String args[]) {
		int[] arr = { 1, 2, -4, 0, 0, 2, 3, 7, -6, -13, 5, 8, 0, 2, -5, 3, -2,
				5, -16, 0, -23, -25, -6, 1, 0, 0 };
		int[] res = partitionArray(arr);

		for (int i = 0; i < res.length; i++) {
			System.out.print(res[i] + " ");
		}
	}
}

The result is

-4 -6 -13 -5 -2 -16 -23 -25 -6 0 0 0 0 0 0 1 5 3 2 8 5 
7 3 2 2 1

void arrange(int *a,int n)
{
   int negative_right_end=0;
   int positive_left_end=n-1;
   for(int i=0; (i<n || i>positive_left_end);)
  {
     if(a[i]==0) 
        i++;
    else if(a[i]==-1)
       {
         swap(a[i],a[negative_right_end]);
         negative_right_end++;
       }
      else if(a[i]==1)
      {
        swap(a[i],a[positive_left_end]);
        positive_left_end--;
      }
   }
}

It is similar to Dutch Nation Flag problem:

Just imagine negatives numbers as 0, zeroes as 1 and positive numbers as 2. Then the problem is to sort the array containing only 0, 1, 2.

Dutch nation flag problem code:

Lo := 1; Mid := 1; Hi := N;
while Mid <= Hi do
Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and a[Hi+1..N]=2; a[Mid..Hi] are unknown.
case a[Mid] in
0: swap a[Lo] and a[Mid]; Lo++; Mid++
1: Mid++
2: swap a[Mid] and a[Hi]; Hi--

So for the above problem:

switch cases will be if arr[mid] <0 arr[mid] ==0 and arr[mid]>0

1.get two pointer for head and tail,
2.trace the array from the beginning,
3.if the pointer see a negative number swap with head and if is positive swap with tail
4. move to next item until hit the tail

int[] sortArray(int[] T)
{
int i=0, head = 0;
int tail=T.length()-1;
while(i<=tail)
{
  if(T[i]<0) {
      int tmp=T[head];
      T[head++]=T[i];
      T[i]=tmp;
  }
  else if (T[i]>0) {
     int tmp = T[tail];
     T[tail--]=T[i];
     T[i--]=tmp;
  }
  i++;
}
return T;
}