Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Implementation of the linear time median of medians algorithm.
# Gist to go with http://www.austinrochford.com/posts/2013-10-28-median-of-medians.html
# Chad Brewbaker 10/28/2013
# https://news.ycombinator.com/item?id=6628474
def median_5(list, i = list.length/2)
return list.sort[i]
end
def median(list, i = list.length/2)
if (list.length <= 5)
return median_5(list, i)
end
median_list = []
list.each_slice(5) { |s|
median_list.push(median_5(s))
}
more =[]
less = []
pivot = median(median_list)
less = list.find_all { |x| x < pivot }
if (i < less.length)
return median(less, i)
end
if (i == less.length)
return pivot
end
more = list.find_all { |x| x > pivot }
return median(more, i-(less.length+1))
end
test = (1..1000).select { |x| true }
puts test.length.to_s + " elements in the test array"
0.upto(5) do |iteration|
test = test.shuffle!
0.upto(test.length-1) do |i|
if median(test, i) != test.dup.sort[i]
puts median(test, i).to_s + " != " + test.dup.sort[i].to_s
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.