This is a classic quick select problem.

Note:

There is a notable improvements to randomised inputs. I forgot to shuffle the `nums`

in my first attempt, ending up *2000+ms*. Then I added the shuffle method, getting *98ms*.

A little wrap-up for myself:

- In this case, without shuffling, it's O(N) average, but O(N^2) in worst case. With shuffling, it guarantees O(N) in worst case.
- Always remember to
**shuffle**when using the 'quick' family algorithms

```
def find_kth_largest(nums, k)
shuffle!(nums)
k -= 1
# kth largest is the (length-1-k)th smallest
k = nums.count - 1 - k
lo, hi = 0, nums.count-1
loop do
break if lo >= hi
j = partition(nums, lo, hi)
if j == k
return nums[k]
elsif j < k
lo = j + 1
else
hi = j - 1
end
end
nums[k]
end
def shuffle!(nums)
(1..nums.count-1).each do |i|
j = rand(i+1)
swap(nums, i, j)
end
end
def partition(array, lo, hi)
v = lo
i, j = lo, hi+1
loop do
loop do
i += 1
break if i == hi or array[i] >= array[v]
end
loop do
j -= 1
break if j == lo or array[j] <= array[v]
end
break if i >= j
swap(array, i, j)
end
swap(array, j, v)
return j
end
def swap(array, i, j)
t = array[i]; array[i] = array[j]; array[j] = t
end
```