Rubyでクイックソート

最近、「van勉だぃありぃ〜読んでるよ」とか言われるから、なんか書くの恥ずかしくなった。

クイックソートをするメソッド書きました。

def qsort(data, left, right)
  return if left >= right # 位置から文字の長さを判別
  pivot = data[(left + right) / 2]
  l, r = partitioning(data, pivot, left, right)
  qsort(data, left, l - 1)
  qsort(data, r + 1, right)
end

クイックソートは

1. 枢軸出す
2. 枢軸以下のグループと枢軸以上のグループに分ける
3. 各グループをさらにクイックソートしていく

以上の流れで行います。
私は3番目の各グループをさらにクイックソートしていく部分で悩んだんですけど、2つのグループを再帰呼び出しすればいいんですね。勉強になりました。

ソートするメソッドは以下。

def partitioning(data, pivot, left, right)
  while true
    while data[left] < pivot
      left +=1
    end
    while data[right] > pivot
      right -= 1
    end
    break if left >= right
    wk = data[left]
    data[left] = data[right]
    data[right] = wk
    left += 1
    right -= 1
  end
  return left, right
end

pratitioningメソッドは、qsortメソッド内で書こうと思っていました。でも、ソート処理が難しかったのでメソッド化して取り出しました。全体のコードを書いてから、後で難しい部分を作る。この方法をトップダウンな開発方法と呼ぶらしいです。
逆に、難しそうな処理を先に作ってしまい、後から本体となるプログラミングする方法をボトムアップな開発方法とう呼ぶ。