quickselect.rb

# :)

require 'benchmark'
include Benchmark

def find_median_by_sorting(v)
  sorted = v.sort
  quot = sorted.size / 2
  if !sorted.size.even?
    sorted[quot]
  else
    f = sorted[quot]
    b = sorted[quot - 1]
    (f+b) / 2
  end
end

def quickselect(v, k, piv: p)
  array = v.dup
  loop do
    pivot = p || array.delete_at(rand(array.size))
    left, right = array.partition{|x| x < pivot }
    if k == left.length
      return pivot
    elsif k < left.length
      array = left
    else
      k = k - left.length - 1
      array = right
    end
  end
end

def median_of_medians(v)
  array = v.dup
  while array.size > 5
    medians = array.each_slice(5).map do |group|
      quickselect(group, group.size / 2)
    end
    array = medians.flatten
  end
  quickselect(array, array.size / 2)
end

array = 100000000.times.map{|n| rand * 10 }
puts "mean: #{array.reduce(:+) / array.size}"

Benchmark.benchmark(CAPTION, 7, FORMAT, ">total:", ">avg:") do |x|
  x.report("find median by sorting: "){ puts find_median_by_sorting(array) }
  x.report("find median by quickselect: "){ puts quickselect(array, array.size / 2) }
  x.report("find median by quickselect with median of medians: "){ puts quickselect(array, array.size/2, piv: median_of_medians(array))}
end