[アルゴリズム] 挿入ソートの実装（Python編）
挿入ソートにおけるPythonは、僕が今までコーディングしたPython言語で最長のプログラムになってしまいました。
あえて、そうしたという事もありますが、配列操作の勉強になったので、まあ結果良しということにしましょう。
そして、多言語構成をそのまま持ってきたので修正ボリュームもなかなかのものとなってしまいました。
ソースコード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
#coding: UTF-8 # 基本関数 def insertSort(numbers): # 数値配列を最初から順番に評価していく for i in range(1 , len(numbers)): # 確定数値リストを取得 confirmLists = getConfirmLists(numbers , i) # 対象外の数値リストを取得 lastLists = getLastLists(numbers , i) # 確定数値リストに挿入数値の挿入 ##print "setInsert : " , i ," : ", numbers , " : " , confirmLists , " : " , numbers[i] firstLists = setInsert(confirmLists , numbers[i]) # リストの結合 numbers = setUnionLists(firstLists , lastLists) return numbers ## # 確定数値リストに対象数値が挿入される位置を取得する # [Summery] # 返り値の手前に挿入される # 数値リストよりも指定数値の方が大きい場合はnullが返る->数値の後ろに追加 # @param : confirmLists | 確定数値リスト # @param : targetNum | 対象数値 # @return : number or null | 挿入位置番号 def getInsertPlace(confirmLists , targetNum): num = None for i in range(0 , len(confirmLists)): if targetNum <= confirmLists[i]: num = i break if num is None: num = len(confirmLists) return num # 全体数値リストから確定数値リストを取得 # @param : numbers | 全体数値リスト # @param : targetNum | 対象数値番号 # @return : array | 確定数値リスト def getConfirmLists(numbers , targetNum): arr = [] for i in range(0 , len(numbers)): if i == targetNum: break arr.append(numbers[i]) return arr # 数値リストの挿入 # @param : confirmLists | 確定数値リスト # @param : targetNum | 対象数値 # @return : array | 数値入れ替え後の全体数値リスト def setInsert(confirmLists , targetNum): # 確定数値リストに対象数値が挿入される位置を取得する replaceNum = getInsertPlace(confirmLists , targetNum) # 挿入操作 arr = [] if replaceNum == len(confirmLists): confirmLists.append(targetNum) arr = confirmLists else: for i in range(0 , len(confirmLists)): if i == replaceNum: arr.append(targetNum) arr.append(confirmLists[i]) return arr # リストの結合 # @param : firstLists | 確定数値リスト # @param : lastLists | 対象外数値リスト # @return : array | 入れ替え後の全体数値リスト def setUnionLists(firstLists , lastLists): arr = [] if len(firstLists) > 0: for i in range(0, len(firstLists)): arr.append(firstLists[i]) if len(lastLists) > 0: for i in range(0, len(lastLists)): arr.append(lastLists[i]) return arr # 対象外の数値リストを取得 # @param : numbers # @param : targetNum # @return : array | 対象外リスト def getLastLists(numbers , targetNum): arr = [] for i in range(targetNum+1, len(numbers)): arr.append(numbers[i]) return arr # 実行 res = insertSort([10,2,12,7,16,8,13]) print res |
解説
nullではなくてNone
Pythonはnull使えないんですね。「None」です。
しかも、if文での扱いは”hoge == null”ではなく、”hoge is None”です。
ググればすぐにわかるんですが、多言語と違う点なので、慣れるのに少し時間かかりそうです。
for文のrangeに注意
今までなんとなく使ってたので奇跡的に問題なかったのですが、”for i in range(0,10)”とした場合、
内部で扱われるiに入る値は”0~9″になります。
これてっきり”0~10″だと思っていて-1していたので、バグの温床でした。
型に注意
PHPもJavascriptも型に関しては非常に緩い言語として有名ですが、Pythonは比較的しっかり管理したほうがよさそうです。
これまでのプログラムでは、挿入位置を返していた関数で、対象値よりも大きい数値がなく、挿入箇所がない場合（一番うしろに追加する場合）
nullを返して対応してましたが、returnで数値とnullという２つの型を同じ変数で対応するのが問題だと考えて、
null（None）ではなく、配列番号の最大値＋１という仕様に変更しています。
実行
|
1 2 |
$ python insertSort.py [2, 7, 8, 10, 12, 13, 16] |
多言語で同じプログラムを書くと、言語に引っ張られる記述をすることもありますが、それまで書いてきたプログラムで動かない事による、より慎重な記述ができるようになり、この点はまあまあプラスと言ってもいいのではないでしょうか？
プログラマーのスキルは書き込んだプログラムコードの行数に比例するという説はまあまあ正しいのではないかと考えられますね。
あくまで一般論ですが・・・
関連リンク
挿入ソート
アルゴリズム過去記事
http://wordpress.ideacompo.com/?cat=562&tag=Algorithm