The problem was to sort an array consisting of only 0,1,2 only using O(n) reversals of subarrays.
When I posted this problem, I had one solution in mind (which I will not reveal just now, but try to reuse for the next problem), without realizing that swapping A[i] and A[j] can be done using two reversals: reverse A[i,…,j] and then reverse A[i+1,…,j−1]!
So any sorting algorithm which uses O(n) swaps should do.
For example, using the Dutch National Flag (DNF) algorithm, we can achieve sorting in O(n) reversals.
Collins made a nice observation that if we use the DNF algorithm, we don't even need to do the second reverse when trying to swap A[i],A[j]. See the comments on the question.
When I posted this problem, I had one solution in mind (which I will not reveal just now, but try to reuse for the next problem), without realizing that swapping A[i] and A[j] can be done using two reversals: reverse A[i,…,j] and then reverse A[i+1,…,j−1]!
So any sorting algorithm which uses O(n) swaps should do.
For example, using the Dutch National Flag (DNF) algorithm, we can achieve sorting in O(n) reversals.
Collins made a nice observation that if we use the DNF algorithm, we don't even need to do the second reverse when trying to swap A[i],A[j]. See the comments on the question.
No comments:
Post a Comment