Combinatorial Optimization: Merge-Sort Algorithm

組合せ最適化: アルゴリズム 1.2 マージソートアルゴリズム

B.コルテ/J.フィーゲン 著「組合せ最適化 理論とアルゴリズム 第2版」の例を Python で実装してみる。

 

	#!/usr/bin/env python
	# -*- coding: utf-8 -*-
	"""
	Combinatorial Optimization - B.Korte, J.Vygen
	Algorithm 1.2
	Merge-Sort Algorithm
	"""
	def merge_sort(a):
	"""
	Recursive Merge-Sort
	Returns mapping function {0 .. n-1} -> {0 .. n-1}
	"""
	n = len(a)
	# step 1 (stopping condition)
	if n == 1:
	return lambda x: x # Returns identity mapping.
	# step 2 (call recursive function)
	m = n / 2
	r = merge_sort(a[:m])
	s = merge_sort(a[m:])
	# step 3 (merge two lists)
	ret = [None] * n
	k = 0
	l = 0
	while k < m and l < n - m:
	if a[r(k)] <= a[m + s(l)]:
	ret[k + l] = r(k)
	k += 1
	else:
	ret[k + l] = m + s(l)
	l += 1
	while k < m:
	ret[k + l] = r(k)
	k += 1
	while l < n - m:
	ret[k + l] = m + s(l)
	l += 1
	return lambda x: ret[x]
	def merge_sort_simple(a):
	"""Returns sorted list."""
	n = len(a)
	if n == 1:
	return a
	r, s = (merge_sort_simple(xs) for xs in (a[:n / 2], a[n / 2:]))
	ret = []
	while r and s:
	ret.append(r.pop(0) if r[0] <= s[0] else s.pop(0))
	return ret + r + s
	if __name__ == '__main__':
	for a in ([1, 3, 5, 2, 4, 90, -1, 0, -2],
	['ac', 'c', 'bc', 'ca', 'bb', 'b'],
	[9.9, 8.8, 7.7, 6.6, 5.5, 4.4, 3.3, 2.2, 1.1, 0.0]):
	f = merge_sort(a)
	print([a[f(i)] for i in range(len(a))])
	print(merge_sort_simple(a))
	print(sorted(a)) # builtin function

view raw a01_2_merge_sort_algorithm.py hosted with ❤ by GitHub

output

1 2 3 4 5 6 7 8 9

[-2, -1, 0, 1, 2, 3, 4, 5, 90] [-2, -1, 0, 1, 2, 3, 4, 5, 90] [-2, -1, 0, 1, 2, 3, 4, 5, 90] ['ac', 'b', 'bb', 'bc', 'c', 'ca'] ['ac', 'b', 'bb', 'bc', 'c', 'ca'] ['ac', 'b', 'bb', 'bc', 'c', 'ca'] [0.0, 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9] [0.0, 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9] [0.0, 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9]

identity が出てくるのが面白い。