練習：クイックソート (続き)

頭の中の材料だけでやろうとしたんだけど...だめだ、理屈はわかっているんだけど、答えが合わない!
というわけで、アルゴリズム事典に頼ってしまいました。ちょっと情けないですが、そこから自分流キレイ風にアレンジするのに頑張りました。
同時に、まだ使い慣れないモジュールの練習も兼ねて。インスタンスにモジュール「装着」してる感覚です。多重代入の良い例と悪い例、配列の初期化なども練習のうち。

module Sort
  module QuickSort
    def sort () self.clone.sort! end
    def sort! () execute(self, 0, self.size - 1) end
    def execute (a, f, t)
      x = a[(f + t) / 2]
      i, j = f, t # 多重代入にする必要がない
      while true
        i += 1 while a[i] < x
        j -= 1 while a[j] > x
        break unless i < j
        a[i], a[j] = a[j], a[i] # 交換には適している
        i += 1
        j -= 1
      end
      execute(a, f, i - 1) if (f < i - 1)
      execute(a, j + 1, t) if (j + 1 < t)
      return a
    end
    private :execute
  end
end

o = Array.new(16) do |i| rand(1000) end
a = o.clone
b = o.clone.extend Sort::QuickSort
p a.sort!
p b.sort!
puts a == b

ランダムだから毎回結果は異なりますが、最後がtrueならOKってことで。

[352, 771, 576, 933, 388, 746, 898, 894, 372, 763, 8, 364, 584, 498, 579, 743]
[8, 352, 364, 372, 388, 498, 576, 579, 584, 743, 746, 763, 771, 894, 898, 933]
[8, 352, 364, 372, 388, 498, 576, 579, 584, 743, 746, 763, 771, 894, 898, 933]
true