### 8-4 Water jugs

Suppose that you are given n red and n blue water jugs, all of different
shapes andsizes. All red jugs hold different amounts of water, as do the
blue ones. Moreover,for every red jug, there is a blue jug that holds
the same amount of water, and vice versa.

Your task is to ﬁnd a grouping of the jugs into pairs of red and blue
jugs that hold the same amount of water. To do so, you may perform the
following operation: pick a pair of jugs in which one is red and one is
blue, ﬁll the red jug with water, and then pour the water into the blue
jug. This operation will tell you whether the red or the blue jug can
hold more water, or that they have the same volume. Assume that such a
comparison takes one time unit. Your goal is to ﬁnd an algorithm that
makes a minimum number of comparisons to determine the grouping.
Remember that you may not directly compare two red jugs or two blue
jugs.

1. Describe a deterministic algorithm that uses $\theta(n^2)$
comparisons to group the jugs into pairs.
2. Prove a lower bound of Ω(n lg n) for the number of comparisons that
an algorithm solving this problem must make.
3. Give a randomized algorithm whose expected number of comparisons is
O(n lg n), and prove that this bound is correct. What is the
worst-case number of comparisons for your algorithm?

2.其实水壶问题，就是一个变相的排序问题，例如，我们先将红壶依次摆开，然后给他

3.快速排序恰好满足这种要求,只不过与a相似比较的对象是另一种颜色的水壶,其最坏情

### 8-5 Average sorting

Suppose that, instead of sorting an array, we just require that the
elements increase on average. More precisely, we call an n-element array
A k-sorted if, for all i = 1;2,…,n - k, the following holds: 1. What does it mean for an array to be 1-sorted?
2. Give a permutation of the numbers 1;2;….;10 that is 2-sorted, but
not sorted.
3. Prove that an n-element array is k-sorted if and only if
A[i] <= A[i+k] for all i =1;2;…;n-k.>
4. Give an algorithm that k-sorts an n-element array in O(n lg(n/k))time.
We can also show a lower bound on the time to produce a k-sorted
array, when k is a constant.
5. Show that we can sort a k-sorted array of length n in O(n lg k)time.
(Hint:Use the solution to Exercise 6.5-9. )
6. Show that when k is a constant, k-sorting an n-element array requires
Ω(n lg n) time. (Hint: Use the solution to the previous part along with
the lower bound on comparison sorts.)

1. 意味着它与普通排序完全一样。
2. 2,1,3,4,6,5,8,7,9,10。
3. 反证法：若有任意i使得A[i]>A[i+k],那么题设不总是成立。
4. 使用合并排序，当待排序的数目，小于等于k时停止递归。其递归深度为lg(n/k)。
5. 根据c我们可以得出，对于一个k-排列的数组，我们可以得出k个有序的子数组，例如
对于一个2-排列的2n个元素的数组我们可以得出两个2个有序的子数列：第一个为
k1 <= k3
6. 又是一个关于比较排序的下限证明的问题，由c可知，对于一个k-排序的数组来说，必
须满足一个条件：按照e的方法生成的k个数组必然是有序的。所以问题f可以看做是，
对k组数目为n/k的数组进行比较排序。余下，略。