バケットソートシリーズも後半の折り返しです。
大体、Shellで苦しんで、AWKで機能の少なさに嘆いて、C言語で肩の制御と、メモリ管理に悩んで、Go言語で触り慣れて無くて悩んで、Rubyで繰り返し分に悩むという毎回のこの連鎖です。
AWKは比較的直感的に書けるのですが、インクリメントが無かったり、配列での関数受け渡しができない、などのもどかしい言語です。
でも、OSにしっかりと入り込んでいる言語なので、重宝することは間違いないです。
普段からAWKに触り慣れておくと、良い事があるかもね。
ソース
BEGIN{
FS=",";
}
function bucketSort(numbers_str){
split(numbers_str , numbers , ",");
split("",bucket);
max=0;
for(i=1; i<=length(numbers); i++){
if(numbers[i] in bucket){}else{
bucket[numbers[i]] = 0;
}
bucket[numbers[i]] = bucket[numbers[i]] + 1;
if(max < numbers[i]){max = numbers[i];}
}
split("",arr);
num=1;
for(i=1; i<=max; i++){
if(i in bucket){}else{continue;}
for(j=1; j<=bucket[i]; j++){
arr[num] = i;
num = num + 1;
}
}
str = "";
for(i=1; i<=length(arr); i++){
if(arr[i]==""){continue;}
if(str == ""){ str = arr[i]; } else { str = str","arr[i]; }
}
return str;
}
{
print bucketSort($0);
}
実行
$ echo "1,1,3,2,4,6,1,2,4,6"|awk -f bucketSort.awk
1,1,1,2,2,3,4,4,6,6
解説
配列の要素確認
# 配列内に任意のkeyが含まれているかの確認
if(a in arr){
...[含まれている場合の処理]
}
else{
...[含まれていない場合の処理]
}
#今回は含まれていない場合のみの処理なので、以下のように書いた
if(i in bucket){}else{continue;}
空配列の定義
split("",arr);
関数への配列の受け渡しと戻し
基本的には、配列での扱いはできないと思ったほうがいいので、文字列で受け渡して文字列で戻す。
# 文字列で受け取って、配列に変換
split(numbers_str , numbers , ",");
# 戻す時に配列を文字列にする
str = "";
for(i=1; i< =length(arr); i++){
if(arr[i]==""){continue;}
if(str == ""){ str = arr[i]; } else { str = str","arr[i]; }
}
return str;
関連リンク
wikipedia
たくさんのプログラム言語でアルゴリズム学習
0 件のコメント:
コメントを投稿