kaushikmtc
BAN USERpublic static void Segregrate(int[] a)
{
bool isPositiveBlock;
//first rule out case of all positive or all -ve integers
int j = getContigousBlock(a, 0, out isPositiveBlock);
if((j==-1) || (j==a.Length-1) )
return;
int i = 0;
if (!isPositiveBlock)
{
i = j + 1;
j = getContigousBlock(a, i, out isPositiveBlock);
}
// Invariant: i is the begining of the +ve block and j the end of the positive block and if we enter forsure there
//is a -ve block starting at j+1
while(j<a.Length-1 && (j>=0))
{
int k = getContigousBlock(a, j+1, out isPositiveBlock); // k is the end of the negative block
if (isPositiveBlock) // invariant is broken something wrong with algo as we must get negative block
throw new Exception("invariant is broken something wrong with algo as we must get negative block");
MovePositivestoEndOfBlock(a, i, j, k);
i = i+k-j; // number of negative integers being k-j which are now shifted and starts from i+k-j and does not end at k but goes beyond
j = getContigousBlock(a, k + 1, out isPositiveBlock);
if (j!=-1 && !isPositiveBlock) // invariant is broken something wrong with algo we must get a positive block
throw new Exception("invariant is broken something wrong with algo we must get a positive block ");
}
}
- kaushikmtc December 25, 2014public static void Segregrate(int[] a)
{
bool isPositiveBlock;
//first rule out case of all positive or all -ve integers
int j = getContigousBlock(a, 0, out isPositiveBlock);
if((j==-1) || (j==a.Length-1) )
return;
int i = 0;
if (!isPositiveBlock)
{
i = j + 1;
j = getContigousBlock(a, i, out isPositiveBlock);
}
// Invariant: i is the begining of the +ve block and j the end of the positive block and if we enter forsure there
//is a -ve block starting at j+1
while(j<a.Length-1 && (j>=0))
{
int k = getContigousBlock(a, j+1, out isPositiveBlock); // k is the end of the negative block
if (isPositiveBlock) // invariant is broken something wrong with algo as we must get negative block
throw new Exception("invariant is broken something wrong with algo as we must get negative block");
MovePositivestoEndOfBlock(a, i, j, k);
i = i+k-j; // number of negative integers being k-j which are now shifted and starts from i+k-j and does not end at k but goes beyond
j = getContigousBlock(a, k + 1, out isPositiveBlock);
if (j!=-1 && !isPositiveBlock) // invariant is broken something wrong with algo we must get a positive block
throw new Exception("invariant is broken something wrong with algo we must get a positive block ");
}
}
public static void Segregrate(int[] a)
{
bool isPositiveBlock;
//first rule out case of all positive or all -ve integers
int j = getContigousBlock(a, 0, out isPositiveBlock);
if((j==-1) || (j==a.Length-1) )
return;
int i = 0;
if (!isPositiveBlock)
{
i = j + 1;
j = getContigousBlock(a, i, out isPositiveBlock);
}
// Invariant: i is the begining of the +ve block and j the end of the positive block and if we enter forsure there
//is a -ve block starting at j+1
while(j<a.Length-1 && (j>=0))
{
int k = getContigousBlock(a, j+1, out isPositiveBlock); // k is the end of the negative block
if (isPositiveBlock) // invariant is broken something wrong with algo as we must get negative block
throw new Exception("invariant is broken something wrong with algo as we must get negative block");
MovePositivestoEndOfBlock(a, i, j, k);
i = i+k-j; // number of negative integers being k-j which are now shifted and starts from i+k-j and does not end at k but goes beyond
j = getContigousBlock(a, k + 1, out isPositiveBlock);
if (j!=-1 && !isPositiveBlock) // invariant is broken something wrong with algo we must get a positive block
throw new Exception("invariant is broken something wrong with algo we must get a positive block ");
}
}
- kaushikmtc December 25, 2014This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and The code in c#
public static void Segregrate(int[] a)
{
bool isPositiveBlock;
//first rule out case of all positive or all -ve integers
int j = getContigousBlock(a, 0, out isPositiveBlock);
if((j==-1) || (j==a.Length-1) )
return;
int i = 0;
if (!isPositiveBlock)
{
i = j + 1;
j = getContigousBlock(a, i, out isPositiveBlock);
}
// Invariant: i is the begining of the +ve block and j the end of the positive block and if we enter forsure there
//is a -ve block starting at j+1
while(j<a.Length-1 && (j>=0))
{
int k = getContigousBlock(a, j+1, out isPositiveBlock); // k is the end of the negative block
if (isPositiveBlock) // invariant is broken something wrong with algo as we must get negative block
throw new Exception("invariant is broken something wrong with algo as we must get negative block");
MovePositivestoEndOfBlock(a, i, j, k);
i = i+k-j; // number of negative integers being k-j which are now shifted and starts from i+k-j and does not end at k but goes beyond
j = getContigousBlock(a, k + 1, out isPositiveBlock);
if (j!=-1 && !isPositiveBlock) // invariant is broken something wrong with algo we must get a positive block
throw new Exception("invariant is broken something wrong with algo we must get a positive block ");
}
}
- kaushikmtc December 25, 2014This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence
- kaushikmtc December 25, 2014This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence
- kaushikmtc December 25, 2014This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence
- kaushikmtc December 25, 2014
- kaushikmtc December 26, 2014