The problem was to sort an almost complete binary search tree, which is represented as an array: the children of $a[i]$ are $a[2i]$ and $a[2i+1]$.
The catch was to sort in $O(n)$ time and using $O(1)$ space.
[Detailed problem statement is here]
Solution
The solution depends on the following
1) If $a[1], a[2], \dots, a[2^k-1]$ is already sorted, then we can sort $a[1], a[2], \dots, a[2^{k+1}-1]$ by interleaving $$\{a[1], a[2], \dots, a[2^k-1]\}\quad \{a[2^k], a[2^k+1], \dots, a[2^{k+1}-1]\}$$ as
$$ a[2^k], a[1], a[2^k+1], a[2], \dots, a[2^{k+1} -2], a[2^k-1], a[2^{k+1}-1]$$
Now this interleaving can be done on linear time and constant space, using the solution in the blog post here: http://ruffnsluff.blogspot.com/2015/01/solution-to-rearrange-array-algorithm.html
So starting with $k=1$ and so on, we can do this in time $n + n/2 + n/4 + \dots$ = $O(n)$ and $O(1)$ space.
[Sorry for the terse solution, I suggest you try it out with a few examples].
The catch was to sort in $O(n)$ time and using $O(1)$ space.
[Detailed problem statement is here]
Solution
The solution depends on the following
1) If $a[1], a[2], \dots, a[2^k-1]$ is already sorted, then we can sort $a[1], a[2], \dots, a[2^{k+1}-1]$ by interleaving $$\{a[1], a[2], \dots, a[2^k-1]\}\quad \{a[2^k], a[2^k+1], \dots, a[2^{k+1}-1]\}$$ as
$$ a[2^k], a[1], a[2^k+1], a[2], \dots, a[2^{k+1} -2], a[2^k-1], a[2^{k+1}-1]$$
Now this interleaving can be done on linear time and constant space, using the solution in the blog post here: http://ruffnsluff.blogspot.com/2015/01/solution-to-rearrange-array-algorithm.html
So starting with $k=1$ and so on, we can do this in time $n + n/2 + n/4 + \dots$ = $O(n)$ and $O(1)$ space.
[Sorry for the terse solution, I suggest you try it out with a few examples].
No comments:
Post a Comment