[アルゴリズム] バケットソート(Python編)

2017年4月7日

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

現存のWEBプログラム言語で、一番直感的にコーディングできるのは、Javascriptだと実感しています。 慣れもありますが、変数の型の扱いの緩さや、それをコントロールする術が、直感的に行えるのですが、今回扱ったPythonコードでは、多次元配列や多次元辞書においてのkeyの扱いが、厳密に行わないといけないことから、言語の注意ポイントを改めて認識できた。 大きなプログラムを構築する時は、厳密に管理出来たほうが便利なのだが、スピード速くコーディングするようなスポーツプログラムの場合は、少しもどかしく感じてしまう。 感覚は人それぞれだが、こうした事を慣れていくことが、コーダーのスキルアップなのだという事ですね。

ソース

#coding: UTF-8 def bucketSort(numbers): # バケツ bucket = {} max = 0 # バケツに入れる数字の数を足し込む for i in range(0 , len(numbers)): if (numbers[i] in bucket) == False: bucket[numbers[i]] = [] bucket[numbers[i]].append(numbers[i]) if max < numbers[i] : max = numbers[i] # 並び替え用配列(リスト) arr = [] # 数字の入っている数分配列(リスト)データを作成 for i in range(0 , max+1): if (bucket.has_key(i)) == False: continue for j in range(0 , len(bucket[i])): arr.append(bucket[i][j]) return arr numbers = [3,1,3,2,4,6,1,2,4,6] numbers = bucketSort(numbers) print numbers

実行

$ python bucketSort.py [1, 1, 2, 2, 3, 3, 4, 4, 6, 6]

解説

配列(リスト)と辞書(ディクショナリ)の存在確認

pythonはkeyの存在しない配列や辞書にアクセスしようとしたら、errorで止まります。 なので、key存在確認は確実に行いましょう。 # 元データ arr = ["a" , "b" , "c"] obj = {"a":"aa" , "b":"bb" , "c":"cc"} # 配列と辞書でkeyが存在することを確認 "a" in arr # True "d" in arr # False "a" in obj # True "d" in obj # False # 辞書で使える存在確認 obj.has_key("a") # True obj.has_key("d") # Flase 注意点としては、TrueとFalseは、大文字をちゃんと区別して記入しないと「true / false」のように書くとErrorになります。 もう一つ注意点があり、if文内でこの記述をするときは、ちゃんと(...)で囲わないと、Errorになります。

配列と辞書の定義

今回bucketを配列ではなくて辞書で定義しています。 理由としては、Pythonでの配列は、存在しないkeyが存在すると、そのkey値を"0"で埋めてしまうため、今回の処理がうまく動作しなかったためです。 という事で、改めて定義は以下のように行いましょう。 # 配列の定義 arr = [] # 辞書の定義 obj = {}

関連リンク

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

このブログを検索

ごあいさつ

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