The problem was:
You have an size $n$ array of zeroes, ones and twos. The only write operation is to reverse a sub-array (paying cost equal to the length of the the sub-array). Can we sort the array in $O(n \log n)$ cost?
Solution
One solution is to use divide and conquer.
Suppose you divided the array into two approximately equal halves, and sorted each sub-array separately.
Then you will see an array like
$$0 \dots 0 1 \dots 12 \dots 2\vert 0 \dots 0 1 \dots 1 2 \dots 2$$
Now, we can sort a chunk of 2s and 0s by doing a cyclic shift of the chunk $2 \dots 2 0 \dots 0$, so that it looks like $ 0 \dots 0 2 \dots 2$.
We can do a cyclic shift of an array using only three reversals. Say you want to cyclic shift $a_1, \dots a_m$ to look like $a_k, a_{k+1}, \dots, a_m, a_1, a_2, \dots a_{k-1}$. This we can achieve by first reversing $a_1, \dots a_{k-1}$ and $a_k \dots a_m$, so the array now looks like $a_{k-1}, \dots a_1, a_m, \dots a_{k+1}, a_k$ and then reversing the whole array.
Each reverse costs $O(n)$, and with a constant number of these, give the two sorted halves, we can sort the whole array.
Thus the cost satisfies the recurrence
$$ C(n) = 2 C(n/2) + O(n)$$
which gives us $C(n) = O(n \log n)$.
You have an size $n$ array of zeroes, ones and twos. The only write operation is to reverse a sub-array (paying cost equal to the length of the the sub-array). Can we sort the array in $O(n \log n)$ cost?
Solution
One solution is to use divide and conquer.
Suppose you divided the array into two approximately equal halves, and sorted each sub-array separately.
Then you will see an array like
$$0 \dots 0 1 \dots 12 \dots 2\vert 0 \dots 0 1 \dots 1 2 \dots 2$$
Now, we can sort a chunk of 2s and 0s by doing a cyclic shift of the chunk $2 \dots 2 0 \dots 0$, so that it looks like $ 0 \dots 0 2 \dots 2$.
We can do a cyclic shift of an array using only three reversals. Say you want to cyclic shift $a_1, \dots a_m$ to look like $a_k, a_{k+1}, \dots, a_m, a_1, a_2, \dots a_{k-1}$. This we can achieve by first reversing $a_1, \dots a_{k-1}$ and $a_k \dots a_m$, so the array now looks like $a_{k-1}, \dots a_1, a_m, \dots a_{k+1}, a_k$ and then reversing the whole array.
Each reverse costs $O(n)$, and with a constant number of these, give the two sorted halves, we can sort the whole array.
Thus the cost satisfies the recurrence
$$ C(n) = 2 C(n/2) + O(n)$$
which gives us $C(n) = O(n \log n)$.
No comments:
Post a Comment