Distributing 0s and 1s in even and odd positions

Given an array of 0s and 1s, write an algo such that,
- the 0s will occupy the even positions.
- the 1s will occupy the odd positions.
- any extra 0s or 1s should be placed at the end of array
Complexity: linear, in a single pass

Answer:


#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;

//
// 1 0 1 0 1 1 1
// i j --> move by step of 2
void Distribute0s1s(vector& a, size_t n)
{
size_t i = 0, // i will point to the even indices
j = i+1; // j will point to the odd indices
for ( ; (i < n) && (j < n) ; )
{
// already 0 in even position, move ahead
if ( a[i] == 0 )
{
i += 2;
}

// already 1 in odd position, move ahead
if ( a[j] == 1 )
{
j += 2;
}

if ( i >=n ) break;
if ( j >=n ) break;

// 1 in even pos, 0 in odd pos, swap
if ( a[i] && !a[j] )
{
swap( a[i], a[j] );
i += 2;
j += 2;
}
}

if ( i < n )
{
// At this point, all the odd positions are enused with
// 1s
j = i + 2;
}
else if ( j < n )
{
// At this point, all the even positions are enused with
// 0s
i = j;
j = i + 2;
}

// handle the remaining numbers
while ( j < n )
{
if (
( ( i % 2 == 0 ) && ( a[j] < a[i] ) ) ||
( ( i % 2 == 1 ) && ( a[j] > a[i] ) )
)
{
swap( a[j], a[i] );
i += 2;
}
j += 2;
}
}

int main( int argc, char* argv[] )
{
if ( argc == 1 ) return 0;
else
{
vector a(argc-1);
for ( int i = 1; i <= argc-1; ++i)
a[i-1] = atoi(argv[i]);
cout << "Input :" << endl;
copy ( a.begin(), a.end(), ostream_iterator(cout, " "));
cout << endl << "Output :" << endl;
Distribute0s1s(a, a.size() );
copy ( a.begin(), a.end(), ostream_iterator(cout, " "));
}
return 0xabcdef;

}

No comments: