quicksort.rb

def sort(xs, st, en)
  pivot = xs[st]
  s, e = st + 1, en

  loop do
    while (s <= en && xs[s] < pivot)
      s += 1
    end

    while (e > st && pivot < xs[e])
      e -= 1
    end

    if (s >= e)
      xs[st], xs[e] = xs[e], xs[st]
      break
    end

    xs[s], xs[e] = xs[e], xs[s]
  end

  sort(xs, st, e - 1) if (e - st > 1)
  sort(xs, e + 1, en) if (en - e > 1)
end

if $0 == __FILE__
  require 'test/unit'

  class Tezt < Test::Unit::TestCase
    def test
      500.times do
        xs = 200.times.to_a.shuffle
        expected = xs.sort
        sort(xs, 0, xs.size - 1)
        assert_equal(expected, xs)
      end
    end
  end
end