here base index is 1 and total no. of elements are n.
k=1;
i=1;
while(i<n && k<n )
{ if(i%2==0 && a[i]==0)
{i++; continue;}
if( i%2 != 0 && a[i]==1)
{i++; continue;}
if(i%2==0) // if even place is not 0
{ k=i+1;
while(k<n)
{ *if(a[k]==0)*
{ break;
}
k++;
}
if(k<n)
{ swap( a[i]=a[k] );
}
}
else // // if odd place is not 1
{ k=i+1;
while(k<n)
{ *if(a[k]==1)*
{ break;
}
k++;
}
if(k<n)
{ swap( a[i]=a[k] );
}
}
}
Plz check this ,, i thinks it will work
On Sat, Dec 4, 2010 at 5:07 PM, Senthilnathan Maadasamy <
[email protected]> wrote:
> I hope the following approach will work.
> Let 'a' be the input array with size n.
>
> int i = 0, j = 1;
>
> while( true)
> {
> while( i < n && a[i] == 0) i += 2;
> while( j < n && a[j] == 1) j += 2;
>
> if ( i < n && j < n ) swap(a[i], a[j]);
>
> if ( i > n && j < n ) {
> do single pass 2-color sort only on odd indices from j to n-1
> putting 1's before 0's;
> break;
> }
>
> if ( i < n && j > n ) {
> do single pass 2-color sort only on even indices from i to n-1
> putting 0's before 1's;
> break;
> }
> }
>
> Every element of the array is touched exactly once and it is in place.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
*Divesh*
(¨`·.·´¨) Always
`·.¸(¨`·.·´¨ ) Keep
(¨`·.·´¨)¸.·´Smiling!
`·.¸.·´" Life can give u 100's of reason 2cry,but u can give life 1000's
of reasons 2Smile"
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
