[アルゴリズム] クイックソートの実装(Awk編)

2017年2月18日

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

t f B! P L
WEBサービスを作っているエンジニアをしている場合、どのくらいの割合でShellスクリプトをコーディングするかを少し考えてみたが、サーバーバッチを作る時以外はないだろうと考えた。 ただ、個人的には、LinuxOSでは必ず動作するこの言語を利用しない手はなく、ちゃんとした書き方をしておけば、サーバー間における汎用性は半端なく高いのではないかと考えられるので、かなり強力なスクリプト言語だと考えてます。 そうそう、MacOSXもUNIXベースなので、Linuxと同じと考えてもいいですね。

ソース

BEGIN{ FS=","; } function mid(x , y , z){ if (x < y) { if (y < z) {return y;} else if (z < x) {return x;} else {return z;} } else { if (z < y) {return y;} else if (x < z) {return x;} else {return z;} } } function quickSort(numbers_str , begin , end){ split(numbers_str , numbers , ","); if(begin != "null" && end != "null" && (end - begin) <= 1){ res = numbers[1]; for(i=2; i<=length(numbers); i++){ res = res","numbers[i]; } return res; } # 左辺と右辺の開始位置を定義 if(begin == "null"){begin = 1;} if(end == "null"){end = length(numbers);} left = begin; right = end; if(begin >= end){ res = numbers[1]; for(i=2; i<=length(numbers); i++){ res = res","numbers[i]; } return res; } # ピボット(中央の値) pivot = mid(numbers[left] , numbers[left + int((right-left) / 2)] , numbers[right]); # ソート処理実行(pivotが交差するまで続行) while(1){ # 左辺のpivotよりも大きい値見つける while(numbers[left] < pivot){left++;} # 右辺のpivotよりも小さい値をみつける while(numbers[right] > pivot){right--;} # pivotが交差したら終了 if(left >= right){break;} # 値の入れ替え処理 tmp = numbers[left]; numbers[left] = numbers[right]; numbers[right] = tmp; # 繰り返し対応 left++; right--; } # pivotの左辺のソート処理 numbers_str = numbers[1]; for(i=2; i<=length(numbers); i++){ numbers_str = numbers_str","numbers[i]; } numbers_str = quickSort(numbers_str , begin , left); # pivotの右辺のソート処理 numbers_str = numbers[1]; for(i=2; i<=length(numbers); i++){ numbers_str = numbers_str","numbers[i]; } numbers_str = quickSort(numbers_str , right , end); # res numbers_str = numbers[1]; for(i=2; i<=length(numbers); i++){ numbers_str = numbers_str","numbers[i]; } return numbers_str; } { res = quickSort($0 , "null" , "null"); print res; }

実行

$ echo "10,2,12,7,16,8,13"|awk -f quickSort.awk 2,7,8,10,12,13,16

解説

nullの扱い

AWKでは、null値も0もif文において同じ判定をされてしまうので、型がちゃんと制御できない言語では、それを逆手に取って文字列の"null"を使用することにしました。 C言語のように型が厳密に管理されなくてはいけない言語では、この方法は使えないのですが、型の緩い言語ならではの方法かもしれません。

関数との配列のやりとり

AWKにおける関数では配列のやりとりはご法度なため、いちいち","カンマ区切りの文字列に変換してから行います。 非常にめんどくさいやり方ですが、他にいい方法があれば使いたいんですが、今のところできるのはこれぐらいですね。 しかも少し得意なやり方をしていて、最初の配列1番目を定義しておいて、その後for文で文字列に追記する形です。 numbers_str = numbers[1]; for(i=2; i<=length(numbers); i++){ numbers_str = numbers_str","numbers[i]; } return numbers_str;

整数化

Awkでもint関数は使えます。 int((right-left) / 2) こんな感じで問題なく使えます。

参考リンク

クイックソート

解説 Javascript PHP Python Shell Awk

アルゴリズム過去記事

http://wordpress.ideacompo.com/?cat=562&tag=Algorithm

このブログを検索

プロフィール

自分の写真
町田市, 東京都, Japan
プログラミングとサーバーを心の底から楽しむクリエーターです。 経営者であり、開発者でもありますが、得意としているのは、アイデア創出です。

ブログ アーカイブ

QooQ