优化比较次数的排序算法 (Ford Johnson Algorithm)

偶然发现 AtCoder，上去注册了准备试试，结果卡在 practice contest…

问题倒是很简单：

There are N balls labeled with the first N uppercase letters. The balls have pairwise distinct weights. You are allowed to ask at most Q queries. In each query, you can compare the weights of two balls (see Input/Output section for details). Sort the balls in the ascending order of their weights.

Constraints (N,Q)=(26,1000), (26,100), or (5,7).

Partial Score There are three testsets. Each testset is worth 100 points. In testset 1, N=26 and Q=1000. In testset 2, N=26 and Q=100. In testset 3, N=5 and Q=7.

通过比较排序，一共三种数据，其中 (26, 1000) 的情况用任何比较都能过，但是可能会 TLE，(26, 100) 的用 worst-case $O(nlgn)$ 的 merge sort 能过，唯一难受的是 (5, 7)。这个样例 merge sort 的 worst case 是比较 8 次。

我和某网友一样，尝试用 STL 的 sort 来解决，结果发现 WA 了更多 🙄

You must be kidding!

Ford-Johnson#

绝望之下只能求助 google，果然找到了一个算法叫 Ford-Johnson Algorithm，是 1959 年被提出来的，是针对比较排序中比较数进行最优化的算法，事实上在提出后的相当长一段时间被认为是比较数的 lower bound。

即便后来被证明能够进一步优化，Ford-Johnson 算法距离事实 lower bound 也极其接近。

在 Knuth 老爷子的《 The Art of Computer Programming 》第三卷中，该算法也被称为 merge-insertion sort。

算法流程#

假设我们有 n 个元素需要排序，算法总共分为三步：

将元素分为 $\lfloor n/2 \rfloor$ 对，并两两进行比较，如果 n 是奇数，最后一个元素不进行配对
递归地排序每对中大的那一个。现在我们有一个由每对中较大值组成的排过序的序列，叫做 main chain。假设 main chain 是 $a_1, a_2, ... a_{\lfloor n/2 \rfloor}$ ，剩余的元素假设他们是 $b_1, b_2, ..., b_{\lceil n/2\rceil}$ ，并且有 $b_i \le a_i$ 对 $i = 1, 2, ..., \lfloor n/2 \rfloor$ 成立。
现在我们将 $b_1, ..., b_{\lceil n/2 \rceil}$ 插入 main chain 中，首先是 $b_1$ ，我们知道他在 $a_1$ 前面，所以 main chain 变为 $\{b_1, a_1, a_2, ... a_{\lfloor n/2 \rfloor}\}$ ，然后考虑插入 $b_3$ ，仅需要比较三个数 $\{b_1, a_1, a_2\}$ ；假设前三个元素变为 $\{b_1, a_1, b_3\}$ ，那么插入 $b_2$ 也是在这三个数内；可以看到，不论 $b_3$ 被插入到那里了，要插入的范围总是最多为 3。下一个要插入的数 $b_k$ 对应于下一个Jacobsthal Number，即我们先插入 $b_3$ ，然后插入 $b_5, b_{11}, b_{21} ...$ ，总结一下插入顺序为 $b_1, b_3, b_2, b_5, b_4, b_{11}, b_{10}, ..., b_6, b_{21}, ...$

性能#

Ford-Johnson 算法需要特殊的数据结构来实现，运行速度并不算快，只是能够更少地进行比较，在实际使用中还是 merge sort 和 quick sort 来得更快一点。

问题 (5, 7)#

假设元素 A, B, C, D, E

比较 (A, B) 和 (C, D)，不失一般性，我们假设 A > B，C > D
比较 (A, C)，不失一般性，假设 A > C
将 E 插入 (D, C, A)，两次比较内完成
将 B 插入排序后的{E, C, D} 中 (因为 B < A，所以不需要考虑 A 的比较)，两次比较内完成

这里第三步先插入 E，是因为如果先插入 B 到 (D, C)，最多需要两次比较，而插入 E 到 {D, C, B, A} 最多要三次比较。

References#

[1] Bui, T. D., and Mai Thanh. “Significant improvements to the Ford-Johnson algorithm for sorting.” BIT Numerical Mathematics 25.1 (1985): 70-75.

[2] https://codereview.stackexchange.com/questions/116367/ford-johnson-merge-insertion-sort

Appendix#

Interactive Sorter in C++#

1
#include <iostream>
2
#include <algorithm>
3
#include <vector>
4
using namespace std;
5

6
bool less_than(char a, char b) {
7
    cout << "? " << a << " " << b << endl;
8
    cout.flush();
9
    char ans;
10
    cin >> ans;
11
    if (ans == '<') return true;
12
    return false;
13
}
14

15
void ford_johnson(string &s, int n) {
16
    // assert(n == 5)
17
    // ugly but work
18
    if (!less_than(s[0], s[1])) {
19
        swap(s[0], s[1]);
20
    }
21

22
    if (!less_than(s[2], s[3])) {
23
        swap(s[2], s[3]);
24
    }
25

26
    if (!less_than(s[1], s[3])) {
27
        swap(s[0], s[2]);
28
        swap(s[1], s[3]);
29
    }
30

31
    // now we have s[0] < s[1], s[2] < s[3], s[1] < s[3]
32
    vector<char> cs = {s[0], s[1], s[3]};
33

34
    // insertion will be completed in two comparations
35
    auto insert_into_first_three = [&](char c) {
36
        if (less_than(c, cs[1])) {
37
            if (less_than(c, cs[0])) cs.insert(cs.begin(), c);
38
            else cs.insert(cs.begin() + 1, c);
39
        } else {
40
            if (less_than(c, cs[2])) cs.insert(cs.begin() + 2, c);
41
            else cs.insert(cs.begin() + 3, c);
42
        }
43
    };
44

45
    insert_into_first_three(s[4]);
46
    // always sorted {s[0], s[1], s[4]} < s[3] or s[0] < s[1] < s[3] < s[4]
47
    // so the first three elements are enough
48
    insert_into_first_three(s[2]);
49

50
    s = string(cs.begin(), cs.end());
51
}
52

53
// at most 99 comparations for n = 26
54
void merge_sort(string &s, int n) {
55
    if (n == 1) return;
56
    else if (n == 2) {
57
        if (!less_than(s[0], s[1])) swap(s[0], s[1]);
58
        return;
59
    }
60

61
    auto left_half = s.substr(0, n / 2),
62
        right_half = s.substr(n / 2);
63

64
    merge_sort(left_half, n / 2);
65
    merge_sort(right_half, n - n / 2);
66

67
    // merge, at most n - 1 comparations
68
    int i = 0, j = 0, k = 0;
69
    while (k < n) {
70
        if (i >= n / 2) s[k++] = right_half[j++];
71
        if (j >= n - n / 2) s[k++] = left_half[i++];
72
        else if (less_than(left_half[i], right_half[j])) s[k++] = left_half[i++];
73
        else s[k++] = right_half[j++];
74
    }
75
}
76

77
int main() {
78
    int n, q;
79
    cin >> n >> q;
80

81
    string s;
82
    for (int i = 0; i < n; ++i) {
83
        s += 'A' + i;
84
    }
85

86
    if (n == 5) ford_johnson(s, n);
87
    else merge_sort(s, n);
88

89
    cout << "! " << s << endl;
90

91
    return 0;
92
}