@NUPUL Did you describe an algorithm? On 3/14/07, NUPUL <[EMAIL PROTECTED]> wrote: > > > > > On Mar 13, 11:55 pm, "Karthik Singaram L" <[EMAIL PROTECTED]> > wrote: > > I agree with you completely but for the problem that I posted it is > > enough that we have O(n) in accessing the elements in order. Your > > solution does better by calculating every element in O(1) time. The > > key now is to do the actual sorting with this method > > Firstly your problem is not out of the blue...it's an enquiry for an > existence of such an algorithm. Secondly, a good deal of research has > gone into finding algorithms with O(n) sorting time and that too > inplace (with space of O(1)). This is an ideal requirement! Existing > Sorting algorithms can only *approximate* such constraints! If such an > algorithm exists it'll be a breakthrough and everyone will want to > jump for it! But that algorithm may not be applicable for "general > use"...i.e. Radix sort was primarliy for punch card based systems > (that's where it was invented!) and maybe used for sorting on multiple > keys like in a DBMS. > > Now in your later posts you clarified that it's a binary search tree > that is stored in an array. You say you don't want to "print" the > numbers but to sort the array in place. Any reasons for such a > requirement or just curiosity? Anyways, I don't think such an > algorithm exists...keep reading texts and do correct me if I'm wrong. > In fact, I'm left wondering...why would one want to do that? > > Let me get your requirements right: > > 1. A binary search tree stored in an array (1..n) > 2. you want the array to be sorted inplace in max O(n) time and > constant space. > > If you want 1 then forget about 2...it's not possible. > if you want 2 then why the stringent requirement of 1? let it be an > unordered array and all of a sudden many algos will begin to appear!! > > > > There is actually a simpler logic to perform inorder traversal in > > constant space and O(n) time. Just keep track of the previous node you > > have visited and the current node. > > Try looking at threaded binary trees. > > >Now If you are coming from the top > > go left. If you are coming from left down go the right. If you are > > coming from right down go up. > > Post it algorithmically! This is a confusing way to describe an > algorithm. > > > The question still remains as to how to apply this permutation in a > > cute manner to the array so that we can be able to sort the array. > > Good. So you think you may have found a neat little algorithm to help > you sort but some loop holes still remain. Please continue to read > texts on algorithms...so as to keep you inplace! > > > To give a hint, a simplistic solution is to swap each element in ith > > position with the permutation value a[i]. > > A hint for what? Is this your second algo? different from the above? > Then why give a hint and not the complete solution algorithmically > > > The weird nuance of this > > however is that it doesnt behave in the way we want since some > > numbers may move around to different places. Try to impose an > > ordering. > > So you found another *wierd* flaw (or nuance as you've put it)! > > I suggest you refer "Introduction to algorithms: Cormen." It'll > satiate your appetite for the hunt of such an algorithm. If you are > successful at finding such an algorithm do post it here! > > Regards, > > Nupul > > > > > > > >
--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
