find the kth smallest element in an array in ruby

To find the kth smallest element in an array, we can sort the array and then return the element at index k-1. One way to sort the array is to use the built-in sort method.


main.rb
def kth_smallest_element(array, k)
  sorted_array = array.sort
  return sorted_array[k-1]
end
94 chars
5 lines

Another way to sort the array is to use a more efficient algorithm, such as quicksort or heapsort. One implementation of quicksort could look like this:


main.rb
def quicksort(array)
  return array if array.length <= 1

  pivot = array.sample
  less = []
  equal = []
  greater = []

  array.each do |x|
    if x < pivot
      less << x
    elsif x == pivot
      equal << x
    else
      greater << x
    end
  end

  return quicksort(less) + equal + quicksort(greater)
end

def kth_smallest_element(array, k)
  sorted_array = quicksort(array)
  return sorted_array[k-1]
end
415 chars
26 lines

Note that this implementation of quicksort picks a random pivot element to help avoid worst-case performance when the input array is already sorted or nearly sorted.

similar ruby code snippets

find the kth least frequent element in an array in ruby

find the kth most frequent element in an array in ruby

find the kth smallest number in a list in ruby

find the kth largest number in a list in ruby

sort an array in ruby

find the kth smallest element in an array in ruby

find the kth largest element in an array in ruby

find the index of an element in an array in ruby

remove an element from the beginning of an array in ruby

insert an element into an array at a specific index in ruby

related categories