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

2017年2月25日

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

t f B! P L
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に近いと感じたの僕だけなんでしょうか?

参考リンク

クイックソート

解説 Javascript PHP Python Shell Awk C言語 Go言語 Ruby

アルゴリズム過去記事

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

このブログを検索

プロフィール

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

ブログ アーカイブ

QooQ