Here is a C++ version of the algorithm to solve this problem.
#include <iostream>
#define TRUE 1
#define FALSE 0
typedef struct Binarr{
int iNumber;
};
class binaryarr{
Binarr * arr;
public:
int iHead;
int iSize;
int iZeroes;
int iOnes;
int iTail;
binaryarr(void);
~binaryarr(void);
bool Rearrange(void);
bool IsOdd(int iNumber);
bool IsZero(int iNumber);
bool SwapElements(int iUnexpected, int iCurrTail, int iExpected);
bool ZeroOneBalanced(void);
void Display(void);
};
void binaryarr:: Display(void){
std::cout << std::endl << "Contents of the arr are";
for(int j=0; j<iSize;j++)
std::cout << std::endl<< arr[j].iNumber;
}
bool binaryarr:: ZeroOneBalanced(void){
int iTotal = -1;
iTotal = iOnes + iZeroes;
if (iTotal == iSize && iOnes != iZeroes){
std::cout << std::endl<<"Number of Ones =
"<<iOnes<<std::endl<<"Number of Zeros = "<<iZeroes;
return FALSE; // done or error occurred.
}
return TRUE;
}
// Builds the arr
binaryarr::binaryarr(void){
int iIndex = 0;
std::cout << "Enter the size of the arr\n";
std::cin >> iSize;
if(iSize != 0){
if ((iSize % 2) == 0)
{
std::cout << std::endl<<"Enter each zero or one and press
enter"<<std::endl;
arr = (Binarr *) malloc(iSize-1);
for (iIndex = 0 ; iIndex < iSize ; iIndex ++ )
std::cin >> arr[iIndex].iNumber;
iHead = 0;
iTail = iSize-1;
iZeroes = 0;
iOnes = 0;
}
else
{
std::cout << "The size of the arr cant fit equal number of zeros
and ones\n";
iHead = -1;
}
}
else
{
std::cout << "The size of the arr cant fit equal number of zeros
and ones\n";
iHead = -1;
}
}
// Free the memory
binaryarr::~binaryarr(void){
/*if (iHead != -1)
free(arr);*/
}
// is the given number odd or even
bool binaryarr::IsOdd(int iNumber){
if ( (iNumber == 0 ) )
return TRUE;
else
if (( (iNumber % 2) == 0 ) && (iNumber!=1) )
return TRUE;
else
return FALSE;
}
// is the given number zero or one
bool binaryarr::IsZero(int iNumber){
if (arr[iNumber].iNumber == 0){
iZeroes = iZeroes + 1;
return TRUE;
}
else
{
iOnes = iOnes + 1;
return FALSE;
}
}
bool binaryarr:: SwapElements(int iUnexpected, int iCurrTail, int
iExpected){
int iTemp = -1;
int iFound = -1;
/*while !((IsZero(iUnexpected)) && iExpected){
iCurrTail = iCurrTail - 1;
iFound = 1;
}*/
for (int iDecr = iCurrTail; iDecr >= iUnexpected; iDecr--)
{
if((IsZero(iDecr)) && (iExpected == 0) || (!(IsZero(iDecr))) &&
(iExpected == 1))
{
iFound = 1;
iTail = iDecr; // Reposition current tail.
iTemp = arr[iUnexpected].iNumber;
arr[iUnexpected].iNumber = arr[iDecr].iNumber;
arr[iDecr].iNumber = iTemp;
return TRUE;
}
}
//
if ((iFound == -1) || (iOnes != iZeroes))
{
std::cout << std::endl << "binaryarr:: SwapElements: Mismatch or
mismatch in num of zeros : ones. Expected = "<<iExpected<<".Unexpected =
"<<arr[iUnexpected].iNumber;
return FALSE;
}
}
// sort the input arr such that every odd position has a 1 and even position
a zero.
bool binaryarr::Rearrange(void){
for (iHead = 0; iHead < iTail; iHead++) {
if (IsOdd(iHead)) // Determine if the position on the arr is ODD
{
if (IsZero(iHead)) // Position is odd; but a zero encountered
{
/*if (iTail == iHead)
iTail = iTail +1;*/
// Expected is 1.
if (!(SwapElements(iHead,iTail, 1))) {
std::cout << std::endl <<"No matching element found for
element @:"<<iHead;
return FALSE;
}
else
std::cout << std::endl <<"Successfully swapped between
"<<iHead<<" & "<<iTail;
}
// arr head is 1
}
else // position is even
{
if (!(IsZero(iHead)))
{
if (!(SwapElements(iHead,iTail, 0))) {
std::cout << std::endl <<"No matching element found for
element @:"<<iHead;
return FALSE;
}
else
std::cout << std::endl <<"Successfully swapped between
"<<iHead<<" & "<<iTail;
}
// arr head is 0
}
}
Display();
if (!(ZeroOneBalanced()))
return FALSE;
return TRUE;
}
int main (int argc, char * const argv[]) {
binaryarr test;
if (test.iHead == -1)
std::cout << std::endl<<"Error:Number of zeros and ones cannot be
equal with this size of arr";
else
{
if (!(test.Rearrange()))
std::cout << std::endl << "Rearrange failed";
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
