Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
@amol : even if your algo wont work for this...until and unless you use
extra space...
but your sorting algo is not working.
On Sun, Jul 1, 2012 at 11:08 PM, Amol Sharma amolsharm...@gmail.com wrote:
i think it has been discussed beforenevertheless here is the required
linear time solution.
first, count the total number 0's and 1's in the array.
let say, total elements are n and there are x zero's.
take count1=0 and count2=x;
traverse through the array :
for(i=0;in;i++)
if(arr[i]==0)
arr[i]=count1++;
else
arr[i]=count2++;
let's say array is {1,0,0,0,1,1,1,0,0,1} n=10,x=5
count1=0;count2=5
after the traversal it becomes a[]={5,0,1,2,6,7,8,3,4,9}
now sort this array in O(n) like this :
for(j=0;j=1;j++)
{
for(i=0;in;i++)
{
if(arr[i]!=i)
swap(arr[i],arr[arr[i]]);
}
}
after the array is sorted again traverse the array and set the elements
from index 0 to x-1 to '0' and rest '1'.
--
Amol Sharma
Final Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99
On Fri, Jun 29, 2012 at 9:20 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@Hassan I think your algo will take time O(n^2) in worst case which
occurs when all elements are negative except the last one
@everyone Can we solve this problem in linear time?
On Fri, Jun 29, 2012 at 9:10 PM, Hassan Monfared hmonfa...@gmail.comwrote:
Hi,
this can be done by simple modification in bubble sort :
void inplace_pos_neg(int pdata[],int sz)
{
bool changed=false;
do
{
changed=false;
for(int i=1;isz;i++)
if(pdata[i-1]0 pdata[i]0)
{
swap(pdata[i-1], pdata[i]);
changed=true;
}
}while(changed);
}
void test_inplace_pos_neg()
{
int a[]={-1,-5,10,11,15,-500,200,-10};
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
inplace_pos_neg(a,sizeof(a)/sizeof(int));
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
}
Regards
On Fri, Jun 29, 2012 at 7:52 PM, utsav sharma
utsav.sharm...@gmail.comwrote:
@bhaskar:- please explain stable sorting algorithm you would use(as
mainly all of them require extra space)
@sourabh:- that previous post discussion does't lead to any correct soln
On Fri, Jun 29, 2012 at 8:39 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@saurabh please provide the link to the post you are mentioning
On Fri, Jun 29, 2012 at 8:38 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
If the order is important then I think we can use any stable sorting
algorithm with the following comparison function
int compare (int a ,int b)
{
if((a0b0)||(a0b0)) return 0;
else return ab;
}
On Fri, Jun 29, 2012 at 3:37 PM, raghavan M
peacelover1987...@yahoo.co.in wrote:
This is a variant of that one
--
*From:* saurabh singh saurab...@gmail.com
*To:* algogeeks@googlegroups.com
*Sent:* Friday, 29 June 2012 3:05 PM
*Subject:* Re: [algogeeks] MS Question: Segregrate positive and
negative nos in array without changing order
duplicate of a previous post.Kindly refer to that post.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Jun 29, 2012 at 10:41 AM, raghavan M
peacelover1987...@yahoo.co.in wrote:
Hi
Question as in subject
*No extra space (can use one extra space)-O(1) max
*No order change allowed
example:
input : 1,-5,2,10,-100,-2
output: -5,-10,-100,1,2
input : -1,-5,10,11,15,-500,200,-10
output : -1,-5,-10,-500,-10,10,11,15
Thanks
Raghavn
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
regards,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
regards,
Bhaskar Kushwaha
Student
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
I think O(N) space or O(nlogn) [stable nlogn sort : like stable merge sort
) time is required.
( I provided O(n^2) time and O(1) space before )
On Mon, Jul 2, 2012 at 10:24 AM, atul anand atul.87fri...@gmail.com wrote:
@amol : even if your algo wont work for this...until and unless you use
extra space...
but your sorting algo is not working.
On Sun, Jul 1, 2012 at 11:08 PM, Amol Sharma amolsharm...@gmail.comwrote:
i think it has been discussed beforenevertheless here is the required
linear time solution.
first, count the total number 0's and 1's in the array.
let say, total elements are n and there are x zero's.
take count1=0 and count2=x;
traverse through the array :
for(i=0;in;i++)
if(arr[i]==0)
arr[i]=count1++;
else
arr[i]=count2++;
let's say array is {1,0,0,0,1,1,1,0,0,1} n=10,x=5
count1=0;count2=5
after the traversal it becomes a[]={5,0,1,2,6,7,8,3,4,9}
now sort this array in O(n) like this :
for(j=0;j=1;j++)
{
for(i=0;in;i++)
{
if(arr[i]!=i)
swap(arr[i],arr[arr[i]]);
}
}
after the array is sorted again traverse the array and set the elements
from index 0 to x-1 to '0' and rest '1'.
--
Amol Sharma
Final Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99
On Fri, Jun 29, 2012 at 9:20 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@Hassan I think your algo will take time O(n^2) in worst case which
occurs when all elements are negative except the last one
@everyone Can we solve this problem in linear time?
On Fri, Jun 29, 2012 at 9:10 PM, Hassan Monfared hmonfa...@gmail.comwrote:
Hi,
this can be done by simple modification in bubble sort :
void inplace_pos_neg(int pdata[],int sz)
{
bool changed=false;
do
{
changed=false;
for(int i=1;isz;i++)
if(pdata[i-1]0 pdata[i]0)
{
swap(pdata[i-1], pdata[i]);
changed=true;
}
}while(changed);
}
void test_inplace_pos_neg()
{
int a[]={-1,-5,10,11,15,-500,200,-10};
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
inplace_pos_neg(a,sizeof(a)/sizeof(int));
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
}
Regards
On Fri, Jun 29, 2012 at 7:52 PM, utsav sharma utsav.sharm...@gmail.com
wrote:
@bhaskar:- please explain stable sorting algorithm you would use(as
mainly all of them require extra space)
@sourabh:- that previous post discussion does't lead to any correct
soln
On Fri, Jun 29, 2012 at 8:39 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@saurabh please provide the link to the post you are mentioning
On Fri, Jun 29, 2012 at 8:38 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
If the order is important then I think we can use any stable
sorting algorithm with the following comparison function
int compare (int a ,int b)
{
if((a0b0)||(a0b0)) return 0;
else return ab;
}
On Fri, Jun 29, 2012 at 3:37 PM, raghavan M
peacelover1987...@yahoo.co.in wrote:
This is a variant of that one
--
*From:* saurabh singh saurab...@gmail.com
*To:* algogeeks@googlegroups.com
*Sent:* Friday, 29 June 2012 3:05 PM
*Subject:* Re: [algogeeks] MS Question: Segregrate positive and
negative nos in array without changing order
duplicate of a previous post.Kindly refer to that post.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Jun 29, 2012 at 10:41 AM, raghavan M
peacelover1987...@yahoo.co.in wrote:
Hi
Question as in subject
*No extra space (can use one extra space)-O(1) max
*No order change allowed
example:
input : 1,-5,2,10,-100,-2
output: -5,-10,-100,1,2
input : -1,-5,10,11,15,-500,200,-10
output : -1,-5,-10,-500,-10,10,11,15
Thanks
Raghavn
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
@atul... can u point out where sorting is not working ? any case ?
--
Amol Sharma
Final Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99
On Mon, Jul 2, 2012 at 12:12 PM, Hassan Monfared hmonfa...@gmail.comwrote:
I think O(N) space or O(nlogn) [stable nlogn sort : like stable merge sort
) time is required.
( I provided O(n^2) time and O(1) space before )
On Mon, Jul 2, 2012 at 10:24 AM, atul anand atul.87fri...@gmail.comwrote:
@amol : even if your algo wont work for this...until and unless you use
extra space...
but your sorting algo is not working.
On Sun, Jul 1, 2012 at 11:08 PM, Amol Sharma amolsharm...@gmail.comwrote:
i think it has been discussed beforenevertheless here is the
required linear time solution.
first, count the total number 0's and 1's in the array.
let say, total elements are n and there are x zero's.
take count1=0 and count2=x;
traverse through the array :
for(i=0;in;i++)
if(arr[i]==0)
arr[i]=count1++;
else
arr[i]=count2++;
let's say array is {1,0,0,0,1,1,1,0,0,1} n=10,x=5
count1=0;count2=5
after the traversal it becomes a[]={5,0,1,2,6,7,8,3,4,9}
now sort this array in O(n) like this :
for(j=0;j=1;j++)
{
for(i=0;in;i++)
{
if(arr[i]!=i)
swap(arr[i],arr[arr[i]]);
}
}
after the array is sorted again traverse the array and set the elements
from index 0 to x-1 to '0' and rest '1'.
--
Amol Sharma
Final Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99
On Fri, Jun 29, 2012 at 9:20 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@Hassan I think your algo will take time O(n^2) in worst case which
occurs when all elements are negative except the last one
@everyone Can we solve this problem in linear time?
On Fri, Jun 29, 2012 at 9:10 PM, Hassan Monfared
hmonfa...@gmail.comwrote:
Hi,
this can be done by simple modification in bubble sort :
void inplace_pos_neg(int pdata[],int sz)
{
bool changed=false;
do
{
changed=false;
for(int i=1;isz;i++)
if(pdata[i-1]0 pdata[i]0)
{
swap(pdata[i-1], pdata[i]);
changed=true;
}
}while(changed);
}
void test_inplace_pos_neg()
{
int a[]={-1,-5,10,11,15,-500,200,-10};
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
inplace_pos_neg(a,sizeof(a)/sizeof(int));
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
}
Regards
On Fri, Jun 29, 2012 at 7:52 PM, utsav sharma
utsav.sharm...@gmail.com wrote:
@bhaskar:- please explain stable sorting algorithm you would use(as
mainly all of them require extra space)
@sourabh:- that previous post discussion does't lead to any correct
soln
On Fri, Jun 29, 2012 at 8:39 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@saurabh please provide the link to the post you are mentioning
On Fri, Jun 29, 2012 at 8:38 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
If the order is important then I think we can use any stable
sorting algorithm with the following comparison function
int compare (int a ,int b)
{
if((a0b0)||(a0b0)) return 0;
else return ab;
}
On Fri, Jun 29, 2012 at 3:37 PM, raghavan M
peacelover1987...@yahoo.co.in wrote:
This is a variant of that one
--
*From:* saurabh singh saurab...@gmail.com
*To:* algogeeks@googlegroups.com
*Sent:* Friday, 29 June 2012 3:05 PM
*Subject:* Re: [algogeeks] MS Question: Segregrate positive and
negative nos in array without changing order
duplicate of a previous post.Kindly refer to that post.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Jun 29, 2012 at 10:41 AM, raghavan M
peacelover1987...@yahoo.co.in wrote:
Hi
Question as in subject
*No extra space (can use one extra space)-O(1) max
*No order change allowed
example:
input : 1,-5,2,10,-100,-2
output: -5,-10,-100,1,2
input : -1,-5,10,11,15,-500,200,-10
output : -1,-5,-10,-500,-10,10,11,15
Thanks
Raghavn
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
@amol :
#includestdio.h
int main()
{
int arr[]={5,0,1,2,6,7,8,3,4,9};
int i,j,n,temp;
n=sizeof(arr)/sizeof(arr[0]);
for(j=0;j=1;j++)
{
for(i=0;in;i++)
{
if(arr[i]!=i){
temp=arr[i];
arr[i]=arr[arr[i]];
arr[arr[i]]=temp;
}
}
}
for(i=0;in;i++)
printf(%d ,arr[i]);
printf(\n);
return 1;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
i don't see any change in the code you posted...other than expanding swap
function
i believe in discussing the idea/algonot the code..
--
Amol Sharma
Final Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99
On Mon, Jul 2, 2012 at 12:59 PM, atul anand atul.87fri...@gmail.com wrote:
@amol :
#includestdio.h
int main()
{
int arr[]={5,0,1,2,6,7,8,3,4,9};
int i,j,n,temp;
n=sizeof(arr)/sizeof(arr[0]);
for(j=0;j=1;j++)
{
for(i=0;in;i++)
{
if(arr[i]!=i){
temp=arr[i];
arr[i]=arr[arr[i]];
arr[arr[i]]=temp;
}
}
}
for(i=0;in;i++)
printf(%d ,arr[i]);
printf(\n);
return 1;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
yes it is same and it not working . Apart for this you had provided code
for sorting O(n) time and not the idea/algo.
please explain the algorithm , how you are sorting it within O(n) time and
O(1) space complexity.
On Mon, Jul 2, 2012 at 3:18 PM, Amol Sharma amolsharm...@gmail.com wrote:
i don't see any change in the code you posted...other than expanding swap
function
i believe in discussing the idea/algonot the code..
--
Amol Sharma
Final Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99
On Mon, Jul 2, 2012 at 12:59 PM, atul anand atul.87fri...@gmail.comwrote:
@amol :
#includestdio.h
int main()
{
int arr[]={5,0,1,2,6,7,8,3,4,9};
int i,j,n,temp;
n=sizeof(arr)/sizeof(arr[0]);
for(j=0;j=1;j++)
{
for(i=0;in;i++)
{
if(arr[i]!=i){
temp=arr[i];
arr[i]=arr[arr[i]];
arr[arr[i]]=temp;
}
}
}
for(i=0;in;i++)
printf(%d ,arr[i]);
printf(\n);
return 1;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
opssyeah dat was the bug... now got it :)
On Mon, Jul 2, 2012 at 4:08 PM, Amol Sharma amolsharm...@gmail.com wrote:
@atul:
the logic for the O(n) counting is same as for the count sort.
you haven't write the swap function correctly,
here is correct code for swap function --
temp=arr[i];
arr[i]=arr[arr[i]];
arr[temp]=temp;
please replace this in your code and it works fine, hope now it's clear.
--
Amol Sharma
Final Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99
On Mon, Jul 2, 2012 at 3:30 PM, atul anand atul.87fri...@gmail.comwrote:
yes it is same and it not working . Apart for this you had provided code
for sorting O(n) time and not the idea/algo.
please explain the algorithm , how you are sorting it within O(n) time
and O(1) space complexity.
On Mon, Jul 2, 2012 at 3:18 PM, Amol Sharma amolsharm...@gmail.comwrote:
i don't see any change in the code you posted...other than expanding
swap function
i believe in discussing the idea/algonot the code..
--
Amol Sharma
Final Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99
On Mon, Jul 2, 2012 at 12:59 PM, atul anand atul.87fri...@gmail.comwrote:
@amol :
#includestdio.h
int main()
{
int arr[]={5,0,1,2,6,7,8,3,4,9};
int i,j,n,temp;
n=sizeof(arr)/sizeof(arr[0]);
for(j=0;j=1;j++)
{
for(i=0;in;i++)
{
if(arr[i]!=i){
temp=arr[i];
arr[i]=arr[arr[i]];
arr[arr[i]]=temp;
}
}
}
for(i=0;in;i++)
printf(%d ,arr[i]);
printf(\n);
return 1;
}
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
i think it has been discussed beforenevertheless here is the required
linear time solution.
first, count the total number 0's and 1's in the array.
let say, total elements are n and there are x zero's.
take count1=0 and count2=x;
traverse through the array :
for(i=0;in;i++)
if(arr[i]==0)
arr[i]=count1++;
else
arr[i]=count2++;
let's say array is {1,0,0,0,1,1,1,0,0,1} n=10,x=5
count1=0;count2=5
after the traversal it becomes a[]={5,0,1,2,6,7,8,3,4,9}
now sort this array in O(n) like this :
for(j=0;j=1;j++)
{
for(i=0;in;i++)
{
if(arr[i]!=i)
swap(arr[i],arr[arr[i]]);
}
}
after the array is sorted again traverse the array and set the elements
from index 0 to x-1 to '0' and rest '1'.
--
Amol Sharma
Final Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99
On Fri, Jun 29, 2012 at 9:20 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@Hassan I think your algo will take time O(n^2) in worst case which occurs
when all elements are negative except the last one
@everyone Can we solve this problem in linear time?
On Fri, Jun 29, 2012 at 9:10 PM, Hassan Monfared hmonfa...@gmail.comwrote:
Hi,
this can be done by simple modification in bubble sort :
void inplace_pos_neg(int pdata[],int sz)
{
bool changed=false;
do
{
changed=false;
for(int i=1;isz;i++)
if(pdata[i-1]0 pdata[i]0)
{
swap(pdata[i-1], pdata[i]);
changed=true;
}
}while(changed);
}
void test_inplace_pos_neg()
{
int a[]={-1,-5,10,11,15,-500,200,-10};
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
inplace_pos_neg(a,sizeof(a)/sizeof(int));
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
}
Regards
On Fri, Jun 29, 2012 at 7:52 PM, utsav sharma
utsav.sharm...@gmail.comwrote:
@bhaskar:- please explain stable sorting algorithm you would use(as
mainly all of them require extra space)
@sourabh:- that previous post discussion does't lead to any correct soln
On Fri, Jun 29, 2012 at 8:39 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@saurabh please provide the link to the post you are mentioning
On Fri, Jun 29, 2012 at 8:38 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
If the order is important then I think we can use any stable sorting
algorithm with the following comparison function
int compare (int a ,int b)
{
if((a0b0)||(a0b0)) return 0;
else return ab;
}
On Fri, Jun 29, 2012 at 3:37 PM, raghavan M
peacelover1987...@yahoo.co.in wrote:
This is a variant of that one
--
*From:* saurabh singh saurab...@gmail.com
*To:* algogeeks@googlegroups.com
*Sent:* Friday, 29 June 2012 3:05 PM
*Subject:* Re: [algogeeks] MS Question: Segregrate positive and
negative nos in array without changing order
duplicate of a previous post.Kindly refer to that post.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Jun 29, 2012 at 10:41 AM, raghavan M
peacelover1987...@yahoo.co.in wrote:
Hi
Question as in subject
*No extra space (can use one extra space)-O(1) max
*No order change allowed
example:
input : 1,-5,2,10,-100,-2
output: -5,-10,-100,1,2
input : -1,-5,10,11,15,-500,200,-10
output : -1,-5,-10,-500,-10,10,11,15
Thanks
Raghavn
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
regards,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
regards,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
@amol :- i don't think this algo would work here
after sorting how would you replace back the original no.s(as no.s are not
0 and 1 in this case)
On Sun, Jul 1, 2012 at 11:08 PM, Amol Sharma amolsharm...@gmail.com wrote:
i think it has been discussed beforenevertheless here is the required
linear time solution.
first, count the total number 0's and 1's in the array.
let say, total elements are n and there are x zero's.
take count1=0 and count2=x;
traverse through the array :
for(i=0;in;i++)
if(arr[i]==0)
arr[i]=count1++;
else
arr[i]=count2++;
let's say array is {1,0,0,0,1,1,1,0,0,1} n=10,x=5
count1=0;count2=5
after the traversal it becomes a[]={5,0,1,2,6,7,8,3,4,9}
now sort this array in O(n) like this :
for(j=0;j=1;j++)
{
for(i=0;in;i++)
{
if(arr[i]!=i)
swap(arr[i],arr[arr[i]]);
}
}
after the array is sorted again traverse the array and set the elements
from index 0 to x-1 to '0' and rest '1'.
--
Amol Sharma
Final Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99
On Fri, Jun 29, 2012 at 9:20 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@Hassan I think your algo will take time O(n^2) in worst case which
occurs when all elements are negative except the last one
@everyone Can we solve this problem in linear time?
On Fri, Jun 29, 2012 at 9:10 PM, Hassan Monfared hmonfa...@gmail.comwrote:
Hi,
this can be done by simple modification in bubble sort :
void inplace_pos_neg(int pdata[],int sz)
{
bool changed=false;
do
{
changed=false;
for(int i=1;isz;i++)
if(pdata[i-1]0 pdata[i]0)
{
swap(pdata[i-1], pdata[i]);
changed=true;
}
}while(changed);
}
void test_inplace_pos_neg()
{
int a[]={-1,-5,10,11,15,-500,200,-10};
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
inplace_pos_neg(a,sizeof(a)/sizeof(int));
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
}
Regards
On Fri, Jun 29, 2012 at 7:52 PM, utsav sharma
utsav.sharm...@gmail.comwrote:
@bhaskar:- please explain stable sorting algorithm you would use(as
mainly all of them require extra space)
@sourabh:- that previous post discussion does't lead to any correct soln
On Fri, Jun 29, 2012 at 8:39 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@saurabh please provide the link to the post you are mentioning
On Fri, Jun 29, 2012 at 8:38 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
If the order is important then I think we can use any stable sorting
algorithm with the following comparison function
int compare (int a ,int b)
{
if((a0b0)||(a0b0)) return 0;
else return ab;
}
On Fri, Jun 29, 2012 at 3:37 PM, raghavan M
peacelover1987...@yahoo.co.in wrote:
This is a variant of that one
--
*From:* saurabh singh saurab...@gmail.com
*To:* algogeeks@googlegroups.com
*Sent:* Friday, 29 June 2012 3:05 PM
*Subject:* Re: [algogeeks] MS Question: Segregrate positive and
negative nos in array without changing order
duplicate of a previous post.Kindly refer to that post.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Jun 29, 2012 at 10:41 AM, raghavan M
peacelover1987...@yahoo.co.in wrote:
Hi
Question as in subject
*No extra space (can use one extra space)-O(1) max
*No order change allowed
example:
input : 1,-5,2,10,-100,-2
output: -5,-10,-100,1,2
input : -1,-5,10,11,15,-500,200,-10
output : -1,-5,-10,-500,-10,10,11,15
Thanks
Raghavn
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
regards,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
regards
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
@amol u have used O(n) extra space!
I think it's not possible without using extra space.
On 7/2/12, Darpan Baweja darpan.bav...@gmail.com wrote:
@amol :- i don't think this algo would work here
after sorting how would you replace back the original no.s(as no.s are not
0 and 1 in this case)
On Sun, Jul 1, 2012 at 11:08 PM, Amol Sharma amolsharm...@gmail.com
wrote:
i think it has been discussed beforenevertheless here is the required
linear time solution.
first, count the total number 0's and 1's in the array.
let say, total elements are n and there are x zero's.
take count1=0 and count2=x;
traverse through the array :
for(i=0;in;i++)
if(arr[i]==0)
arr[i]=count1++;
else
arr[i]=count2++;
let's say array is {1,0,0,0,1,1,1,0,0,1} n=10,x=5
count1=0;count2=5
after the traversal it becomes a[]={5,0,1,2,6,7,8,3,4,9}
now sort this array in O(n) like this :
for(j=0;j=1;j++)
{
for(i=0;in;i++)
{
if(arr[i]!=i)
swap(arr[i],arr[arr[i]]);
}
}
after the array is sorted again traverse the array and set the elements
from index 0 to x-1 to '0' and rest '1'.
--
Amol Sharma
Final Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99
On Fri, Jun 29, 2012 at 9:20 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@Hassan I think your algo will take time O(n^2) in worst case which
occurs when all elements are negative except the last one
@everyone Can we solve this problem in linear time?
On Fri, Jun 29, 2012 at 9:10 PM, Hassan Monfared
hmonfa...@gmail.comwrote:
Hi,
this can be done by simple modification in bubble sort :
void inplace_pos_neg(int pdata[],int sz)
{
bool changed=false;
do
{
changed=false;
for(int i=1;isz;i++)
if(pdata[i-1]0 pdata[i]0)
{
swap(pdata[i-1], pdata[i]);
changed=true;
}
}while(changed);
}
void test_inplace_pos_neg()
{
int a[]={-1,-5,10,11,15,-500,200,-10};
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
inplace_pos_neg(a,sizeof(a)/sizeof(int));
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
}
Regards
On Fri, Jun 29, 2012 at 7:52 PM, utsav sharma
utsav.sharm...@gmail.comwrote:
@bhaskar:- please explain stable sorting algorithm you would use(as
mainly all of them require extra space)
@sourabh:- that previous post discussion does't lead to any correct
soln
On Fri, Jun 29, 2012 at 8:39 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@saurabh please provide the link to the post you are mentioning
On Fri, Jun 29, 2012 at 8:38 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
If the order is important then I think we can use any stable
sorting
algorithm with the following comparison function
int compare (int a ,int b)
{
if((a0b0)||(a0b0)) return 0;
else return ab;
}
On Fri, Jun 29, 2012 at 3:37 PM, raghavan M
peacelover1987...@yahoo.co.in wrote:
This is a variant of that one
--
*From:* saurabh singh saurab...@gmail.com
*To:* algogeeks@googlegroups.com
*Sent:* Friday, 29 June 2012 3:05 PM
*Subject:* Re: [algogeeks] MS Question: Segregrate positive and
negative nos in array without changing order
duplicate of a previous post.Kindly refer to that post.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Jun 29, 2012 at 10:41 AM, raghavan M
peacelover1987...@yahoo.co.in wrote:
Hi
Question as in subject
*No extra space (can use one extra space)-O(1) max
*No order change allowed
example:
input : 1,-5,2,10,-100,-2
output: -5,-10,-100,1,2
input : -1,-5,10,11,15,-500,200,-10
output : -1,-5,-10,-500,-10,10,11,15
Thanks
Raghavn
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
A simple Divide and Conquer strategy can work Well
Seg_pos_neg(A,beg,end) //A is the array
-
mid=beg+end/2
if(begend)
Seg_pos_neg(A,beg,mid)
Seg_pos_neg(A,mid+1,end)
//if leftsubarray contains +ve no and right subarray -ve array,we
swap them
if(A[mid+1]0)
j=mid+1
i=beg
while(A[i]0i=mid)
i++
while(A[j]0i=mid)
swap(A[j],A[i])
-
Running Time O(nlogn)
O(1) space
Correct me if I'm Wrong.
On Mon, Jul 2, 2012 at 7:53 AM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@amol u have used O(n) extra space!
I think it's not possible without using extra space.
On 7/2/12, Darpan Baweja darpan.bav...@gmail.com wrote:
@amol :- i don't think this algo would work here
after sorting how would you replace back the original no.s(as no.s are
not
0 and 1 in this case)
On Sun, Jul 1, 2012 at 11:08 PM, Amol Sharma amolsharm...@gmail.com
wrote:
i think it has been discussed beforenevertheless here is the
required
linear time solution.
first, count the total number 0's and 1's in the array.
let say, total elements are n and there are x zero's.
take count1=0 and count2=x;
traverse through the array :
for(i=0;in;i++)
if(arr[i]==0)
arr[i]=count1++;
else
arr[i]=count2++;
let's say array is {1,0,0,0,1,1,1,0,0,1} n=10,x=5
count1=0;count2=5
after the traversal it becomes a[]={5,0,1,2,6,7,8,3,4,9}
now sort this array in O(n) like this :
for(j=0;j=1;j++)
{
for(i=0;in;i++)
{
if(arr[i]!=i)
swap(arr[i],arr[arr[i]]);
}
}
after the array is sorted again traverse the array and set the elements
from index 0 to x-1 to '0' and rest '1'.
--
Amol Sharma
Final Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99
http://in.linkedin.com/pub/amol-sharma/21/79b/507
http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99
On Fri, Jun 29, 2012 at 9:20 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@Hassan I think your algo will take time O(n^2) in worst case which
occurs when all elements are negative except the last one
@everyone Can we solve this problem in linear time?
On Fri, Jun 29, 2012 at 9:10 PM, Hassan Monfared
hmonfa...@gmail.comwrote:
Hi,
this can be done by simple modification in bubble sort :
void inplace_pos_neg(int pdata[],int sz)
{
bool changed=false;
do
{
changed=false;
for(int i=1;isz;i++)
if(pdata[i-1]0 pdata[i]0)
{
swap(pdata[i-1], pdata[i]);
changed=true;
}
}while(changed);
}
void test_inplace_pos_neg()
{
int a[]={-1,-5,10,11,15,-500,200,-10};
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
inplace_pos_neg(a,sizeof(a)/sizeof(int));
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
}
Regards
On Fri, Jun 29, 2012 at 7:52 PM, utsav sharma
utsav.sharm...@gmail.comwrote:
@bhaskar:- please explain stable sorting algorithm you would use(as
mainly all of them require extra space)
@sourabh:- that previous post discussion does't lead to any correct
soln
On Fri, Jun 29, 2012 at 8:39 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@saurabh please provide the link to the post you are mentioning
On Fri, Jun 29, 2012 at 8:38 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
If the order is important then I think we can use any stable
sorting
algorithm with the following comparison function
int compare (int a ,int b)
{
if((a0b0)||(a0b0)) return 0;
else return ab;
}
On Fri, Jun 29, 2012 at 3:37 PM, raghavan M
peacelover1987...@yahoo.co.in wrote:
This is a variant of that one
--
*From:* saurabh singh saurab...@gmail.com
*To:* algogeeks@googlegroups.com
*Sent:* Friday, 29 June 2012 3:05 PM
*Subject:* Re: [algogeeks] MS Question: Segregrate positive and
negative nos in array without changing order
duplicate of a previous post.Kindly refer to that post.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Jun 29, 2012 at 10:41 AM, raghavan M
peacelover1987...@yahoo.co.in wrote:
Hi
Question as in subject
*No extra space (can use one extra space)-O(1) max
*No order change allowed
example:
input : 1,-5,2,10,-100,-2
output: -5,-10,-100,1,2
input : -1,-5,10,11,15,-500,200,-10
output : -1,-5,-10,-500,-10,10,11,15
Thanks
Raghavn
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
*
while(A[j]0i=mid)
swap(A[j],A[i])
i++
j++
On Mon, Jul 2, 2012 at 8:34 AM, shiva@Algo shiv.jays...@gmail.com wrote:
A simple Divide and Conquer strategy can work Well
Seg_pos_neg(A,beg,end) //A is the array
-
mid=beg+end/2
if(begend)
Seg_pos_neg(A,beg,mid)
Seg_pos_neg(A,mid+1,end)
//if leftsubarray contains +ve no and right subarray -ve array,we
swap them
if(A[mid+1]0)
j=mid+1
i=beg
while(A[i]0i=mid)
i++
while(A[j]0i=mid)
swap(A[j],A[i])
-
Running Time O(nlogn)
O(1) space
Correct me if I'm Wrong.
On Mon, Jul 2, 2012 at 7:53 AM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@amol u have used O(n) extra space!
I think it's not possible without using extra space.
On 7/2/12, Darpan Baweja darpan.bav...@gmail.com wrote:
@amol :- i don't think this algo would work here
after sorting how would you replace back the original no.s(as no.s are
not
0 and 1 in this case)
On Sun, Jul 1, 2012 at 11:08 PM, Amol Sharma amolsharm...@gmail.com
wrote:
i think it has been discussed beforenevertheless here is the
required
linear time solution.
first, count the total number 0's and 1's in the array.
let say, total elements are n and there are x zero's.
take count1=0 and count2=x;
traverse through the array :
for(i=0;in;i++)
if(arr[i]==0)
arr[i]=count1++;
else
arr[i]=count2++;
let's say array is {1,0,0,0,1,1,1,0,0,1} n=10,x=5
count1=0;count2=5
after the traversal it becomes a[]={5,0,1,2,6,7,8,3,4,9}
now sort this array in O(n) like this :
for(j=0;j=1;j++)
{
for(i=0;in;i++)
{
if(arr[i]!=i)
swap(arr[i],arr[arr[i]]);
}
}
after the array is sorted again traverse the array and set the elements
from index 0 to x-1 to '0' and rest '1'.
--
Amol Sharma
Final Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99
http://in.linkedin.com/pub/amol-sharma/21/79b/507
http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99
On Fri, Jun 29, 2012 at 9:20 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@Hassan I think your algo will take time O(n^2) in worst case which
occurs when all elements are negative except the last one
@everyone Can we solve this problem in linear time?
On Fri, Jun 29, 2012 at 9:10 PM, Hassan Monfared
hmonfa...@gmail.comwrote:
Hi,
this can be done by simple modification in bubble sort :
void inplace_pos_neg(int pdata[],int sz)
{
bool changed=false;
do
{
changed=false;
for(int i=1;isz;i++)
if(pdata[i-1]0 pdata[i]0)
{
swap(pdata[i-1], pdata[i]);
changed=true;
}
}while(changed);
}
void test_inplace_pos_neg()
{
int a[]={-1,-5,10,11,15,-500,200,-10};
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
inplace_pos_neg(a,sizeof(a)/sizeof(int));
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
}
Regards
On Fri, Jun 29, 2012 at 7:52 PM, utsav sharma
utsav.sharm...@gmail.comwrote:
@bhaskar:- please explain stable sorting algorithm you would use(as
mainly all of them require extra space)
@sourabh:- that previous post discussion does't lead to any correct
soln
On Fri, Jun 29, 2012 at 8:39 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@saurabh please provide the link to the post you are mentioning
On Fri, Jun 29, 2012 at 8:38 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
If the order is important then I think we can use any stable
sorting
algorithm with the following comparison function
int compare (int a ,int b)
{
if((a0b0)||(a0b0)) return 0;
else return ab;
}
On Fri, Jun 29, 2012 at 3:37 PM, raghavan M
peacelover1987...@yahoo.co.in wrote:
This is a variant of that one
--
*From:* saurabh singh saurab...@gmail.com
*To:* algogeeks@googlegroups.com
*Sent:* Friday, 29 June 2012 3:05 PM
*Subject:* Re: [algogeeks] MS Question: Segregrate positive and
negative nos in array without changing order
duplicate of a previous post.Kindly refer to that post.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Jun 29, 2012 at 10:41 AM, raghavan M
peacelover1987...@yahoo.co.in wrote:
Hi
Question as in subject
*No extra space (can use one extra space)-O(1) max
*No order change allowed
example:
input : 1,-5,2,10,-100,-2
output: -5,-10,-100,1,2
input : -1,-5,10,11,15,-500,200,-10
output : -1,-5,-10,-500,-10,10,11,15
Thanks
Raghavn
--
You
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
@darpan : storing the +ve and -ve numbers in a separate array and using it
later for restoring the array will do the trick.
@bhaskar: if thee numbers are 0 1 then no extra space required else you
need O(n) extra space.
--
Amol Sharma
Final Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99
On Mon, Jul 2, 2012 at 8:35 AM, shiva@Algo shiv.jays...@gmail.com wrote:
*
while(A[j]0i=mid)
swap(A[j],A[i])
i++
j++
On Mon, Jul 2, 2012 at 8:34 AM, shiva@Algo shiv.jays...@gmail.com wrote:
A simple Divide and Conquer strategy can work Well
Seg_pos_neg(A,beg,end) //A is the array
-
mid=beg+end/2
if(begend)
Seg_pos_neg(A,beg,mid)
Seg_pos_neg(A,mid+1,end)
//if leftsubarray contains +ve no and right subarray -ve
array,we swap them
if(A[mid+1]0)
j=mid+1
i=beg
while(A[i]0i=mid)
i++
while(A[j]0i=mid)
swap(A[j],A[i])
-
Running Time O(nlogn)
O(1) space
Correct me if I'm Wrong.
On Mon, Jul 2, 2012 at 7:53 AM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@amol u have used O(n) extra space!
I think it's not possible without using extra space.
On 7/2/12, Darpan Baweja darpan.bav...@gmail.com wrote:
@amol :- i don't think this algo would work here
after sorting how would you replace back the original no.s(as no.s are
not
0 and 1 in this case)
On Sun, Jul 1, 2012 at 11:08 PM, Amol Sharma amolsharm...@gmail.com
wrote:
i think it has been discussed beforenevertheless here is the
required
linear time solution.
first, count the total number 0's and 1's in the array.
let say, total elements are n and there are x zero's.
take count1=0 and count2=x;
traverse through the array :
for(i=0;in;i++)
if(arr[i]==0)
arr[i]=count1++;
else
arr[i]=count2++;
let's say array is {1,0,0,0,1,1,1,0,0,1} n=10,x=5
count1=0;count2=5
after the traversal it becomes a[]={5,0,1,2,6,7,8,3,4,9}
now sort this array in O(n) like this :
for(j=0;j=1;j++)
{
for(i=0;in;i++)
{
if(arr[i]!=i)
swap(arr[i],arr[arr[i]]);
}
}
after the array is sorted again traverse the array and set the
elements
from index 0 to x-1 to '0' and rest '1'.
--
Amol Sharma
Final Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99
http://in.linkedin.com/pub/amol-sharma/21/79b/507
http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99
On Fri, Jun 29, 2012 at 9:20 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@Hassan I think your algo will take time O(n^2) in worst case which
occurs when all elements are negative except the last one
@everyone Can we solve this problem in linear time?
On Fri, Jun 29, 2012 at 9:10 PM, Hassan Monfared
hmonfa...@gmail.comwrote:
Hi,
this can be done by simple modification in bubble sort :
void inplace_pos_neg(int pdata[],int sz)
{
bool changed=false;
do
{
changed=false;
for(int i=1;isz;i++)
if(pdata[i-1]0 pdata[i]0)
{
swap(pdata[i-1], pdata[i]);
changed=true;
}
}while(changed);
}
void test_inplace_pos_neg()
{
int a[]={-1,-5,10,11,15,-500,200,-10};
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
inplace_pos_neg(a,sizeof(a)/sizeof(int));
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
}
Regards
On Fri, Jun 29, 2012 at 7:52 PM, utsav sharma
utsav.sharm...@gmail.comwrote:
@bhaskar:- please explain stable sorting algorithm you would use(as
mainly all of them require extra space)
@sourabh:- that previous post discussion does't lead to any correct
soln
On Fri, Jun 29, 2012 at 8:39 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@saurabh please provide the link to the post you are mentioning
On Fri, Jun 29, 2012 at 8:38 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
If the order is important then I think we can use any stable
sorting
algorithm with the following comparison function
int compare (int a ,int b)
{
if((a0b0)||(a0b0)) return 0;
else return ab;
}
On Fri, Jun 29, 2012 at 3:37 PM, raghavan M
peacelover1987...@yahoo.co.in wrote:
This is a variant of that one
--
*From:* saurabh singh saurab...@gmail.com
*To:* algogeeks@googlegroups.com
*Sent:* Friday, 29 June 2012 3:05 PM
*Subject:* Re: [algogeeks] MS Question: Segregrate positive and
negative nos
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
duplicate of a previous post.Kindly refer to that post. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Fri, Jun 29, 2012 at 10:41 AM, raghavan M peacelover1987...@yahoo.co.inwrote: Hi Question as in subject *No extra space (can use one extra space)-O(1) max *No order change allowed example: input : 1,-5,2,10,-100,-2 output: -5,-10,-100,1,2 input : -1,-5,10,11,15,-500,200,-10 output : -1,-5,-10,-500,-10,10,11,15 Thanks Raghavn -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
one can modify dutch national flag algo for two colors(2 types positive n negative) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
Quick sort partition routine variation. On Fri, Jun 29, 2012 at 3:06 PM, Ravi Ranjan ravi.cool2...@gmail.comwrote: one can modify dutch national flag algo for two colors(2 types positive n negative) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
The main idea of this question is *not to change order of occurrence.Dutch National flag other swapping like quick sort will change the order of occurrence of number try yourself with simple example for proof. From: Ravi Ranjan ravi.cool2...@gmail.com To: algogeeks@googlegroups.com Sent: Friday, 29 June 2012 3:06 PM Subject: Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order one can modify dutch national flag algo for two colors(2 types positive n negative) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
This is a variant of that one From: saurabh singh saurab...@gmail.com To: algogeeks@googlegroups.com Sent: Friday, 29 June 2012 3:05 PM Subject: Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order duplicate of a previous post.Kindly refer to that post. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Fri, Jun 29, 2012 at 10:41 AM, raghavan M peacelover1987...@yahoo.co.in wrote: Hi Question as in subject *No extra space (can use one extra space)-O(1) max *No order change allowed example: input : 1,-5,2,10,-100,-2 output: -5,-10,-100,1,2 input : -1,-5,10,11,15,-500,200,-10 output : -1,-5,-10,-500,-10,10,11,15 Thanks Raghavn -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
If the order is important then I think we can use any stable sorting
algorithm with the following comparison function
int compare (int a ,int b)
{
if((a0b0)||(a0b0)) return 0;
else return ab;
}
On Fri, Jun 29, 2012 at 3:37 PM, raghavan M
peacelover1987...@yahoo.co.inwrote:
This is a variant of that one
--
*From:* saurabh singh saurab...@gmail.com
*To:* algogeeks@googlegroups.com
*Sent:* Friday, 29 June 2012 3:05 PM
*Subject:* Re: [algogeeks] MS Question: Segregrate positive and negative
nos in array without changing order
duplicate of a previous post.Kindly refer to that post.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Jun 29, 2012 at 10:41 AM, raghavan M
peacelover1987...@yahoo.co.in wrote:
Hi
Question as in subject
*No extra space (can use one extra space)-O(1) max
*No order change allowed
example:
input : 1,-5,2,10,-100,-2
output: -5,-10,-100,1,2
input : -1,-5,10,11,15,-500,200,-10
output : -1,-5,-10,-500,-10,10,11,15
Thanks
Raghavn
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
regards,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
@saurabh please provide the link to the post you are mentioning
On Fri, Jun 29, 2012 at 8:38 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
If the order is important then I think we can use any stable sorting
algorithm with the following comparison function
int compare (int a ,int b)
{
if((a0b0)||(a0b0)) return 0;
else return ab;
}
On Fri, Jun 29, 2012 at 3:37 PM, raghavan M peacelover1987...@yahoo.co.in
wrote:
This is a variant of that one
--
*From:* saurabh singh saurab...@gmail.com
*To:* algogeeks@googlegroups.com
*Sent:* Friday, 29 June 2012 3:05 PM
*Subject:* Re: [algogeeks] MS Question: Segregrate positive and negative
nos in array without changing order
duplicate of a previous post.Kindly refer to that post.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Jun 29, 2012 at 10:41 AM, raghavan M
peacelover1987...@yahoo.co.in wrote:
Hi
Question as in subject
*No extra space (can use one extra space)-O(1) max
*No order change allowed
example:
input : 1,-5,2,10,-100,-2
output: -5,-10,-100,1,2
input : -1,-5,10,11,15,-500,200,-10
output : -1,-5,-10,-500,-10,10,11,15
Thanks
Raghavn
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
regards,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
regards,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
@bhaskar:- please explain stable sorting algorithm you would use(as mainly
all of them require extra space)
@sourabh:- that previous post discussion does't lead to any correct soln
On Fri, Jun 29, 2012 at 8:39 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@saurabh please provide the link to the post you are mentioning
On Fri, Jun 29, 2012 at 8:38 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
If the order is important then I think we can use any stable sorting
algorithm with the following comparison function
int compare (int a ,int b)
{
if((a0b0)||(a0b0)) return 0;
else return ab;
}
On Fri, Jun 29, 2012 at 3:37 PM, raghavan M
peacelover1987...@yahoo.co.in wrote:
This is a variant of that one
--
*From:* saurabh singh saurab...@gmail.com
*To:* algogeeks@googlegroups.com
*Sent:* Friday, 29 June 2012 3:05 PM
*Subject:* Re: [algogeeks] MS Question: Segregrate positive and
negative nos in array without changing order
duplicate of a previous post.Kindly refer to that post.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Jun 29, 2012 at 10:41 AM, raghavan M
peacelover1987...@yahoo.co.in wrote:
Hi
Question as in subject
*No extra space (can use one extra space)-O(1) max
*No order change allowed
example:
input : 1,-5,2,10,-100,-2
output: -5,-10,-100,1,2
input : -1,-5,10,11,15,-500,200,-10
output : -1,-5,-10,-500,-10,10,11,15
Thanks
Raghavn
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
regards,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
regards,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
Utsav Sharma,
NIT Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
Hi,
this can be done by simple modification in bubble sort :
void inplace_pos_neg(int pdata[],int sz)
{
bool changed=false;
do
{
changed=false;
for(int i=1;isz;i++)
if(pdata[i-1]0 pdata[i]0)
{
swap(pdata[i-1], pdata[i]);
changed=true;
}
}while(changed);
}
void test_inplace_pos_neg()
{
int a[]={-1,-5,10,11,15,-500,200,-10};
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
inplace_pos_neg(a,sizeof(a)/sizeof(int));
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
}
Regards
On Fri, Jun 29, 2012 at 7:52 PM, utsav sharma utsav.sharm...@gmail.comwrote:
@bhaskar:- please explain stable sorting algorithm you would use(as mainly
all of them require extra space)
@sourabh:- that previous post discussion does't lead to any correct soln
On Fri, Jun 29, 2012 at 8:39 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@saurabh please provide the link to the post you are mentioning
On Fri, Jun 29, 2012 at 8:38 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
If the order is important then I think we can use any stable sorting
algorithm with the following comparison function
int compare (int a ,int b)
{
if((a0b0)||(a0b0)) return 0;
else return ab;
}
On Fri, Jun 29, 2012 at 3:37 PM, raghavan M
peacelover1987...@yahoo.co.in wrote:
This is a variant of that one
--
*From:* saurabh singh saurab...@gmail.com
*To:* algogeeks@googlegroups.com
*Sent:* Friday, 29 June 2012 3:05 PM
*Subject:* Re: [algogeeks] MS Question: Segregrate positive and
negative nos in array without changing order
duplicate of a previous post.Kindly refer to that post.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Jun 29, 2012 at 10:41 AM, raghavan M
peacelover1987...@yahoo.co.in wrote:
Hi
Question as in subject
*No extra space (can use one extra space)-O(1) max
*No order change allowed
example:
input : 1,-5,2,10,-100,-2
output: -5,-10,-100,1,2
input : -1,-5,10,11,15,-500,200,-10
output : -1,-5,-10,-500,-10,10,11,15
Thanks
Raghavn
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
regards,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
regards,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
Utsav Sharma,
NIT Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
@Hassan I think your algo will take time O(n^2) in worst case which occurs
when all elements are negative except the last one
@everyone Can we solve this problem in linear time?
On Fri, Jun 29, 2012 at 9:10 PM, Hassan Monfared hmonfa...@gmail.comwrote:
Hi,
this can be done by simple modification in bubble sort :
void inplace_pos_neg(int pdata[],int sz)
{
bool changed=false;
do
{
changed=false;
for(int i=1;isz;i++)
if(pdata[i-1]0 pdata[i]0)
{
swap(pdata[i-1], pdata[i]);
changed=true;
}
}while(changed);
}
void test_inplace_pos_neg()
{
int a[]={-1,-5,10,11,15,-500,200,-10};
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
inplace_pos_neg(a,sizeof(a)/sizeof(int));
copy(a,a+sizeof(a)/sizeof(int),ostream_iteratorint(cout,,));coutendl;
}
Regards
On Fri, Jun 29, 2012 at 7:52 PM, utsav sharma utsav.sharm...@gmail.comwrote:
@bhaskar:- please explain stable sorting algorithm you would use(as
mainly all of them require extra space)
@sourabh:- that previous post discussion does't lead to any correct soln
On Fri, Jun 29, 2012 at 8:39 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
@saurabh please provide the link to the post you are mentioning
On Fri, Jun 29, 2012 at 8:38 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
If the order is important then I think we can use any stable sorting
algorithm with the following comparison function
int compare (int a ,int b)
{
if((a0b0)||(a0b0)) return 0;
else return ab;
}
On Fri, Jun 29, 2012 at 3:37 PM, raghavan M
peacelover1987...@yahoo.co.in wrote:
This is a variant of that one
--
*From:* saurabh singh saurab...@gmail.com
*To:* algogeeks@googlegroups.com
*Sent:* Friday, 29 June 2012 3:05 PM
*Subject:* Re: [algogeeks] MS Question: Segregrate positive and
negative nos in array without changing order
duplicate of a previous post.Kindly refer to that post.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Jun 29, 2012 at 10:41 AM, raghavan M
peacelover1987...@yahoo.co.in wrote:
Hi
Question as in subject
*No extra space (can use one extra space)-O(1) max
*No order change allowed
example:
input : 1,-5,2,10,-100,-2
output: -5,-10,-100,1,2
input : -1,-5,10,11,15,-500,200,-10
output : -1,-5,-10,-500,-10,10,11,15
Thanks
Raghavn
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
regards,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
regards,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
Utsav Sharma,
NIT Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
regards,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email
