sort in o(1) extra memory
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).
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).
use K-tonic sort.:)
ReplyDeleteHeyy I googled this and found the solution something like this...
ReplyDeletesuppose the array is 12345 4321 2345 4321
it increases then dcreases then increases and decreases again
first of all in a single scan find the location of decreasing sub-arrays
here it is 5 to 8 and 13-16
and reverse the decreasing array.
so the array becomes
12345 1234 2345 1234
now do simple inplace merging of sorted arrays.
My question is how in place merge can be done in O(n) times...
I googled K-tonic sort also. Bt dint find any suitable ans/description
If u hv ne link plz post
i am sorry the merging will take O(k*m),where m is number of elements in first and second list.
ReplyDelete