find the kth largest number in a list in ruby

One way to find the kth largest number in a list in Ruby is to sort the list in descending order and return the element at index k-1. However, sorting the entire list can be time-consuming and unnecessary.

A more efficient way to solve this problem is to use the Quickselect algorithm, which is similar to Quicksort but only partitions the array on one side of a pivot element. This allows us to find the kth largest number in linear time complexity, on average.

Here is an implementation of the Quickselect algorithm in Ruby:

main.rb
def quickselect(arr, k)
  return nil if k > arr.length || k < 1

  pivot = arr.sample
  left = arr.select { |x| x > pivot }
  mid  = arr.select { |x| x == pivot }
  right = arr.select { |x| x < pivot }

  if k <= left.length
    quickselect(left, k)
  elsif k <= left.length + mid.length
    pivot
  else
    quickselect(right, k - left.length - mid.length)
  end
end
368 chars
17 lines

This method takes an array arr and an integer k as input, and returns the kth largest number in arr. It first selects a pivot element at random from arr, and partitions the array into three subarrays containing elements greater than, equal to, and less than the pivot. It then recursively calls the quickselect method on the left or right subarray depending on the value of k.

To find the kth largest number in a list, we can call this method as follows:

main.rb
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
k = 4
kth_largest = quickselect(arr, arr.length-k+1)
puts "The #{k}th largest number in #{arr} is #{kth_largest}"
154 chars
5 lines

This will output:

main.rb
The 4th largest number in [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] is 5
65 chars
2 lines