You are given an array $A$ of $n$ elements, each element being either $0$ or $1$ or $2$.
You want to sort the array.
The catch is, the only write operation you can do on the array is pick two any two indices $i \le j$, and reverse the contiguous portion of the array from $A[i]$ to $A[j]$, i.e. after the operation, $A[i]$ and $A[j]$ are swapped, $A[i+1]$ and $A[j-1]$ are swapped, $\dots ,A[i+k]$ and $A[j-k]$ are swapped (where $k \approx (i+j)/2$).
Let's say we call this operation the splice-reverse.
Can you sort the array using $O(n)$ splice-reverses?
[Solution. Also see comments below]
You want to sort the array.
The catch is, the only write operation you can do on the array is pick two any two indices $i \le j$, and reverse the contiguous portion of the array from $A[i]$ to $A[j]$, i.e. after the operation, $A[i]$ and $A[j]$ are swapped, $A[i+1]$ and $A[j-1]$ are swapped, $\dots ,A[i+k]$ and $A[j-k]$ are swapped (where $k \approx (i+j)/2$).
Let's say we call this operation the splice-reverse.
Can you sort the array using $O(n)$ splice-reverses?
[Solution. Also see comments below]
The comment editor seems to have eaten my first response. I apologize if this is a duplicate
ReplyDeleteI have not seen this formulation before but is seems very similar to Dijkstra's problem of the Dutch national flag. The same solution seems to work. The reversal does more work than is strictly needed; all we really need to do is swap the endpoints of the a subarray.
define 3 locals a0, a1, a2 that point to locations in a where the next 0 1 or 2 is to be placed.
a0 = a1 = 0;
a2 = n-1
// a1 will always point to the lowest bound of the unknown region of the array
examine a[a1]
case 0:
reverse(a0,a1) a0++; a1++;
case 1:
a1++
case 2
reverse(a1,a2); a2--
until the unknown region is empty (a1> a2)
You are absolutely correct! This does indeed look like the Dutch National Flag problem, and if I understand your post correctly, you are claiming we can do a swap of any two elements using two reversals?
DeleteIf so, I agree, and that will give us an O(n) splice-reversal algorithm.
Well done.
What I was trying to say (but I was not very clear), is that reverse(i,j) has the side effect of being a swap(i,j) it just also does some other stuff (that for this problem is neither helpful or hurtful.
Deletereverse(a1,a2) in my construction exchanges the newly discovered 2 at a1 for the higher index unknown as indicated by a2. The fact that it also flips around all the other unknowns in between them makes no difference.
I see. I did misunderstand. I am not really sure that flipping the intermediates is not a problem. You might undo some work done earlier, right? (like swapping a 0 and 2 might move around some 0s and 1s?)
DeleteIn any case, even if the intermediates are a problem, we can just do another reverse and put them back as they were, so any variant of the dutch national flag algorithm still works.
FYI: I have posted a second version of the problem. Hope you find that interesting too.
DeleteConsider the array at some point in time
ReplyDelete0000111UUUUUUU22222
0 1 2
The second numbers are a0 a1 and a2. By definition the region from a[0] to a[a0-1] are all 0; from a[a0] to a[a1-1] are all 1; from a[a1] to a[a2] are all U and from a[a2] to a[n-1] are all 2
So reverse(a0,a1) swaps a 1 into a[a1] and a newly discovered 0 into a[a0] everhing else that is reversed is a 1
similarly reverse(a1,a2) swaps a U from a[a2] into a[a1} and a newly discovered 2 from a[a1] into a[a2] . All the remaining elements in the region being reversed were unknown and remain so.
Hope that makes sense
The editor made my decorated array not line up...I need a non proportional font!
DeleteWhat I was trying to show was the following invariant:
a1 <= a2 <=a3 <= n-1
AND
a[0] through a[a0-1] are all 0
a[a0] through a[a1-1] are all 1
a[a1] through a[a2-1] are all U for Unknown
a[a2] through a[n-1] are all 2
You are right! I agree. Thanks for the explanation.
Delete