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

commits5 min read読了の目安(約4600字

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