マージソートをpythonで実装するのは、そんなに難しくないですね。
それは、配列操作も、関数操作も、かなり直感的にコーディングできるからです。
何か新しい命令でも入れようかと思ったんですが、今回は無難なコーディングにしています。
ソースコード
#coding: UTF-8
def midPoint(nums):
return int((len(nums) / 2) + 0.5)
def setMerge(arr1 , arr2):
arr = []
while len(arr1) or len(arr2):
if len(arr1) == 0:
arr.append(arr2.pop(0))
elif len(arr2) == 0:
arr.append(arr1.pop(0))
elif arr1[0] > arr2[0]:
arr.append(arr2.pop(0))
else:
arr.append(arr1.pop(0))
return arr
def mergeSort(numbers):
if len(numbers) == 0:
return [];
elif len(numbers) == 1:
numbers = numbers
elif len(numbers) == 2:
if numbers[0] > numbers[1]:
tmp = numbers[0]
numbers[0] = numbers[1]
numbers[1] = tmp
else:
midNum = midPoint(numbers)
arr1 = numbers[0 : midNum]
arr2 = numbers[midNum :]
arr1 = mergeSort(arr1)
arr2 = mergeSort(arr2)
numbers = setMerge(arr1 , arr2)
return numbers
numbers = [20,10,2,12,7,16,8,13,1]
numbers = mergeSort(numbers)
print numbers
実行
$ python mergeSort.py
[1, 2, 7, 8, 10, 12, 13, 16, 20]
解説
Pythonの配列操作
# 配列に要素追加
arr = [1,2]
arr.append(3,4)
> arr = [1,2,3,4]
# 配列の先頭を取得して元データを削除
arr = [5,4,3,2,1]
num = arr.pop(2)
> num = 3
> arr = [5,4,2,1]
# 空の配列データを定義
arr = []
# 配列の要素を範囲で取得
arr = [5,4,3,2,1]
nums = arr[2:3]
> nums = [3,2]
# 後方全て
arr = [5,4,3,2,1]
nums = arr[2:]
> nums = [3,2,1]
# 前方全て
arr = [5,4,3,2,1]
nums = arr[:3]
> nums = [5,4,3,2]
if文の構文
# 一般
if aa == 0:
b = 0
elif aa == 1:
b = 1
else:
b = 2
# 複数の条件文の結合
if aa == 0 and aa == 1:
b = 0
elif aa == 2 or aa == 3:
b = 1
else:
b = 2
配列の要素数
arr = [5,4,3,2,1]
print len(arr)
> 5
関連記事
たくさんのプログラム言語でアルゴリズム学習
0 件のコメント:
コメントを投稿