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

2017年4月11日

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

バケットソートシリーズも後半の折り返しです。 大体、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 たくさんのプログラム言語でアルゴリズム学習

このブログを検索

ごあいさつ

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