[algogeeks] Amazon: sort array
Given an array of n elements and an integer k where kn. Elemnts
{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.
Re: [algogeeks] Amazon: sort array
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 ankibha...@gmail.comwrote:
Given an array of n elements and an integer k where kn. Elemnts
{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.comalgogeeks%2bunsubscr...@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] Amazon: sort array
@Anand: good one
On Sat, Jul 3, 2010 at 2:02 AM, Anand anandut2...@gmail.com 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 ankibha...@gmail.comwrote:
Given an array of n elements and an integer k where kn. Elemnts
{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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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] Amazon: sort array
Something like merge sort should do.
On Sat, Jul 3, 2010 at 12:00 AM, ANKUR BHARDWAJ ankibha...@gmail.com wrote:
Given an array of n elements and an integer k where kn. Elemnts
{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.
--
Siddharth Prakash Singh
http://www.spsneo.com
--
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] Amazon: sort array
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 ankibha...@gmail.comwrote:
Given an array of n elements and an integer k where kn. Elemnts
{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.comalgogeeks%2bunsubscr...@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] Amazon: sort array
@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.
