##
# A quick sort implementation I made for fun in Ruby.
def quick_sort(values)
  return values if values.size < 2
  pivot_index = values.size - 1
  pivot_value = values[pivot_index]
  curr_index = 0
  (values.size - 1).times do
    curr_value = values[curr_index]
    # less than or equal, leave the item where it is
    if curr_value <= pivot_value
      curr_index += 1
    elsif curr_value > pivot_value
      # bump everything over one, including pivot
      (pivot_index - curr_index).times do |i|
        values[curr_index + i] = values[curr_index + i + 1]
      end
      values[pivot_index] = curr_value
      pivot_index -= 1
    end
  end

  smaller = pivot_index == 0 ? [] : values[0..pivot_index - 1]
  larger = values[pivot_index + 1..values.size]

  [*quick_sort(smaller), pivot_value, *quick_sort(larger)]
end

# quick dirty tests
[
  [5,2,7,1,3,-5,13,4],
  [1,2,3,2,1],
].map do |test|
  puts "Sorting #{test}"
  puts "Sorted #{quick_sort(test)}"
  quick_sort(test)
end
# first move:  2, 1, 4, 5