[アルゴリズム] マージソートのプログラミング(Python編)

2017年3月15日

Python テクノロジー プログラミング 特集

マージソートを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

関連記事

たくさんのプログラム言語でアルゴリズム学習

このブログを検索

ごあいさつ

このWebサイトは、独自思考で我が道を行くユゲタの少し尖った思考のTechブログです。 毎日興味がどんどん切り替わるので、テーマはマルチになっています。 もしかしたらアイデアに困っている人の助けになるかもしれません。