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

2017年4月9日

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

今回のバケットソートは、全ての言語で共通の仕様にすることが難しく、言語毎に細かく仕様を変更してしまっています。 具体的には、多重配列が使える言語と使えない言語があるので、多重配列が使えない場合は、単次元配列で、中に入る数字は同じという事で、入っている個数の値を保持するようにしてます。 (ちなみに、多重配列が使える場合は、中に入る文字をそのまま2次元目の配列に放り込んでいます) ただ、改めて感じたのは、「出来ないことは無い」という事。

ソース

#!/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 たくさんのプログラム言語でアルゴリズム学習

このブログを検索

ごあいさつ

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