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