quicksort.rb

module Quicksort
  module_function

  # Sorts in place the subarray of `array` from index `first`
  # to index `last`, inclusive.
  #
  # @param array [Array] the array to be (partially) sorted
  # @param first [Integer] the left index of the subarray to be sorted
  # @param last [Integer] the right index of the subarray to be sorted
  # @return [Array] the sorted array
  def quicksort!(array, first, last)
    return unless last > first
    pivot = partition!(array, first, last)
    quicksort!(array, first, pivot - 1)
    quicksort!(array, pivot + 1, last)
    array
  end


  # Reorders the subarray of `array` from index `first` to `last`,
  # inclusive, such that for some index `pivot`, where
  # `first` <= `pivot` <= `last`, the value at index `pivot` is
  # >= all the subarray values to its left and <= all the subarray
  # values to its right.
  #
  # The last value of the subarray—the one at index `last`—is
  # arbitrarily chosen as the pivot value.
  #
  # @param array [Array] the array to be (partially) partitioned
  # @param first [Integer] the left index of the subarray to be partitioned
  # @param last [Integer] the right index of the subarray to be partitioned
  # @return [Integer] the index of the pivot value
  def partition!(array, first, last)
    pivot = first

    (first...last).each do |idx|
      if array[idx] <= array[last]
        swap(array, idx, pivot)
        pivot += 1
      end
    end

    swap(array, last, pivot)
    pivot
  end

  # Swap the value in `array` at index `i` with the value at `j`.
  #
  # @param array [Array] the target array
  # @param i [Integer] the index of the first value to swap
  # @param j [Integer] the index of the second value to swap
  # @return [Array] the array with its values swapped
  def swap(array, i, j)
    array[i], array[j] = array[j], array[i]
    array
  end
end