I am currently going through Chapter 1 of the Training Gateway. In section 1.4, I’m reading the text for Greedy Algorithms. There is 1 part I do not understand:
Sorting a three-valued sequence [IOI 1996]
You are given a three-valued (1, 2, or 3) sequence of length up to 1000. Find a minimum set of exchanges to put the sequence in sorted order.
Algorithm The sequence has three parts: the part which will be 1 when in sorted order, 2 when in sorted order, and 3 when in sorted order. The greedy algorithm swaps as many as possible of the 1’s in the 2 part with 2’s in the 1 part, as many as possible 1’s in the 3 part with 3’s in the 1 part, and 2’s in the 3 part with 3’s in the 2 part. Once none of these types remains, the remaining elements out of place need to be rotated one way or the other in sets of 3. You can optimally sort these by swapping all the 1’s into place and then all the 2’s into place.
Analysis: Obviously, a swap can put at most two elements in place, so all the swaps of the first type are optimal. Also, it is clear that they use different types of elements, so there is no “interference” between those types. This means the order does not matter. Once those swaps have been performed, the best you can do is two swaps for every three elements not in the correct location, which is what the second part will achieve (for example, all the 1’s are put in place but no others; then all that remains are 2’s in the 3’s place and vice-versa, and which can be swapped).
Can you please explain the algorithm to me? What would be the 1 part, 2 part, and 3 part? How would we exchange the i's in the $j$th part and the j's in the $i$th part? Can you please show me a step-by-step example for this?
Additionally, how does the second section of the solution work (rotating elements)? Why would the best we can do be 2 swaps for every 3 elements not in the correct location?
I would also appreciate it if you can explain why this is greedy. What role does optimization play in this problem?