c++ - 算法:仅使用比较对 0/1 的序列进行排序

Question

我正在努力提高我的算法知识，并试图解决 Skiena 的算法设计手册中的以下问题:

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 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) 的解决方案:

void sort(int arr[], int length) {
    int last_zero = -1;
    for (int i = 1; i < length; i++) {
        if (arr[i] < arr[i-1]) {
            int tmp = arr[i];
            arr[i] = arr[++last_zero];
            arr[last_zero] = tmp;
        } else if (arr[i] > arr[i-1]) {
            last_zero = i-1;
        }
    }
    return;
}

有更好的方法吗？

我不确定如何处理 (b) 部分。还有一个类似的问题here但我不明白那里的解释。

编辑:显然这被认为太模糊了，所以让我根据回复进行跟进。

我正在跟进@amit 的回复。这部分我不太明白:

(such that i_k != i_h for k!= h, i_k != i_h for k!= h, and i_k != j_h for all k,h).

无论如何，我想我大致理解您提出的解决第 (b) 部分的想法。然而，当我尝试为其编写代码时，我发现它很难完成。这是我到目前为止所拥有的，根据我的测试，它成功地对所有 (0,1) 和 (1,0) 对进行排序，并将相等的对推到数组的末尾，所以我最终得到 {all zeros, all ones , 相等对}。我试图实际移动数组元素，而不是计算 0 和 1 的数量。我坚持如何从我目前所拥有的开始:

int compare(int a, int b);
void shift_right(int arr[], int start, int end);
int prob_4_26_b(int arr[], int length) {
    int last_zero = -1;
    int last_one = -1;
    for (int i = 0; i < length; i += 2) {
        int tmp = compare(arr[i], arr[i+1]);
        int cur_zero, cur_one;
        if (tmp == 0) {
            continue;
        }

        cur_zero = i;
        cur_one = i + 1;
        /* We have a 0 and a 1 */
        /* If this is the first zero we have put it at index 0
         and shift everything from index 0 to cur_zero-1 right by 1.
         last_zero = 0 and if there are ones last_one++ */
        if (last_zero == -1) {
            int start = 0;
            int end = cur_zero - 1;
            shift_right(arr, start, end);
            arr[0]=0;
            last_zero = 0;
            if (last_one != -1) {
                last_one++;
            }
        }
        /* If this is not the first zero we have then put it at
         last_zero+1 and shift everything from last_zero+1 to cur_zero-1
         right by 1. last_zero++ and if we have ones last_one++. */
        else {
            int start = last_zero + 1;
            int end = cur_zero - 1;
            shift_right(arr, start, end);
            arr[last_zero+1] = 0;
            last_zero++;
            if (last_one != -1) {
                last_one++;
            }
        }

        /* If this is the first one we have put it after the last_zero.
         Shift everything from last_zero+1 to cur_one-1 right by 1.
         last_one = last_zero+1. */
        if (last_one == -1) {
            int start = last_zero + 1;
            int end = cur_one-1;
            shift_right(arr, start, end);
            arr[last_zero+1] = 1;
            last_one = last_zero + 1;
        }
        /* If this is not the first one we have put it at last_one+1
         and shift everything from last_one+1 to cur_one-1 right by 1.
         last_one++ */
        else {
            int start = last_one + 1;
            int end = cur_one - 1;
            shift_right(arr, start, end);
            arr[last_one+1] = 1;
            last_one++;
        }
    }
    return 0;
}

void shift_right(int arr[], int start, int end) {
    for (int i = end; i >=start; i--) {
        arr[i+1] = arr[i];
    }
}

int compare(int a, int b) {
    if (a < b)
        return -1;
    else if (a > b)
        return 1;
    else
        return 0;
}

Answer 1

为了做第二部分，你需要先实现检查comp(a[i], a[i+1]) , 和 comp(a[i+1], a[i+2])不无关系。第一个的答案可能会帮助您获得第二个的答案。

要使用它，首先将序列分成对，(a[i1],a[j1]), (a[i2],a[j2]),..., (a[i_n/2], a[j_n/2]) . (例如 i_k != i_h for k!= h，i_k != i_h for k!= h，i_k != j_h for all k,h)。

比较每一对。平均而言(假设位均匀分布)，您将得到 n/4 个结论性答案 a[i] < a[j]或者反过来，对于剩下的 n/4，你将拥有平等。

所以，首先你可以很容易地对那些有结论的答案进行排序(开头越小，结尾越大)。

接下来，您将在提醒上递归调用算法。但是这里是“技巧”，如果你知道一些i,j : a[i] = a[j] ，你不需要得到两者的答案。其中一个的答案也会告诉您第二个的值。
这意味着您可以递归调用仅 n/4 个元素，而不是 n/2(平均)。

停止子句是当你有一个元素时，只需将它与 0 进行比较了解它的值(value)。

这为您提供了以下复杂度函数:

T(1) = 1
T(n) = n/2 + T(n/4)

经过一些数学运算找到此递归公式(或 consulting with wolfram alpha)的近似形式后，您会发现 T(n) = (2n+1)/3