Median of Medians Algorithm

median.rb

# Common median algorithm, which averages the two middle
# values when needed.
def median(list)
  sorted = list.sort
  half = (list.size - 1) / 2
  if list.size.even?
    (sorted[half] + sorted[half+1]) / 2.0
  else
    sorted[half]
  end
end

raise 'fail' unless median([0,1,2])     == 1
raise 'fail' unless median([0,1,2,3])   == 1.5
raise 'fail' unless median([0,1,1,2,3]) == 1

# Return the given list separated into three lists with values
# either <, =, or > the given pivot value.
def partition(list, pivot)
  list.reduce([[],[],[]]) do |(lesser, equal, greater), element|
    if element < pivot
      [lesser << element, equal, greater]
    elsif element == pivot
      [lesser, equal << element, greater]
    else
      [lesser, equal, greater << element]
    end
  end
end

raise 'fail' unless partition([0,1,2,3], 2)  == [[0,1],[2],[3]]
raise 'fail' unless partition([0], 1)        == [[0],[],[]]
raise 'fail' unless partition([0,4], 4)      == [[0],[4],[]]
raise 'fail' unless partition([0,3,8,13], 4) == [[0,3],[],[8, 13]]

# Find a good pivot value for quickselect.
# NOTE: could be just `list[rand(list.size)]` for the
# functionality of our quickselect.
def pivot(list)
  if list.size < 5
    median(list)
  else
    chunks = list.each_slice(5).to_a
    medians = chunks.map { |c| c.sort[2] }.compact
    quickselect_median(medians)
  end
end

# Return the kth ordered element from the list. This is
# (approximately when the list length is odd) the median,
# when k = list.size / 2.
def quickselect(list, k)
  case list.size
  when 1
    list[k]
  else
    # Find a pivot, and partition the list with it.
    lesser, equal, greater = *partition(list, pivot(list))

    # If we're looking for an element position (k) less than the size of the
    # lesser list, the value must be in that list.
    if k < lesser.size
      quickselect(lesser, k)

    # We managed to partition on the median value.
    elsif k < lesser.size + equal.size
      equal[0]

    # Otherwise, we're looking for an element which must be in the greater
    # list, so we recur on that list, looking for an element position offset
    # by the length of the lesser and equal lists we now ignore.
    else
      quickselect(greater, k - lesser.size - equal.size)
    end
  end
end

# Faster? median algorithm, which is functionally the same as `median`.
def quickselect_median(list)
  if list.size.even?
    (quickselect(list, list.size / 2 - 1) +
     quickselect(list, list.size / 2)) / 2.0
  else
    quickselect(list, list.size / 2)
  end
end

##### Run on Random Data

list = Array.new(100) { rand(0...100) }
result = quickselect_median(list)
puts result

# Sanity check.
raise 'fail' unless result == Array.send(:median, list)