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

bucket-164265_1280
LINEで送る
Share on GREE
Share on LinkedIn

今回のアルゴリズム・ソースコードは今までの流れと少し変わっています。
これまでは、異なる乱数でのソートプログラムで、同数が存在していても、あまり気にしなかったのですが、
今回のバケットソートというのは、同一の数字をグループ化することで、ある一定のグルーピングされている数字がランダムに並んだ数字郡を
揃えて表示するというものです。
使い方は、なかなかイメージできないですが、とりあえず、比較的有名なソートアルゴリズムという事で、シリーズに加えたいと思います。

ソース

実行

解説

バケツ処理

バケツ配列を作って、そこには整数が入るという事が条件なので、乱数にマイナス値や、少数値が入っていると、
正常に動作しない。

バケツから1次元配列の作成

バケツには、同じ数字が入っている個数を値としていれているので、nullまたは0の状態のバケツは、処理をしない為、continueしている。

このソートの問題点

さらに、乱数の数字の幅が大きすぎると、単純にそれだけでメモリを食いつぶしてしまう。
このソートの使いみちとして、近似値の数値または、rangeが似通っているグループ郡に対して、処理することが前提になる。

ソース改修

単純に今回のプログラムでは、汎用性が少ないので、下記のように改修してみました。

変更点は、バケツ処理のところで、中に入っている個数を配列で格納するようにした。
整数の格納という条件は変わらないが、少し柔軟なグルーピングができるようになる。
例えば、0 – 100までの乱数がある場合、バケツが100個必要になってしまうが、
最初の処理として、10,20,30…という風に10のバケツには10-19、20のバケツには20-29という風に、まとめて入れ込むことで、
さらにバケツの中身を10-19の乱数をバケツ処理するという再帰処理的に行うことで、メモリ値を抑えて処理することができるようになる訳です。
でも、やはり、マイナス値や、小数点なども処理できるようにしなければイケないかな?

関連リンク

kiwipedia

マージソート記事

解説
Javascript

アルゴリズム過去記事

http://wordpress.ideacompo.com/?cat=562&tag=Algorithm

Leave a Reply

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です


*