Apply quickselect to nd the median of the list of numbers 9

Apply quickselect to nd the median of the list of numbers 9, 12, 5, 17, 20, 30, 8.

Solution

class Array
def median
return nil if self.empty?
length = self.size
if length.odd?
return quickselect(0, length-1, length/2)
else
lower = quickselect(0, length-1, length/2-1)
higher = quickselect(0, length-1, length/2)
return (lower + higher) / 2.0
end
end
private
def partition(left, right, pivot)
pivot_value = self[pivot]
swap(pivot, right)
store_index = left
(left...right).each do |i|
if self[i] < pivot_value
swap(i, store_index)
store_index += 1
end
end
swap(store_index, right)
return store_index
end
def swap(from, to)
tmp = self[to]
self[to] = self[from]
self[from] = tmp
end

# returns kth smallest element
def quickselect(left, right, k)
return self[left] if left == right

pivot = (right+1 + left) / 2
new_pivot_index = partition(left, right, pivot)
diff = (new_pivot_index - left)

if diff == k
return self[new_pivot_index]
elsif k < diff # kth element is in lower partition
return quickselect(left, new_pivot_index-1, k)
else # kth element is in higher partition
return quickselect(new_pivot_index+1, right, k-diff-1)
end
end
end

array = 10.times.map { rand(100) }
puts \"sorted array: #{array.sort.inspect}, median: #{array.median}\"