[algogeeks] Re: Inplace sorting

2007-03-15 Thread Karthik Singaram L
well the requirement is only to sort the array Array repr: 9,6,21,1,7,16,36 (index starting from 1) Now on sorting the array in place gives: 1,6,7,9,16,21,36 is a perfectly valid answer to the problem. No one is going to look at the result as a BST, it is going to be viewed as a sorted array.

[algogeeks] Re: Inplace sorting

2007-03-14 Thread NUPUL
On Mar 14, 5:43 pm, "Rajiv Mathews" <[EMAIL PROTECTED]> wrote: > On 3/14/07, NUPUL <[EMAIL PROTECTED]> wrote: > > > > > 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

[algogeeks] Re: Inplace sorting

2007-03-14 Thread Rajiv Mathews
On 3/14/07, NUPUL <[EMAIL PROTECTED]> wrote: > > 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 a

[algogeeks] Re: Inplace sorting

2007-03-13 Thread Arun
i think this problem is not a generic sorting problem bcos we already know the "sorted order" thru inorder traversal(O(n) time and O(1) space). the problem is having known the sorted order, how do u "rearrange" the array. while i dont have any solution, we cannot dismiss this problem since its not

[algogeeks] Re: Inplace sorting

2007-03-13 Thread Pradeep Muthukrishnan
@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 orde

[algogeeks] Re: Inplace sorting

2007-03-13 Thread NUPUL
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

[algogeeks] Re: Inplace sorting

2007-03-13 Thread Karthik Singaram L
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 --~--~-~--~~~-

[algogeeks] Re: Inplace sorting

2007-03-13 Thread Atamurad Hezretkuliyev
On 3/14/07, Karthik Singaram L <[EMAIL PROTECTED]> wrote: > > > @atamyrat: > > 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. Now If you are coming from the top > go left

[algogeeks] Re: Inplace sorting

2007-03-13 Thread Karthik Singaram L
@atamyrat: 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. 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

[algogeeks] Re: Inplace sorting

2007-03-13 Thread Karthik Singaram L
The question is not to print out a sorted array which we can easily do by inorder traversal. The question is to store the sorted array in the same array with constant extra space. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Goo

[algogeeks] Re: Inplace sorting

2007-03-13 Thread Manish Garg
if we can get an array of size n then no need to do this much complex... we can make inorder treversal and get the sorted array On 3/13/07, Atamurad Hezretkuliyev <[EMAIL PROTECTED]> wrote: > > Hi, > > I've been working with this problem and now i'm stuck. > > First of all, I assume N is in

[algogeeks] Re: Inplace sorting

2007-03-13 Thread Atamurad Hezretkuliyev
Hi, I've been working with this problem and now i'm stuck. First of all, I assume N is in in the form 2^x-1, i.e. complete binary tree With Inorder (L-n-R) traversal of binary tree we can print elements in sorted order but i couldn't use it to sort in-place within space&time bounds. void trave

[algogeeks] Re: Inplace sorting

2007-03-13 Thread Karthik Singaram L
To make things more easier just assume a complete binary search tree --~--~-~--~~~---~--~~ 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 unsubsc

[algogeeks] Re: Inplace sorting

2007-03-13 Thread Karthik Singaram L
And ofcourse radix sorts take o(nk) ...There is an O(n) algorithm for this problem in constant 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

[algogeeks] Re: Inplace sorting

2007-03-13 Thread Karthik Singaram L
A heap is a much more relaxed data structure than a binary search tree. Note that in a heap there is only relation between the parent and the siblings. Whereas in a binary search tree there exists a relationship between siblings also. --~--~-~--~~~---~--~~ You recei

[algogeeks] Re: Inplace sorting

2007-03-12 Thread Balachander
HI na, Thought of Heaps. FIXHEAP is O(n) Can we use Fix heap so that the Array obeys Heap's shape and value property.. Then We can disp .Level order Traversal. Note : But i am not sure about the Shape of givn Binary tree,,:) Waht has to be dne if it doesnt obey Heap's Shape property On Mar 13,

[algogeeks] Re: Inplace sorting

2007-03-12 Thread NUPUL
On Mar 13, 12:02 am, "Karthik Singaram L" <[EMAIL PROTECTED]> wrote: > Given a binary tree in an array in the standard representation with left and > right nodes being stored in 2i and 2i+1 for a node at position i. Assuming > that the array indices start at 1. This is how a "heap" is organized