チェンジセット 35: python/exercise

コミット日時:

2006/09/24 00:51:15 (2 年前)

コミッタ:

sgk

ログメッセージ:

与えられた引数をいじらないように変更。

ファイル:

python/exercise/mergesort.py

r34	r35
17	17	'''
18	18
19		def mergeSort(a):
	19	def mergeSort(arg):
20	20	'''マージソート
21	21	タプルまたはリストを与える。
22	22	リストを返す。
23	23	'''
24		if len(a) < 2:
	24	if len(arg) < 2:
25	25	# 項目数が1以下なら、そのまま返す。0にはならないけど。
26	26	# リストじゃない場合のためにリストに変換。
27		return list(a)
	27	return list(arg)
28	28
29	29	# 真ん中付近で2つに分離して、それぞれソートする。再帰呼び出し。
30		n = len(a) / 2
31		(a, b) = (mergeSort(a~~[:n]), mergeSort(a~~[n:]))
	30	n = len(arg) / 2
	31	(a, b) = (mergeSort(arg[:n]), mergeSort(arg[n:]))
32	32
33	33	# マージする。

r34	r35
28	28
29	29	# [1, 2, 3] ==> [[1], [2], [3]]
30		arg = [[x] for x in arg]
	30	sorting = [[x] for x in arg]
31	31
32	32	# [[1, 2, 3]]という形になるまで繰り返す。
33		while len(arg) > 1:
	33	while len(sorting) > 1:
34	34
35	35	# リストの長さの半分（端数は切り下げ）まで繰り返す。
36	36	# 端数が出た場合には右端の1個が処理されないが気にしない。
37		for offset in xrange(len(arg) / 2):
	37	for offset in xrange(len(sorting) / 2):
38	38
39	39	# 着目点offsetから2個を取り出して、
40		a = arg[offset]
41		b = arg[offset + 1]
	40	a = sorting[offset]
	41	b = sorting[offset + 1]
42	42
43	43	# マージする。
…	…
50	50
51	51	# 取り出した2個の部分を、マージされた物で置き換える。
52		arg[offset:offset+2] = [r + a + b]
	52	sorting[offset:offset+2] = [r + a + b]
53	53
54		return arg[0]
	54	return sorting[0]
55	55
56	56