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, \dots, j]$ and then reverse $A[i+1, \dots, 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, \dots, j]$ and then reverse $A[i+1, \dots, 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