マージソート
研究やばいんちゃうんか、っていう突っ込みはなしで。
マージソートがひとまず完成した。
一時は自分の力のなさにどうなることかと思ったけど、何とかなるもんだ。
実は参考にしていたサイト↓
Algorithms with Python / 整列 (ソート)
でのソースコードがうまく動いてくれなかった。
自分でそれを見ながらごちゃごちゃといじっていたが結局は解決せずorz
C言語どおりの実装方法は現在の自分の力ではできなかった。
なので、「元の配列の前半部分を移した作業用配列と元の配列の後半」というのではなく「前半部分・後半部分・それらをマージした配列」というなんともメモリ効率のよろしくないプログラムとなった。
でも一応動くし、こっちの方がソースの流れを追っかけやすいかと自負しております。
# MergeSort def merge(numList): if len(numList) <= 1: return numList mid = len(numList) / 2 former_numList = [numList[i] for i in range(mid)] latter_numList = [numList[i] for i in range(mid, len(numList))] merged_numList = [] print "former_numList -> ", former_numList print "latter_numList -> ", latter_numList former_numList = merge(former_numList) latter_numList = merge(latter_numList) i = 0 j = 0 k = 0 while i < len(former_numList) and j < len(latter_numList): if former_numList[i] <= latter_numList[j]: merged_numList.append(former_numList[i]) k += 1 i += 1 else: merged_numList.append(latter_numList[j]) k += 1 j += 1 if i < len(former_numList) or j < len(latter_numList): if i < len(former_numList): while i < len(former_numList): merged_numList.append(former_numList[i]) k += 1 i += 1 else: while j < len(latter_numList): merged_numList.append(latter_numList[j]) k += 1 j += 1 print "merged_List -> ", merged_numList print return merged_numList def main(): import random numList = [random.randint(1,1000) for i in range(20)] print numList print merge(numList) if __name__ == "__main__": main()
実行結果
D:\workspace\Python\2-22>python MergeSort.py [993, 246, 226, 564, 64, 420, 79, 596, 683, 74, 295, 553, 668, 475, 612, 975, 47 8, 470, 877, 967] former_numList -> [993, 246, 226, 564, 64, 420, 79, 596, 683, 74] latter_numList -> [295, 553, 668, 475, 612, 975, 478, 470, 877, 967] former_numList -> [993, 246, 226, 564, 64] latter_numList -> [420, 79, 596, 683, 74] former_numList -> [993, 246] latter_numList -> [226, 564, 64] former_numList -> [993] latter_numList -> [246] merged_List -> [246, 993] former_numList -> [226] latter_numList -> [564, 64] former_numList -> [564] latter_numList -> [64] merged_List -> [64, 564] merged_List -> [64, 226, 564] merged_List -> [64, 226, 246, 564, 993] former_numList -> [420, 79] latter_numList -> [596, 683, 74] former_numList -> [420] latter_numList -> [79] merged_List -> [79, 420] former_numList -> [596] latter_numList -> [683, 74] former_numList -> [683] latter_numList -> [74] merged_List -> [74, 683] merged_List -> [74, 596, 683] merged_List -> [74, 79, 420, 596, 683] merged_List -> [64, 74, 79, 226, 246, 420, 564, 596, 683, 993] former_numList -> [295, 553, 668, 475, 612] latter_numList -> [975, 478, 470, 877, 967] former_numList -> [295, 553] latter_numList -> [668, 475, 612] former_numList -> [295] latter_numList -> [553] merged_List -> [295, 553] former_numList -> [668] latter_numList -> [475, 612] former_numList -> [475] latter_numList -> [612] merged_List -> [475, 612] merged_List -> [475, 612, 668] merged_List -> [295, 475, 553, 612, 668] former_numList -> [975, 478] latter_numList -> [470, 877, 967] former_numList -> [975] latter_numList -> [478] merged_List -> [478, 975] former_numList -> [470] latter_numList -> [877, 967] former_numList -> [877] latter_numList -> [967] merged_List -> [877, 967] merged_List -> [470, 877, 967] merged_List -> [470, 478, 877, 967, 975] merged_List -> [295, 470, 475, 478, 553, 612, 668, 877, 967, 975] merged_List -> [64, 74, 79, 226, 246, 295, 420, 470, 475, 478, 553, 564, 596, 6 12, 668, 683, 877, 967, 975, 993] [64, 74, 79, 226, 246, 295, 420, 470, 475, 478, 553, 564, 596, 612, 668, 683, 87 7, 967, 975, 993]
中級者以上の人には冗長すぎて読みにくいのかな。
でも、初心者の僕としては、再帰のいい勉強になったと思う。
同時にもう少し勉強してエレガントなコードを書きたいという欲求も出てきた。
いい傾向だ！
