AtCoder: L - Interactive Sortingを力技でなくFord-Johnson Algorithmで最速で解く

公開:2020/12/12
更新:2021/03/03
5 min読了の目安(約4900字TECH技術記事

Ford Johnson Algorithmの実装コードがPythonでは初めてらしく、Algorithms/PythonにPRがマージされました

https://github.com/TheAlgorithms/Python/pull/2211

【問題】

https://atcoder.jp/contests/language-test-202001/tasks/practice_2

【実装】
・テストケース1, 2 : マージソートで実装
・テストケース3 : Ford-Johnson Algorithm(merge insert sort)で実装

【コード】

N, Q = map(int, input().split())
S = [chr(ord('A') + i) for i in range(N)]

def compare(a, b):
    print("?", a, b, flush=True)
    return input()

# テストケース1, 2
def merge_sort(collection):
    def merge(left, right):
        result = []
        while left and right:
            if compare(left[0], right[0]) == "<":
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        return result + left + right

    length = len(collection)
    if length <= 1:
        return collection
    middle = length // 2
    return merge(merge_sort(collection[:middle]), merge_sort(collection[middle:]))

# テストケース3
def merge_insertion_sort(collection):
    def binary_search_insertion(sorted_list, item):
        left = 0
        right = len(sorted_list) - 1
        while left <= right:
            middle = (left + right) // 2
            if left == right:
                if compare(sorted_list[middle], item) == "<":
                    left = middle + 1
                    break;
                else:
                    break;
            elif compare(sorted_list[middle], item) == "<":
                left = middle + 1
            else:
                right = middle - 1
        sorted_list.insert(left, item)
        return sorted_list

    def sortlist_2d(list_2d):
        def merge(left, right):
            result = []
            while left and right:
                if compare(left[0][0], right[0][0]) == "<":
                    result.append(left.pop(0))
                else:
                    result.append(right.pop(0))
            return result + left + right

        length = len(list_2d)
        if length <= 1:
            return list_2d
        middle = length // 2
        return merge(sortlist_2d(list_2d[:middle]), sortlist_2d(list_2d[middle:]))

    if len(collection) <= 1:
        return collection

    two_paired_list = []
    is_surplus      = False
    for i in range(0, len(collection), 2):
        if (i == len(collection) - 1):
            is_surplus = True
        else:
            if compare(collection[i], collection[i+1]) == "<":
                two_paired_list.append([collection[i], collection[i+1]])
            else:
                two_paired_list.append([collection[i+1], collection[i]])
    sorted_list_2d = sortlist_2d(two_paired_list)
    result = [i[0] for i in sorted_list_2d]
    result.append(sorted_list_2d[-1][1])

    if is_surplus:
        pivot = collection[-1]
        result = binary_search_insertion(result, pivot)

    is_surplus_inserted_before_this_index = False
    for i in range(len(sorted_list_2d) - 1):
        if result[i] == collection[-1]:
            is_surplus_inserted_before_this_index = True
        pivot = sorted_list_2d[i][1]
        if is_surplus_inserted_before_this_index:
            result = result[:i+2] + binary_search_insertion(result[i+2:], pivot)
        else:
            result = result[:i+1] + binary_search_insertion(result[i+1:], pivot)

    return result

if len(S) == 5:
    print('!', ''.join(merge_insertion_sort(S)))
else:
    print('!', ''.join(merge_sort(S)))

【解説】
Ford-Johnson Algorithmは、N<11の際に最適であることが証明されているソート法です。(参照: https://en.wikipedia.org/wiki/Merge-insertion_sort)
テストケース3はマージソートでは計算量O(n log n)で、最悪時に8回必要となり間に合いません。

そこで別の解法が必要となるのですが、過去の解答や記事ではif文を多重したり、全組合せをpermutationsで出して探索する力技な解法が多いようでした。

実際、全体数が5なら解法自体はすぐに思いつくのでif文でも突破可能です

1. AとBを比較。小さい順にA, Bへ再代入。(max 1回)
2. CとDを比較。小さい順にC, Dへ再代入。(max 1回)
3. AとCを比較。この時A<CならばA<C<D。(max 1回)
4. Eについて、A<C<D内でソート(max 2回)
5. Bについて、A<Bは順序1で確実なので、[A,C,D,E(順はランダム)]の中でAより大きい範囲でソート。(max C,D,Eの範囲でソートする場合の2回)

1 + 1 + 1 + 2 + 2 = 7。

しかし本問題のケースではN<11なのでFord-Johnson Sortを用いる事で解法でき、かつ上限数をクリアできます。せっかくなのでアルゴリズムでスマートに解いてみます。処理の流れは下記の通りです。

1. 2つずつの組合せを作る 例: [[C, B], [E, D], [F, A], Z] この時Zは一旦外す。
2. 2つずつの組合せをsortする 例: [[B, C], [D, E], [A, F]]
3. 2つずつの組合せの先端をsortする 例: [[A, F], [B, C], [D, E]]

この時図に表すと

  D B A    ぼっち(放置中)
  | | |   
  E C F    Z

となっています。

4. 上段で最大値のDよりもEが大きい事は手順2で確実なので、上段の最大位置に配置する

  E D B A     ぼっち(放置中)
      | |
      C F     Z

5. 放置中のZをABDE内でsortします(図では最悪時の場合の、最大位置にsortされてます)

  Z E D B A
        | |
        C F

6. 上段最小のAのペアであるFについて、A<Fは手順2で確実なので、Aを除いたB,D,E,Z内でsortします(図では最悪時の場合の、最大位置にsortされてます)

  F Z E D B A
          |
          C

7. 次にBのペアであるCについて、B<Cは手順2で確実なので、A, Bを除いたD,E,Z,F内でsortします

  C F Z E D B A

この手順で完成です。

【単体としての成果品】

https://github.com/ulwlu/merge_insertion_sort

なにか間違えや、指摘などございましたら是非お教えください。

Thanks

このリポジトリがなかったら理解にたどり着けませんでした。Clojureで書かれた実装。ちなみに間違えが一点実はあるのですが、その間違いについては上記の自分のリポジトリで説明しています。(画像の説明ミスなので、PRできない・・・涙)

https://github.com/decidedlyso/merge-insertion-sort