quicksort.rb

# for reference: http://www.youtube.com/watch?v=3OLTJlwyIqQ
require 'pp'

def quicksort(arr, from=0, to=nil)
  to = arr.length-1 if to.nil?

  # exit condition for recursion
  return if to - from < 1

  pivot_location = move_pivot_to_sorted_location(arr, from, to)

  # once every value less than the pivot has been shifted left of it and
  # every value greater that in has been shifted right of it, the pivot is
  # in its final position. Call quicksort on the subarrays left and right
  # of the pivot, unless they're the right- or left-most element of the
  # (sub)array in question.
  quicksort(arr, from, pivot_location-1) unless pivot_location == from
  quicksort(arr, pivot_location+1, to) unless pivot_location == to
end

def move_pivot_to_sorted_location(arr, left, right)
  pivot = left

  until left == right
    if pivot == left
      pivot, left, right = compare_pivot_to_right(arr, pivot, right)
    elsif pivot == right
      pivot, left, right = compare_pivot_to_left(arr, pivot, left)
    end
  end

  pivot
end

def compare_pivot_to_right(arr, pivot, right)
  if arr[pivot] > arr[right]
    # swap values at pivot and right
    temp = arr[right]
    arr[right] = arr[pivot]
    arr[pivot] = temp

    # and return updated locations of left, right, and pivot for next iteration
    return [right, pivot + 1, right]
  end

  # if no swap is needed, move right in one for next iteration
  [pivot, pivot, right - 1]
end

def compare_pivot_to_left(arr, pivot, left)
  # logically identical to the above, except direction changed to reflect a
  # post-swap world. At least the part of the world being quicksorted.
  if arr[pivot] < arr[left]
    temp = arr[left]
    arr[left] = arr[pivot]
    arr[pivot] = temp

    return [left, left, pivot - 1]
  end

  [pivot, left + 1, pivot]
end

test = []
15.times do
  test << rand(40)
end

pp "UNSORTED ARRAY: #{test}"
quicksort test
pp "SORTED ARRAY: #{test}"