Now in the case of non complete BSTs it may run into trouble...I never
handled them. It will work for complete BSTs though as it is. Refer to
a previous thread in algogeeks where i had posted the thread "inplace
sorting" and look at the solution by atamurad for the explanation.
--~--~-~--
Karthik,
Sorry for this but I still can't understand your program.
Can you describe it for me or give an example of how it works.
Will it work even in the case of non-complete BST, I mean for every
BST?
--~--~-~--~~~---~--~~
You received this message because you
An unique BST does exist for such an array if you assume the root to
be 1, then automatically you will be able to fix the left and right
children of the root and so on.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Karthik,
Can you please explain what your algorithm is doing?
If I am not wrong, we are given a BST in an array form meaning 'i'th
element has children at indices '2i' and '2i+1' right?
Does a unique BST exist for such an array (I believe it does), how to
prove?
--~--~-~--~~
i am sorry that is a[i] = ++cnt
I made a mistake when pasting the code...
--~--~-~--~~~---~--~~
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 un
On Mar 25, 4:17 pm, "leiz" <[EMAIL PROTECTED]> wrote:
> Sorry, I thought populatetest was part of the solution. I havent run
> your code, but it seems not correct and have you tested it before you
> posted here?
>
> in your populatetest
>
> a=++cnt;
it is a syntax error.
*a = ++cnt changes a[0
Sorry, I thought populatetest was part of the solution. I havent run
your code, but it seems not correct and have you tested it before you
posted here?
in your populatetest
a=++cnt;
doesnt it change a[0] only?
I am pretty amazed if you can do constant space. Can you explain your
algo?
On Mar
for(i=1; i<=n; i++) {
p= calc_m1(i)*calc_m2(i) + calc_m1(i)/2;
if((pi && a[p]>a))
continue;
j=i;
while(p!=i)
{
temp = a[j];
a[j] = a[p];
a[p] = temp;
p = calc_m1(p)*calc_m2(p) + calc_m1(p)/2;
}
}
Isnt this constant space (assuming that the array a is given already).
Since calc_m1 and calc_m2 are
I think your algo uses O(n) space too
On Mar 25, 6:50 am, "Karthik Singaram L" <[EMAIL PROTECTED]>
wrote:
> yes...but you can sort without constant space using the posted algorithm
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the
yes...but you can sort without constant space using the posted algorithm
--~--~-~--~~~---~--~~
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 uns
#include
#include
#include
#include
#define MAXN 2000
int a[MAXN];
int cnt = 0;
int log2n;
int n;
void populatetestcase(int i)
{
if(i*2<=n) populatetestcase(i*2);
a=++cnt;
if(i*2+1<=n) populatetestcase(i*2+1);
}
int calc_x(int i)
{
return (int)log2l((double)i);
}
int calc_m1(int i)
{
return 1
hi,
U get sorted numbers if u traverse the BST in inorder..so if u traverse the
array following inorder u get sorted list and also u visit each index
onceso its O(n)...
with regards,
koushik chitta
On 3/24/07, vim <[EMAIL PROTECTED]> wrote:
>
>
> hi guys
> plz explain how to sort elements of
12 matches
Mail list logo
