[アルゴリズム] バケットソート（Shell編）
今回のバケットソートは、全ての言語で共通の仕様にすることが難しく、言語毎に細かく仕様を変更してしまっています。
具体的には、多重配列が使える言語と使えない言語があるので、多重配列が使えない場合は、単次元配列で、中に入る数字は同じという事で、入っている個数の値を保持するようにしてます。（ちなみに、多重配列が使える場合は、中に入る文字をそのまま２次元目の配列に放り込んでいます）
ただ、改めて感じたのは、「出来ないことは無い」という事。
ソース
|
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 |
#!/bin/bash function bucketSort(){ numbers=(`echo $1 | tr -s ',' ' '`) bucket=() max=0 for((i=0;i<${#numbers[@]};i++)){ if [ -z ${bucket[${numbers[$i]}]} ];then bucket[${numbers[$i]}]=0 fi bucket[${numbers[$i]}]=`echo "${bucket[${numbers[i]}]}+1"|bc` if [ $max -lt ${numbers[$i]} ];then max=${numbers[$i]} fi } arr=() num=1 for((i=0;i<=$max;i++)){ if [ -z ${bucket[i]} ];then continue fi for((j=0;j<${bucket[i]};j++)){ arr[$num]=$i num=`echo "$num+1"|bc` } } echo ${arr[@]} } res=(`bucketSort $1`) echo ${res[@]} |
実行
|
1 2 |
$ bash bucketSort.sh 1,1,3,2,4,6,1,2,4,6 1 1 1 2 2 3 4 4 6 6 |
解説
配列に値が入っているか確認
jsのtypeof、phpのisset、こういった便利機能はshellには存在しません。
下記のように、-z条件を使って、値がブランクかどうかを確認しましょう。
デメリットとしては、keyのみセットされている場合はブランクなので、keyの存在確認ではないことを注意すること。
今回のアルゴリズムは、「値がある＝配列が有効」という事なので、これで良し
|
1 2 3 |
if [ -z ${bucket[i]} ];then continue fi |
ちょこっと計算
他の言語の様に(…)という計算をさっくり入れることが難しいshell言語。
少しもどかしいですが、手順としては、...とコマンドを実行させて、中身でechoして、bcしてあげるだけなので、お作法を覚えて怖がらずに行きましょう。
|
1 2 3 |
num=`echo "1+2+3"|bc` echo $num > 6 |
配列の扱いでの注意点
shellは変数の扱いが非常にもどかしい言語です。
定義の時や、代入の時は、
|
1 |
test="hoge" |
とするんですが、参照する時は、
|
1 2 |
echo $test echo ${test} |
という風に、$…や${…}というフォーマットで扱わなければいけない。
こういう仕様と割り切るしか無いんですが、非常に間違いやすく、再代入や、追記の時に$を取り忘れることがあるので、
注意しましょう。
関連リンク
マージソート記事
解説
Javascript
PHP
Python
Shell