[アルゴリズム] マージソートのプログラミング（Ruby編）
Ruby言語とPython言語は、コーディングした見た目が誰が書いても分かりやすいと聞くが、いままでそれは、言語的に遊びがないからだと思っていた。
確かにインデントなどの扱いでエラーになる言語なので、単純にインデントだけの話だと思っていたが、今回のプログラムを書いて気がついたのだが、
ものの１０分程度で完了できた。
基本的にはPHPプログラムのローカライズをしただけなのだが、関数や変数、その他の処理など、そのまま移していくことでほとんどエラーも出ずに完了できた。
そして、コーディングもほぼブレがなく、誰が書いても大体同じという事なのだろう。
C言語やshellなどと違いこんなに早く終わったので、拍子抜けではあるが、とりあえず今回はこんな感じ。
ソースコード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
def midPoint(nums) return ((nums.count / 2) + 0.5).floor end def setMerge(arr1 , arr2) arr = [] while arr1.count > 0 || arr2.count > 0 do if arr1.count == 0 then arr.push(arr2.shift) elsif arr2.count == 0 then arr.push(arr1.shift) elsif arr1[0] > arr2[0] then arr.push(arr2.shift) else arr.push(arr1.shift) end end return arr end def mergeSort(numbers) if numbers.count == 0 then numbers = [] elsif numbers.count == 1 then numbers = numbers elsif numbers.count == 2 then if numbers[0] > numbers[1] then tmp = numbers[0] numbers[0] = numbers[1] numbers[1] = tmp end else midNum = midPoint(numbers) arr1 = numbers.slice(0,midNum+1) arr2 = numbers.slice(midNum+1,numbers.count) arr1 = mergeSort(arr1) arr2 = mergeSort(arr2) numbers = setMerge(arr1 , arr2) end return numbers end numbers = [10,2,12,7,16,8,13] print mergeSort(numbers) ,"\n" |
実行
|
1 2 |
$ ruby mergeSort.rb [2, 7, 8, 10, 12, 13, 16] |
解説
rubyの小数点切り捨て、四捨五入
|
1 |
return ((nums.count / 2) + 0.5).floor |
切り捨ては@.floorで行える。
四捨五入は、0.5を足した後、@.floorすればいい
配列の要素数(length)
|
1 |
arr.count |
ruby言語は、javascriptのprototypeのような扱いで行えるのが非常に分かりやすい。
配列の追加(push)
|
1 |
arr.pusn(変数 or 配列) |
配列の先頭を抜き出す（破壊的処理:shift）
|
1 |
hoge = arr.shift |
hogeに先頭の値が入り、arrは先頭を抜かした残りの配列になる（要素数が一つ減る）
配列の特定部分の抜き出し（slice）
|
1 |
arr.slice(start-num , count-num) |
startは配列の要素番号（0スタート）で、countは○文字分になる。
今回のプログラム内では、中間値が要素数で取得しているので、+1をすることで、対応している。
関連リンク
マージソート記事
解説
JavaScript
PHP
Python
Shell
AWK
C言語
Go言語
Ruby