Sorting
a Three-Valued
Sequence

Sorting is one of the most frequently done computational tasks. Consider the special sorting problem, where the records to be sorted have at most three different key values. This happens for instance when we sort medalists of a competition according to medal value, that is, gold medalists come first, followed by silver , and bronze medalists come last.

In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. Sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers p and q, exchanges the elements in positions p and q.

You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted. (Subtask A). Moreover, construct a sequence of exchange operations for the respective sorting (Subtask B).

Input Data

The first line of file INPUT.TXT contains the number of records N (1<=N<=1000). Each of the following N lines contains a key value.

Output Data

Write on the first line of file OUTPUT.TXT the minimal number L of exchange operations needed to make the sequence sorted (Subtask A). The following L lines give the respective sequence of the exchange operations in the order performed. Each line contains one exchange operation described by two numbers p and q, the positions of the two elements to be exchanged (Subtask B). Positions are denoted by the numbers from 1 to N.

Example Input and Output

INPUT.TXT          OUTPUT.TXT     

9                  4              
2                  1 3            
2                  4 7            
1                  9 2            
3                  5 9           
3                                 
3                                 
2                                 
3                                 
1

Solution (Yogy Namara) :

First we calculate the range of 1's, 2's and 3's in the sorted sequence. Keys from 1..r[1] should be 1's, keys from r[1]+1..r[2] should be 2's, and keys from r[2]+1 to r[3] should be 3's.

Swapping two keys is called perfect if both are in their proper places after the swap, and is called semi-perfect if only one key is in its proper place after the swap (these are my own terminology, feel free to laugh )

First we will place all 1's in their range. We will try to perform perfect swaps if possible, and perform a semi-perfect swap only if not. Second, we will place all 2's in their range. Since all 1's are in their places by now, we will have to deal with the 3's only. This means that these swaps will all be perfect swaps.

yogy-n@sby.mega.net.id GeoCities