# This program demonstrates how to find the Kth smallest number
# in an unsorted array using the Quickselect algorithm.
#
# Quickselect avoids fully sorting the array, improving efficiency
# for large datasets. Average time complexity: O(n).
# ---------------------------------------------------------------
# Swap two elements in the array
# ---------------------------------------------------------------
def swap(arr, i, j)
arr[i], arr[j] = arr[j], arr[i]
end
# ---------------------------------------------------------------
# Partition the array around a pivot:
# - Values smaller than the pivot move left
# - Values larger move right
# Returns the pivot's final index.
# ---------------------------------------------------------------
def partition(arr, left, right)
pivot_value = arr[right]
store_index = left
(left...right).each do |i|
if arr[i] < pivot_value
swap(arr, i, store_index)
store_index += 1
end
end
swap(arr, store_index, right)
store_index
end
# ---------------------------------------------------------------
# Quickselect:
# Repeatedly partitions until the pivot lands on the desired index.
# ---------------------------------------------------------------
def quickselect(arr, left, right, target_index)
loop do
pivot_index = partition(arr, left, right)
if pivot_index == target_index
return arr[pivot_index]
elsif target_index < pivot_index
right = pivot_index - 1
else
left = pivot_index + 1
end
end
end
# ---------------------------------------------------------------
# Finds the Kth smallest number.
# Works on a copy of the array to avoid modifying the original.
# ---------------------------------------------------------------
def find_kth_smallest(values, k)
data = values.dup
target_index = k - 1 # Convert to zero-based index
quickselect(data, 0, data.length - 1, target_index)
end
# ---------------------------------------------------------------
# Main
# ---------------------------------------------------------------
numbers = [42, 90, 50, 30, 37, 21, 83, 45]
k = 3
result = find_kth_smallest(numbers, k)
puts "The #{k}rd smallest number is: #{result}"
=begin
run:
The 3rd smallest number is: 37
=end
