--/--/--

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

2007/07/01

[今日のスクリプト] マージソート

B4 Wiki - 問題集より、マージソート。

 1 #!/usr/bin/python
 2 #coding:utf-8
 3 
 4 def merge2(list1, list2):
 5     i = 0
 6     j = 0
 7     len1 = len(list1)
 8     len2 = len(list2)
 9     result = []
10     while i < len1 or j < len2:
11         if j >= len2 or (i < len1 and list1[i] < list2[j]):
12             result.append(list1[i])
13             i += 1
14         else:
15             result.append(list2[j])
16             j += 1
17     return result
18 
19 def merge2_old(list1, list2):
20     larger = list1
21     smaller = list2
22     if len(list1) < len(list2):
23         larger, smaller = smaller, larger
24     for val in smaller:
25         larger.append(val)
26         larger.sort()
27     return larger
28 
29 def mergeN(list):
30     if len(list) < 2:
31         return list
32     for n in list:
33         result = merge2(result, n)
34     return result
35 
36 def main():
37     print merge2([3,4,6,8], [2,4,7])
38     print mergeN([[2,3], [2,6], [5,9]])
39 
40 if __name__ == "__main__":
41     main()

結果

$ python merge.py
[2, 3, 4, 4, 6, 7, 8]
[2, 2, 3, 5, 6, 9]
  • merge2のほうはだいぶ邪道な気がする。今度調べて正攻法を学ぼう。
  • 2html.vimを使ってみた。<font>タグ使ってるのが気にくわないけど、まぁ見やすいしよかろうってことで。

追記

最初に書いたmerge2をmerge2_oldに、マージソートがどんなもんか調べて書いたのをmerge2として追加。merge2_oldはマージソートにすらなってない。

スポンサーサイト

comment

post




上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。