Problem Statement:

-------------------

An array of size n among which there are n/2 0s and n/2 1s arranged in random order.

Arrange all the 1s to left and all 0s to right but it needs to be

stable i.e., the order of 1s and 0s in the i/p array should be maintained.

Expected Complexity:

--------------------------------

O(N) with constant space.

Pseudocode:

--------------------

1. Have two counters, count1 = 0 and count2 = (n/2)+1

2. Traverse thru the array, if(arr[ i ] == 1) { arr[ i ] = count1++;} else { arr[ i ] = count2++ };

3. At the end of the traversal, you have array filled with numbers 0 to n-1

Now the problem reduces to sorting and array of n numbers which has elements from 0 to

n-1 occuring only once which can be done in O(n).

-------------------

An array of size n among which there are n/2 0s and n/2 1s arranged in random order.

Arrange all the 1s to left and all 0s to right but it needs to be

stable i.e., the order of 1s and 0s in the i/p array should be maintained.

Expected Complexity:

--------------------------------

O(N) with constant space.

Pseudocode:

--------------------

1. Have two counters, count1 = 0 and count2 = (n/2)+1

2. Traverse thru the array, if(arr[ i ] == 1) { arr[ i ] = count1++;} else { arr[ i ] = count2++ };

3. At the end of the traversal, you have array filled with numbers 0 to n-1

Now the problem reduces to sorting and array of n numbers which has elements from 0 to

n-1 occuring only once which can be done in O(n).

for(j = 0; j <= 1; j++)

{

for(i = 0; i<n; i++)

{

if(arr[ i ] != i)

{

swap(arr[ i ], arr[ arr[ i ] ]);

}

}

}

</pre>

Note: j loop runs only twice irrespective on 'n' and has constant complexity. The order of this whole loop is 2*n = O(n).

4. After the array is sorted, Again traverse thru the array and make elements arr[0] to

arr[n/2] to '1' and arr[(n/2)+1] to arr[n] as '0'.

Space complexity is constant and time complexity is O(step2) + O(step3) + O(step4) = n + 2n +n = 4*n = O(n).

Solution #1 (Stable):

------------------------

<pre name='code' class='cpp'>

#include<iostream.h>

int a[] = { 1,0,0,0,1,1,1,0,0,1};

#define _SIZE sizeof(a)/sizeof(a[0])

/* Helper Function */

void printArray()

{

for(int i=0;i<_SIZE; ++i)

cout<<a[i]<<" ";

cout<<endl;

}

int main()

{

int countOne = 0;

int countZero = (_SIZE)/2;

int i = 0;

/* Fill the array with numbers from 1 to N */

for(i=0; i < _SIZE; ++i)

{

if(a[i] == 1)

{

a[i] = countOne;

countOne++;

}

else

{

a[i] = countZero;

countZero++;

}

}

printArray();

/* Swap the number and make it a sorted one */

for(int j = 0; j< 2; ++j)

{

for(i=0; i < _SIZE; ++i)

{

if(a[i] != i)

{

int temp = a[i];

a[i] = a[a[i]];

a[temp] = temp;

}

}

}

printArray();

/* Fill the 1st N/2 elements with 1 */

for(i=0; i<_SIZE/2; ++i)

a[i] = 1;

/* Fill the last N/2 elements with 1 */

for(i=_SIZE/2; i<_SIZE; i++)

a[i] = 0;

printArray();

return 0;

}

</pre>

Solution #2 (UnStable):

-----------------------------------

Here is a small variation of the quick sort to solve the same problem but this solution is not stable. So I prefer #1.

<pre name='code' class='cpp'>

#include<iostream.h>

using namespace std;

#define _SIZE sizeof(a)/sizeof(a[0])

void swap(int *a, int l, int r)

{

cout<<"Swaping "<<l<<" "<<r<<endl;

if(a[l] != a[r])

a[l] ^= a[r] ^= a[l] ^= a[r];

return;

}

bool compare_1_upper(int *a, int u, int p)

{

return (a[u] == p);

}

bool compare_1_lower(int *a, int l, int p)

{

return (a[l] < p);

}

bool compare_0_upper(int *a, int u, int p)

{

return (a[u] > p);

}

bool compare_0_lower(int *a, int u, int p)

{

return (a[u] == p);

}

bool (*funcPtr_upper)(int *, int, int) = 0;

bool (*funcPtr_lower)(int *, int, int) = 0;

void qPartition(int *a, int low, int upper)

{

int pivot = a[low];

int l = low - 1;

int u = upper + 1;

if(a[low])

{

funcPtr_upper = compare_1_upper;

funcPtr_lower = compare_1_lower;

}

else

{

funcPtr_upper = compare_0_upper;

funcPtr_lower = compare_0_lower;

}

while(1)

{

while(funcPtr_upper(a, --u, pivot));

while(funcPtr_lower(a, ++l, pivot));

if(l<u)

swap(a, l, u);

else

return;

}

return;

}

int a[] = { 1,1,1,1,1,0,0,1};

void print()

{

for(int i=0; i< _SIZE; ++i)

cout<<a[i]<<" ";

cout<<"\n";

}

int main()

{

print();

qPartition(a, 0, _SIZE - 1);

print();

return 0;

}

Hi I read ur algo..............but the statement

ReplyDelete*Now the problem reduces to sorting and array of n numbers which has elements from 0 to

n-1 occuring only once which can be done in O(n).*

make me bit surprised, can v really sort in O(n) time. I guess in fastest we can do in O(n log n)

correct me if m wrong

Thanks

Rajnish