Given an array of size n wherein elements keep on increasing monotically upto a certain location
after which they keep on decreasing monotically, then again keep on increasing, then decreasing
again and so on. Sort the array in place (ie. using only O(1) extra memory).
Solution:
Step1: Find the point after which the decrease starts let us call it P1. O(logn)
Step2: From P1 reverse the array. O(n)
Step3: Mark the beginning of the array as P2.
Step4: Now start a inplace merge sort, where first array begins at P1 and other at P2. O(n)
14 comments:
how wud the step one take logn??
Looks like crap!
Any array will be in the format you have mentioned (inc, dec, inc, dec ...) and this is an O(n) solution!!
May be we should patent this.
Please remove this blog post. You will be saving others time.
Any given array will be in the format you mentioned in this question.
Can you please provide an array which doesn't follow the format of increase, decrease, inc, dec etc?
And here you have an O(n) sorting solution!
How do u merge two ranges in place in linear time?
Isnt this like Bitonic sorting?
Sorting on bitonic sequences.
why have you stopped blogging?
kind of yes for time being...
Hello,
Thanks for sharing this link - but unfortunately it seems to be down? Does anybody here at dsalgo.blogspot.com have a mirror or another source?
Cheers,
Charlie
Hi there,
I have a question for the webmaster/admin here at dsalgo.blogspot.com.
May I use some of the information from this post above if I provide a link back to your site?
Thanks,
John
Greetings,
This is a message for the webmaster/admin here at dsalgo.blogspot.com.
Can I use part of the information from your blog post above if I give a backlink back to this website?
Thanks,
Alex
Yes you may...
I am a third year student of CSE at IIT Kharagpur.
I have a sincere request to make to you.
Your collection of beautiful algorithmic problems is one of the best in web, and you can make your blog much better.
1) Please hide solutions so that they are not exposed readily after the problem, since the only way to learn algorithms is to give your best trying and thinking rather than directly seeing the solution.
Atleast leave enough space after the problem and before the solution.
2) Rather than giving the code and solutions directly why don't you give ideas concerned or the techniques used ,for e.g. the technique used in 'Majority Element in Array' is that of using a stack although it can be interpreted in other ways.
Thanks, for reading my suggestion and once again thanks for making such a fine collection of interesting problems and filtering uninteresting problems like FFT.
@mahesh .. first read the question carefully .. it is only
(inc)(dec)
and yes it can be done O(n)...
think before u abuse... crap
Post a Comment