A compare-exchange operation on two array elements A[i] and A[j], where i < j, has the form COMPARE-EXCHANGE (A, i, j)

1     If A[i] > A[j]

2         exchange A[i] with A[j]

After the compare-exchange operation, we know that A[i] ‰¤ A[j]. 

An oblivious compare-exchange algorithm operates solely by a sequence of prespecified compare-exchange operations. The indices of the positions compared in the sequence must be determined in advance, and although they can depend on the number of elements being sorted, they cannot depend on the values being sorted, nor can they depend on the result of any prior compare-exchange operation. For example, here is insertion sort expressed as an oblivious compare-exchange algorithm:

INSERTION-SORT (A)

1     for j = 2 to A.length

2         for i = j €“ 1 down to 1

3             COMPARE-EXCHANGE (A, i, i + 1)

The 0-1 sorting lemma provides a powerful way to prove that an oblivious compare-exchange algorithm produces a sorted result. It states that if an oblivious compare-exchange algorithm correctly sorts all input sequences consisting of only 0s and 1s, then it correctly sorts all inputs containing arbitrary values.

You will prove the 0-1 sorting lemma by proving its contrapositive: if an oblivious compare-exchange algorithm fails to sort an input containing arbitrary values, then it fails to sort some 0-1 input. Assume that an oblivious compare-exchange algorithm X fails to correctly sort the array A[1 . . n]. Let A[p] be the smallest value in A that algorithm X puts into the wrong location, and let A[q] be the value that algorithm X moves to the location into which A[p] should have gone. Define an array B[1. . n] of 0s and 1s as follows:

a. Argue that A[q] > A[p], so that B[p] = 0 and B[q] = 1.

b. To complete the proof of the 0-1 sorting lemma, prove that algorithm X fails to sort array B correctly.

Now you will use the 0-1 sorting lemma to prove that a particular sorting algorithm works correctly. The algorithm, columnsort, works on a rectangular array of n elements. The array has r rows and s columns (so that n = rs), subject to three restrictions:

• r must be even,
• s must be a divisor of r, and
• r 2s².

When columnsort completes, the array is sorted in column-major order: reading down the columns, from left to right, the elements monotonically increase. 

Columnsort operates in eight steps, regardless of the value of n. The odd steps are all the same: sort each column individually. Each even step is a fixed permutation. Here are the steps:

1. Sort each column.

2. Transpose the array, but reshape it back to r rows and s columns. In other words, turn the leftmost column into the top r/s rows, in order; turn the next column into the next r/s rows, in order; and so on.

3. Sort each column.

4. Perform the inverse of the permutation performed in step 2.

Figure 8.5 

The steps of columnsort. (a) The input array with 6 rows and 3 columns. (b) After sorting each column in step 1. (c) After transposing and reshaping in step 2. (d) After sorting each column in step 3. (e) After performing step 4, which inverts the permutation from step 2. (f) After sorting each column in step 5. (g) After shifting by half a column in step 6. (h) After sorting each column in step 7. (i) After performing step 8, which inverts the permutation from step 6. The array is now sorted in column-major order.
5. Sort each column.
6. Shift the top half of each column into the bottom half of the same column, and shift the bottom half of each column into the top half of the next column to the right. Leave the top half of the leftmost column empty. Shift the bottom half of the last column into the top half of a new rightmost column, and leave the bottom half of this new column empty.
7. Sort each column.
8. Perform the inverse of the permutation performed in step 6.

Figure 8.5 

shows an example of the steps of columnsort with r = 6 and s = 3. (Even though this example violates the requirement that r ‰¥ 2s², it happens to work.)

c. Argue that we can treat columnsort as an oblivious compare-exchange algorithm, even if we do not know what sorting method the odd steps use. Although it might seem hard to believe that columnsort actually sorts, you will use the 0-1 sorting lemma to prove that it does. The 0-1 sorting lemma applies because we can treat columnsort as an oblivious compare-exchange algorithm. A couple of definitions will help you apply the 0-1 sorting lemma. We say that an area of an array is clean if we know that it contains either all 0s or all 1s. Otherwise, the area might contain mixed 0s and 1s, and it is dirty. From here on, assume that the input array contains only 0s and 1s, and that we can treat it as an array with r rows and s columns.

d. Prove that after steps 1€“3, the array consists of some clean rows of 0s at the top, some clean rows of 1s at the bottom, and at most s dirty rows between them.

e. Prove that after step 4, the array, read in column-major order, starts with a clean area of 0s, ends with a clean area of 1s, and has a dirty area of at most s² elements in the middle.

f. Prove that steps 5€“8 produce a fully sorted 0-1 output. Conclude that columnsort correctly sorts all inputs containing arbitrary values.

g. Now suppose that s does not divide r. Prove that after steps 1€“3, the array consists of some clean rows of 0s at the top, some clean rows of 1s at the bottom, and at most 2s €“ 1 dirty rows between them. How large must r be, compared with s, for columnsort to correctly sort when s does not divide r?

h. Suggest a simple change to step 1 that allows us to maintain the requirement that r ‰¥ 2s² even when s does not divide r, and prove that with your change, columnsort correctly sorts.

Transcribed Image Text:

0 if A[i] < A[p] , 1 if A[i] > A[p] . B[i] = 10 4 10 11 17 12 16 18 14 4 8 10 9 13 15 11 14 12 16 12 3 17 16 11 11 14 15 12 15 14 13 6. 16 18 3 13 15 17 17 18 (a) (b) (d) 12 4 10 5 11 17 6 12 18 10 16 11 13 16 13 17 12 8 14 15 18 14 9 15 (f) (g) (h) (i) 6795으 으느뜨 으느의 으으으 4 89의 으 으