@aashish, Yeah, i went through the link, nice one dude! But, i believe even that would be O(n2).
On Jun 12, 2:42 pm, ross <[email protected]> wrote: > @piyush: > Hi piyush, > It is reverse the elements from i to j.. > For example, 12 22 33 44 55 66 63 > when given reverse (0,2) produces 33 22 12 44 55 66 63.. so on > > One very naive approach for this problem would be to use a variant of > bubble sort with a swap flag, > > swap=1; > while(swap) { > swap = 0; > for(i=0 to len) > if(get[i]>get[i+1]) {reverse (i,i+1); swap=1} > > } > > But, here the function reverse has just been used to swap and does not > serve its intended purpose.. > complexity is O(n2). Any better approach? > > On Jun 12, 2:15 pm, Piyush Sinha <[email protected]> wrote: > > > > > > > > > @ross....I have a doubt regarding reverse function... > > > does it rotate the array or reverse it?? > > > for say it is 12345 > > > reverse(0,4) make it 51234 or 54321??? > > > On 6/12/11, ross <[email protected]> wrote: > > > > There is an array in an external system (i.e. u cannot access the > > > array elements directly). > > > > The system exposes 3 functions of O(1) - (assume) : > > > length() - returns the length of the array. > > > get(i) - returns the element at index i. > > > reverse(i,j) - reverses the elements in the array from index i to > > > index j (both indexes inclusive). > > > sort the array in the best possible way using only these 3 operations? > > > > -- > > > You received this message because you are subscribed to the Google Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > -- > > *Piyush Sinha* > > *IIIT, Allahabad* > > *+91-8792136657* > > *+91-7483122727* > > *https://www.facebook.com/profile.php?id=100000655377926* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
