algorithm - 如何使用 2n/3 比较对 0/1 数组进行排序？

Question

在Algorithm Design Manual , 有这样的消费税

4-26 Consider the problem of sorting a sequence of n 0’s and 1’s using comparisons. For each comparison of two values x and y, the algorithm learns which of x < y, x = y, or x > y holds.

(a) Give an algorithm to sort in n − 1 comparisons in the worst case. Show that your algorithm is optimal.

(b) Give an algorithm to sort in 2n/3 comparisons in the average case (assuming each of the n inputs is 0 or 1 with equal probability). Show that your algorithm is optimal.

对于(a)，我觉得还是比较容易的。我可以选择a[n-1]作为主元，然后做类似快速排序分区的事情，扫描0到n - 2，找到左边全为0，右边全为1的中间点，这需要n - 1次比较.

但是对于 (b)，我无法得到线索。它说“n 个输入中的每一个都是 0 或 1 的概率相等”，所以我想我可以假设 0 和 1 的数量相等吗？但是我怎样才能得到与 1/3 相关的结果呢？把整个数组分成3组？

谢谢

Answer 1

“0 或 1 的概率相等”是“平均”情况的条件。其他情况的时机可能更差。

提示 1:2/3 = 1/2 + 1/8 + 1/32 + 1/128 + ...

提示 2:将序列视为成对的序列，并比较每对中的项目。一半将返回相等；一半不会。在不相等的那一半中，您知道对中的哪一项是 0，哪一项是 1，因此不需要再进行比较。