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.
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
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
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
@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
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
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
--~--~-~--~~~-
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
@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
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
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
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
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
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
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
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,
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
17 matches
Mail list logo
