# [PYTHON] Solve AtCoder: L-Interactive Sorting test case 3 with Ford-Johnson Algorithm instead of multiple if statements or brute force

【Implementation】 ・ Test cases 1, 2: Implemented by merge sort ・ Test case 3: Implemented by Ford-Johnson Algorithm (merge insert sort)

【code】

``````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()

#Test case 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:]))

#Test case 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)))
``````

[Explanation] The Ford-Johnson Algorithm is a sorting method that has proven to be optimal when N <15. Test case 3 has a computational complexity of O (n log n) in merge sort, which requires 8 times in the worst case and is not in time.

Therefore, another solution is needed, but in the past answers and articles, it seems that there are many powerful solutions that multipleize if statements and search for all combinations by permutations.

In fact, if the total number is 5, the solution itself can be thought of immediately, so it is possible to break through with an if statement.

``````1.Compare A and B. A in ascending order,Reassign to B.(max 1 time)
2.Compare C and D. C in ascending order,Reassign to D.(max 1 time)
3.Compare A and C. At this time A<If C, then A<C<D。(max 1 time)
4.About E, A<C<Sort within D(max 2 times)
5.About B, A<B is certain in order 1, so[A,C,D,E(The order is random)]Sort in a range larger than A.(max C,D,Twice when sorting by E range)

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

In the case of this problem, N <15, so it can be solved by using the Ford-Johnson Algorithm. The processing flow is as follows.

``````1.Example of making a combination of two: [[C, B], [E, D], [F, A], Z]At this time, remove Z once.
2.Example of sorting two combinations: [[B, C], [D, E], [A, F]]
3.Example of sorting the tip of a combination of two: [[A, F], [B, C], [D, E]]

At this time, if you show it in the figure

D B A Bocchi(Left unattended)
| | |
E C F    Z

It has become.

4.Since it is certain in step 2 that E is larger than the maximum value D in the upper row, place it at the maximum position in the upper row.

E D B A Bocchi(Left unattended)
| |
C F     Z

5.Sort the neglected Z in ABDE (in the figure, it is sorted to the maximum position in the worst case)

Z E D B A
| |
C F

6.For F, which is the smallest pair of A in the upper row, A<Since F is certain in step 2, B excluding A,D,E,Sort in Z (in the figure, it is sorted to the maximum position in the worst case)

F Z E D B A
|
C

7.Next, for C, which is a pair of B, B<C is certain in step 2, so A,D excluding B,E,Z,Sort in F

C F Z E D B A

``````

This procedure is complete.

[Ford-Johnson Algorithm repository] I couldn't find the Python implementation code for this algorithm, so I created the repository below.

https://github.com/ryuta69/merge_insertion_python/blob/master/merge_insertion.py

## Summary

Please let us know if you have any mistakes or suggestions.

Recommended Posts