[algogeeks] Re: Amazon: sort array
@Anand, @Abhishek
Thanks for the code and discussion.
However I am not clear as to how the approach suggested is running in
O(n) time. We are dividing and calling bitonicmerge() on two parts
recursively. So this should run in O(n log n) time complexity as
shown below
T(n) = n/2 + 2T(n/2) = n/2 + 2[n/4 + 2T(n/4)] = n/2 + n/2 + 4[n/8 +
2T(n/8)]
= n/2 + n/2 + n/2 + log n terms (because we are doubling base
each time so it should be log n terms]
= n [ 1/2 + 1/2 + 1/2 + ...log n terms]
= n [ (log n)/2] = 1/2*(n log n ) = O(n log n)
Also all the following links mention this approach to be O(n log^2(n))
in best case and O(n log n) in worst case
http://www.extreme.indiana.edu/sage/pcxx_ug/subsection3_6_2.html
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm
http://en.wikipedia.org/wiki/Bitonic_sorter
Some explanation on how this is O(n) will be of great help.
Thanks in Advance.
Sourav
On Jul 3, 1:35 am, Abhishek Sharma wrote:
> @Anand: good one
>
> On Sat, Jul 3, 2010 at 2:02 AM, Anand wrote:
> > This is an example of bitonic sequence if we reverse the bottom half of the
> > array.
> > Sequence is called Bitonics if the sequence of number first
> > increases(ascending order) and then decrease(descending order).
>
> > 1. We need to reverse the bottom half the array to make it bitonic.
> > 2. Appy Bitonic Merge to get the final sorted array.: Complexity.O(n)
>
> > In the below code, I have implemented sorting n/w to sort any kind of array
> > but for bitonic sequence we only bitonic merge function call which take
> > O(n).
> > Refer section Sorting network from Corman for more details
>
> >http://codepad.org/ZhYEBqMw
>
> > On Fri, Jul 2, 2010 at 11:30 AM, ANKUR BHARDWAJ wrote:
>
> >> Given an array of n elements and an integer k where k >> {a[0].a[k] and a[k+1].a[n] are already sorted. Give an
> >> algorithm to sort in O(n) time and O(1) space.
>
> >> --
> >> 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.
>
> > --
> > 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.
--
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.
[algogeeks] Re: Amazon: sort array
Is not ur code is running in o(n^2) complexity
You have used two while loop ...
plzz eleborate if i m wrong .
On Jul 12, 11:00 am, Amit Mittal wrote:
> I think this will work.
>
> # include "stdio.h"
>
> void my_print(int *,int);
> void swap(int &a , int&b)
> {
> a = a + b;
> b = a - b;
> a = a - b;}
>
> void sort(int* array, int SIZE, int i, int j)
> {
> while(i {
> my_print(array,SIZE);
> if(array[i] <= array[j])
> i++;
> if(array[j] < array[i])
> {
> swap(array[i] , array[j]);
> i++;
> int temp = j;
> while(temp< (SIZE-1) && (array[temp] > array[temp+1])
> )
> {
> swap(array[temp] , array[temp + 1]);
> temp++;
> }
> }
> }
>
> }
>
> void my_print(int * array, int SIZE)
> {
> printf("\n");
> int i = 0;
> for(; i < SIZE ; i++)
> printf("%d, ",array[i]);
> printf("\n");}
>
> int main()
> {
> int array1[8] = {1,3,6,7,4,5,6,8};
> int array2[10] = {1,2,3,5,6,7,4,8,9,10};
> int array3[10] = {10,20,30,40,50,23,27,40};
>
> //sort(array1,8,0,4);
> //sort(array2,10,0,6);
> sort(array3,8,0,5);
> //my_print(array1,8);
> //my_print(array2,10);
> my_print(array3,8);
> return 0;
>
> }
>
> On Mon, Jul 12, 2010 at 10:20 AM, Abhishek Kumar Singh <
>
>
>
> iiita2007...@gmail.com> wrote:
> > @souravsain
>
> > for input {10,20,30,40,50,23,27};
> > ur output is coming 10, 20, 23, 27, 40, 30, 50,
> > which not SORTED array.
>
> > On Jul 10, 6:19 pm, souravsain wrote:
> > > @Jitendra
>
> > > I have run the code with input given by you and found that it works
> > > well.
>
> > > Please have a look athttp://codepad.org/iMBTwAL7
>
> > > Appriciate the effort taken by you to analyze the solution and do let
> > > me know if you still do not agree with the code.
>
> > > Regards,
> > > Sourav
>
> > > On Jul 8, 9:03 pm, Jitendra Kushwaha wrote:
>
> > > > @souravsain
> > > > Consider your algo for the case
> > > > int arr[] = {10,20,30,40,50,23,27};
>
> > > > everytime when you increment the j you are missing on element i.e j-1
> > for
> > > > further comparison
>
> > > > --
> > > > Regards
> > > > Jitendra Kushwaha
> > > > MNNIT, Allahabad
>
> > --
> > 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 > .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 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.
Re: [algogeeks] Re: Amazon: sort array
I think this will work.
# include "stdio.h"
void my_print(int *,int);
void swap(int &a , int&b)
{
a = a + b;
b = a - b;
a = a - b;
}
void sort(int* array, int SIZE, int i, int j)
{
while(i array[temp+1]) )
{
swap(array[temp] , array[temp + 1]);
temp++;
}
}
}
}
void my_print(int * array, int SIZE)
{
printf("\n");
int i = 0;
for(; i < SIZE ; i++)
printf("%d, ",array[i]);
printf("\n");
}
int main()
{
int array1[8] = {1,3,6,7,4,5,6,8};
int array2[10] = {1,2,3,5,6,7,4,8,9,10};
int array3[10] = {10,20,30,40,50,23,27,40};
//sort(array1,8,0,4);
//sort(array2,10,0,6);
sort(array3,8,0,5);
//my_print(array1,8);
//my_print(array2,10);
my_print(array3,8);
return 0;
}
On Mon, Jul 12, 2010 at 10:20 AM, Abhishek Kumar Singh <
iiita2007...@gmail.com> wrote:
> @souravsain
>
> for input {10,20,30,40,50,23,27};
> ur output is coming 10, 20, 23, 27, 40, 30, 50,
> which not SORTED array.
>
> On Jul 10, 6:19 pm, souravsain wrote:
> > @Jitendra
> >
> > I have run the code with input given by you and found that it works
> > well.
> >
> > Please have a look athttp://codepad.org/iMBTwAL7
> >
> > Appriciate the effort taken by you to analyze the solution and do let
> > me know if you still do not agree with the code.
> >
> > Regards,
> > Sourav
> >
> > On Jul 8, 9:03 pm, Jitendra Kushwaha wrote:
> >
> >
> >
> > > @souravsain
> > > Consider your algo for the case
> > > int arr[] = {10,20,30,40,50,23,27};
> >
> > > everytime when you increment the j you are missing on element i.e j-1
> for
> > > further comparison
> >
> > > --
> > > Regards
> > > Jitendra Kushwaha
> > > MNNIT, Allahabad
>
> --
> 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.
>
>
--
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.
[algogeeks] Re: Amazon: sort array
@souravsain
for input {10,20,30,40,50,23,27};
ur output is coming 10, 20, 23, 27, 40, 30, 50,
which not SORTED array.
On Jul 10, 6:19 pm, souravsain wrote:
> @Jitendra
>
> I have run the code with input given by you and found that it works
> well.
>
> Please have a look athttp://codepad.org/iMBTwAL7
>
> Appriciate the effort taken by you to analyze the solution and do let
> me know if you still do not agree with the code.
>
> Regards,
> Sourav
>
> On Jul 8, 9:03 pm, Jitendra Kushwaha wrote:
>
>
>
> > @souravsain
> > Consider your algo for the case
> > int arr[] = {10,20,30,40,50,23,27};
>
> > everytime when you increment the j you are missing on element i.e j-1 for
> > further comparison
>
> > --
> > Regards
> > Jitendra Kushwaha
> > MNNIT, Allahabad
--
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.
[algogeeks] Re: Amazon: sort array
@Jitendra
Sorry for the previous post. There is a problem in my approach. I
overlooked that.
Working on it.. :(
On Jul 8, 9:03 pm, Jitendra Kushwaha wrote:
> @souravsain
> Consider your algo for the case
> int arr[] = {10,20,30,40,50,23,27};
>
> everytime when you increment the j you are missing on element i.e j-1 for
> further comparison
>
> --
> Regards
> Jitendra Kushwaha
> MNNIT, Allahabad
--
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.
[algogeeks] Re: Amazon: sort array
@problem owner
Have you posted the correct question? Because this does
not seems like a trivial question which someone can ask in the middle
of an interview. I found a similar question while googling. It reads:
"There are two sorted arrays A1 and A2. Array A1 is full where
as array A2 is partially empty and number of empty slots are just
enough to accommodate all elements of A1. Write a program to merge the
two sorted arrays to fill the array A2. You cannot use any additional
memory and expected run time is O(n)"
Check this link:
http://www.technicalinterviewquestions.net/2009/01/merge-sorted-arrays-empty-slots.html
On Jul 8, 12:03 pm, Jitendra Kushwaha
wrote:
> @souravsain
> Consider your algo for the case
> int arr[] = {10,20,30,40,50,23,27};
>
> everytime when you increment the j you are missing on element i.e j-1 for
> further comparison
>
> --
> Regards
> Jitendra Kushwaha
> MNNIT, Allahabad
--
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.
[algogeeks] Re: Amazon: sort array
@Jitendra
I have run the code with input given by you and found that it works
well.
Please have a look at http://codepad.org/iMBTwAL7
Appriciate the effort taken by you to analyze the solution and do let
me know if you still do not agree with the code.
Regards,
Sourav
On Jul 8, 9:03 pm, Jitendra Kushwaha wrote:
> @souravsain
> Consider your algo for the case
> int arr[] = {10,20,30,40,50,23,27};
>
> everytime when you increment the j you are missing on element i.e j-1 for
> further comparison
>
> --
> Regards
> Jitendra Kushwaha
> MNNIT, Allahabad
--
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.
[algogeeks] Re: Amazon: sort array
@problem owner
Have you posted the correct question? Because this does
not seems like a trivial question which someone can ask in the middle
of an interview. I found a similar question while googling. It reads:
"There are two sorted arrays A1 and A2. Array A1 is full where
as array A2 is partially empty and number of empty slots are just
enough to accommodate all elements of A1. Write a program to merge the
two sorted arrays to fill the array A2. You cannot use any additional
memory and expected run time is O(n)"
Check this link:
http://www.technicalinterviewquestions.net/2009/01/merge-sorted-arrays-empty-slots.html
On Jul 8, 12:03 pm, Jitendra Kushwaha
wrote:
> @souravsain
> Consider your algo for the case
> int arr[] = {10,20,30,40,50,23,27};
>
> everytime when you increment the j you are missing on element i.e j-1 for
> further comparison
>
> --
> Regards
> Jitendra Kushwaha
> MNNIT, Allahabad
--
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.
Re: [algogeeks] Re: Amazon: sort array
@souravsain
Consider your algo for the case
int arr[] = {10,20,30,40,50,23,27};
everytime when you increment the j you are missing on element i.e j-1 for
further comparison
--
Regards
Jitendra Kushwaha
MNNIT, Allahabad
--
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.
[algogeeks] Re: Amazon: sort array
I believe a merge sort requires O(n) space complexity. Is stack spce
counted towards space complexity? If not, I imagine you could write a
merge sort recursively, so that the explict space usage has O(1)
complexity.
On Jul 2, 2:37 pm, Abhishek Sharma wrote:
> I think its similar to the merge operation which is used in merge sort...
>
> correct me if I am wrong..
>
> Regards,
> Abhishek
>
> On Sat, Jul 3, 2010 at 12:00 AM, ANKUR BHARDWAJ wrote:
>
>
>
> > Given an array of n elements and an integer k where k > {a[0].a[k] and a[k+1].a[n] are already sorted. Give an
> > algorithm to sort in O(n) time and O(1) space.
>
> > --
> > 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.- Hide quoted text -
>
> - Show quoted text -
--
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.
[algogeeks] Re: Amazon: sort array
@all
Please find my O(n) time and O(1) space implementation for this
problem.
Summary of approach: let i be start for first sorted part and j be
start of next sorted part. move i as long as a[i] is less than a[j] as
that means things are sorted.
if a[i] > a[j], swap them and increment i. Increment j if it is no
more start of a sprted part. So j always points to start of a sorted
part of array. As long as i equals j, we are done.
Here is the implementation
# include "stdio.h"
void sort(int* array, int SIZE, int i, int j)
{
while(i array[j+1]) )
j++;
}
}
}
void my_print(int * array, int SIZE)
{
printf("\n");
for(int i = 0; i < SIZE ; i++)
printf("%d, ",array[i]);
printf("\n");
}
int main()
{
int array1[8] = {1,3,6,7,4,5,6,8};
int array2[10] = {1,2,3,5,6,7,4,8,9,10};
sort(array1,8,0,4);
sort(array2,10,0,6);
my_print(array1,8);
my_print(array2,10);
return 0;
}
Sourav
On Jul 5, 2:15 pm, harit agarwal wrote:
> inplace merging requires worst case O(nlogn)
> check pdf
>
> merge-algorithms-screen.pdf
> 238KViewDownload
--
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.
Re: [algogeeks] Re: Amazon: sort array
inplace merging can be done.. but i dnt knw the exact algo.. but there is
smthin called inplace merging
On Sat, Jul 3, 2010 at 10:34 PM, padmanaban sahadevan wrote:
> ya pplthe underlying operation is to do merge 2 sorted arrays as we do
> in merge sort.but remember in merge sort the space complexity is not
> O(1).but here v need O(1)...
>
>
> On Sat, Jul 3, 2010 at 9:57 PM, Anand wrote:
>
>> @souravsain:
>> Given an array of n elements and an integer k where k> > > {a[0].a[k] and a[k+1].a[n] are already sorted.
>>
>> As per the question a{0} to a{k} is sorted and a{K+1} to a{n} is sorted
>> so we look at the sequence in a{0} to a{k} and {n} to a{k+1} it makes a
>> bitonic sequence.
>> and if we apply bitonic merge on it, it gives a final sorted sequence.
>>
>>
>>
>>
>> On Sat, Jul 3, 2010 at 12:23 AM, souravsain wrote:
>>
>>> @Anand
>>>
>>> Please explain how you concluded that the array will first
>>> continuously increase and then continuously decrease? Why can it not
>>> be 2 continuous increase like [1,2,3,4,5,3,4,8] where [1,2,3,4,5] and
>>> [3,4,8] are a[1] to a[k] and a[k+1] to a[N] respectively? Whill your
>>> method work still?
>>>
>>> @Ankur, Correct me if my interpretation of the question is wrong.
>>>
>>> Sourav
>>>
>>> On Jul 3, 1:32 am, Anand wrote:
>>> > This is an example of bitonic sequence if we reverse the bottom half of
>>> the
>>> > array.
>>> > Sequence is called Bitonics if the sequence of number first
>>> > increases(ascending order) and then decrease(descending order).
>>> >
>>> > 1. We need to reverse the bottom half the array to make it bitonic.
>>> > 2. Appy Bitonic Merge to get the final sorted array.: Complexity.O(n)
>>> >
>>> > In the below code, I have implemented sorting n/w to sort any kind of
>>> array
>>> > but for bitonic sequence we only bitonic merge function call which take
>>> > O(n).
>>> > Refer section Sorting network from Corman for more details
>>> >
>>> > http://codepad.org/ZhYEBqMw
>>> >
>>> > On Fri, Jul 2, 2010 at 11:30 AM, ANKUR BHARDWAJ >> >wrote:
>>> >
>>> > > Given an array of n elements and an integer k where k>> > > {a[0].a[k] and a[k+1].a[n] are already sorted. Give an
>>> > > algorithm to sort in O(n) time and O(1) space.
>>> >
>>> > > --
>>> > > 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.
>>>
>>> --
>>> 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.
>>>
>>>
>> --
>> 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.
>>
>
> --
> 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.
>
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
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.
Re: [algogeeks] Re: Amazon: sort array
@souravsain: In the method suggested by anand, he was first reversing the second part of the array i.e. a[k+1]a[n] and then applying bitonic sort. Both the parts are initially sorted in same direction. -- 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.
Re: [algogeeks] Re: Amazon: sort array
ya pplthe underlying operation is to do merge 2 sorted arrays as we do
in merge sort.but remember in merge sort the space complexity is not
O(1).but here v need O(1)...
On Sat, Jul 3, 2010 at 9:57 PM, Anand wrote:
> @souravsain:
> Given an array of n elements and an integer k where k > > {a[0].a[k] and a[k+1].a[n] are already sorted.
>
> As per the question a{0} to a{k} is sorted and a{K+1} to a{n} is sorted
> so we look at the sequence in a{0} to a{k} and {n} to a{k+1} it makes a
> bitonic sequence.
> and if we apply bitonic merge on it, it gives a final sorted sequence.
>
>
>
>
> On Sat, Jul 3, 2010 at 12:23 AM, souravsain wrote:
>
>> @Anand
>>
>> Please explain how you concluded that the array will first
>> continuously increase and then continuously decrease? Why can it not
>> be 2 continuous increase like [1,2,3,4,5,3,4,8] where [1,2,3,4,5] and
>> [3,4,8] are a[1] to a[k] and a[k+1] to a[N] respectively? Whill your
>> method work still?
>>
>> @Ankur, Correct me if my interpretation of the question is wrong.
>>
>> Sourav
>>
>> On Jul 3, 1:32 am, Anand wrote:
>> > This is an example of bitonic sequence if we reverse the bottom half of
>> the
>> > array.
>> > Sequence is called Bitonics if the sequence of number first
>> > increases(ascending order) and then decrease(descending order).
>> >
>> > 1. We need to reverse the bottom half the array to make it bitonic.
>> > 2. Appy Bitonic Merge to get the final sorted array.: Complexity.O(n)
>> >
>> > In the below code, I have implemented sorting n/w to sort any kind of
>> array
>> > but for bitonic sequence we only bitonic merge function call which take
>> > O(n).
>> > Refer section Sorting network from Corman for more details
>> >
>> > http://codepad.org/ZhYEBqMw
>> >
>> > On Fri, Jul 2, 2010 at 11:30 AM, ANKUR BHARDWAJ > >wrote:
>> >
>> > > Given an array of n elements and an integer k where k> > > {a[0].a[k] and a[k+1].a[n] are already sorted. Give an
>> > > algorithm to sort in O(n) time and O(1) space.
>> >
>> > > --
>> > > 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.
>>
>> --
>> 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.
>>
>>
> --
> 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.
>
--
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.
Re: [algogeeks] Re: Amazon: sort array
@souravsain:
Given an array of n elements and an integer k where k > {a[0].a[k] and a[k+1].a[n] are already sorted.
As per the question a{0} to a{k} is sorted and a{K+1} to a{n} is sorted
so we look at the sequence in a{0} to a{k} and {n} to a{k+1} it makes a
bitonic sequence.
and if we apply bitonic merge on it, it gives a final sorted sequence.
On Sat, Jul 3, 2010 at 12:23 AM, souravsain wrote:
> @Anand
>
> Please explain how you concluded that the array will first
> continuously increase and then continuously decrease? Why can it not
> be 2 continuous increase like [1,2,3,4,5,3,4,8] where [1,2,3,4,5] and
> [3,4,8] are a[1] to a[k] and a[k+1] to a[N] respectively? Whill your
> method work still?
>
> @Ankur, Correct me if my interpretation of the question is wrong.
>
> Sourav
>
> On Jul 3, 1:32 am, Anand wrote:
> > This is an example of bitonic sequence if we reverse the bottom half of
> the
> > array.
> > Sequence is called Bitonics if the sequence of number first
> > increases(ascending order) and then decrease(descending order).
> >
> > 1. We need to reverse the bottom half the array to make it bitonic.
> > 2. Appy Bitonic Merge to get the final sorted array.: Complexity.O(n)
> >
> > In the below code, I have implemented sorting n/w to sort any kind of
> array
> > but for bitonic sequence we only bitonic merge function call which take
> > O(n).
> > Refer section Sorting network from Corman for more details
> >
> > http://codepad.org/ZhYEBqMw
> >
> > On Fri, Jul 2, 2010 at 11:30 AM, ANKUR BHARDWAJ >wrote:
> >
> > > Given an array of n elements and an integer k where k > > {a[0].a[k] and a[k+1].a[n] are already sorted. Give an
> > > algorithm to sort in O(n) time and O(1) space.
> >
> > > --
> > > 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.
>
> --
> 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.
>
>
--
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.
[algogeeks] Re: Amazon: sort array
@Anand , thanx for info , but does the question asked requires so
much ?
I felt , you have two sorted sub arrays so simply merging it (of merge
sort fame ! ) would solve it , isn't it ?
On Jul 3, 9:24 am, ankur bhardwaj wrote:
> @anand: this code will not work when n is not power of 2.
>
> check for this example:
>
> {2, 4, 55, 25, 15}
>
> Output was:
>
> 0 4
> 0 2
> 1 3
> 0 1
> 2 3
> 2 4 25 55 15 0 0 0
> ascending order
--
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.
[algogeeks] Re: Amazon: sort array
@Anand
Please explain how you concluded that the array will first
continuously increase and then continuously decrease? Why can it not
be 2 continuous increase like [1,2,3,4,5,3,4,8] where [1,2,3,4,5] and
[3,4,8] are a[1] to a[k] and a[k+1] to a[N] respectively? Whill your
method work still?
@Ankur, Correct me if my interpretation of the question is wrong.
Sourav
On Jul 3, 1:32 am, Anand wrote:
> This is an example of bitonic sequence if we reverse the bottom half of the
> array.
> Sequence is called Bitonics if the sequence of number first
> increases(ascending order) and then decrease(descending order).
>
> 1. We need to reverse the bottom half the array to make it bitonic.
> 2. Appy Bitonic Merge to get the final sorted array.: Complexity.O(n)
>
> In the below code, I have implemented sorting n/w to sort any kind of array
> but for bitonic sequence we only bitonic merge function call which take
> O(n).
> Refer section Sorting network from Corman for more details
>
> http://codepad.org/ZhYEBqMw
>
> On Fri, Jul 2, 2010 at 11:30 AM, ANKUR BHARDWAJ wrote:
>
> > Given an array of n elements and an integer k where k > {a[0].a[k] and a[k+1].a[n] are already sorted. Give an
> > algorithm to sort in O(n) time and O(1) space.
>
> > --
> > 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.
--
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.
[algogeeks] Re: Amazon: sort array
@Anand
Also you cannot conclude that k will be middle. There is no mention of
half. Its that only k wrote:
> This is an example of bitonic sequence if we reverse the bottom half of the
> array.
> Sequence is called Bitonics if the sequence of number first
> increases(ascending order) and then decrease(descending order).
>
> 1. We need to reverse the bottom half the array to make it bitonic.
> 2. Appy Bitonic Merge to get the final sorted array.: Complexity.O(n)
>
> In the below code, I have implemented sorting n/w to sort any kind of array
> but for bitonic sequence we only bitonic merge function call which take
> O(n).
> Refer section Sorting network from Corman for more details
>
> http://codepad.org/ZhYEBqMw
>
> On Fri, Jul 2, 2010 at 11:30 AM, ANKUR BHARDWAJ wrote:
>
> > Given an array of n elements and an integer k where k > {a[0].a[k] and a[k+1].a[n] are already sorted. Give an
> > algorithm to sort in O(n) time and O(1) space.
>
> > --
> > 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.
--
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.
