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

2017年2月25日

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

Ruby言語が何故人気があるのか、未だに分からずにコーディングしているんですが、コーディングスピードは確かに早く書ける言語であると言えるでしょう。 後述してますが、改めてshell文と似ている箇所が多く、サーバーサイドエンジニアから好かれているのではないでしょうか? そういやfluentdもrubyで書かれていたな・・・関係ないかな?

ソース

def mid(x , y , z) if x < y then if y < z then return y elsif z < x then return x else return z end else if z < y then return y elsif x < z then return x else return z end end end def quickSort(numbers , beginNum , endNum) if endNum - beginNum <= 1 then return numbers end # 左辺と右辺の開始位置を定義 leftNum = beginNum rightNum = endNum if beginNum >= endNum then return numbers end # ピボット(中央の値) midNum = leftNum + ((rightNum - leftNum)/2) pivot = mid(numbers[leftNum] , numbers[midNum] , numbers[rightNum]) # ソート処理実行(pivotが交差するまで続行) while true do # 左辺のpivotよりも大きい値見つける while numbers[leftNum] < pivot do leftNum = leftNum + 1 end # 右辺のpivotよりも小さい値をみつける while numbers[rightNum] > pivot do rightNum = rightNum - 1 end # pivotが交差したら終了 if leftNum >= rightNum then break end # 値の入れ替え処理 tmp = numbers[leftNum] numbers[leftNum] = numbers[rightNum] numbers[rightNum] = tmp # 繰り返し対応 leftNum = leftNum + 1 rightNum = rightNum - 1 end # pivotの左辺のソート処理 numbers = quickSort(numbers , beginNum , leftNum ) # pivotの右辺のソート処理 numbers = quickSort(numbers , rightNum , endNum) return numbers end numbers = [10,2,12,7,16,8,13] print quickSort(numbers , 0 , numbers.count-1) ,"\n"

実行

$ ruby quickSort.rb [2, 7, 8, 10, 12, 13, 16] そんなに解説がいらないソースコードなので、実行も非常に簡素に完了しました。

解説

予約語対策

今まで多言語で発生しなかった世や予約語制限に引っかかってしまいました。 begin,end この2つをそのまま使っているとどうしてもエラーになってしまうので、 beginNum , endNum として対応しました。 そして、類似で念のため、leftとrightも変更。

while文

ruby言語のwhile文を初めて使ってみましたが、下記の構文で扱えばいいだけなので、非常に楽ですね。 while 条件 do ... end なんだかshellに近いと感じたの僕だけなんでしょうか?

関連記事

アルゴリズム学習

このブログを検索

ごあいさつ

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