#!/usr/bin/ruby

class Array
  
  def swap(i, j)
    self[i], self[j] = self[j], self[i]
  end

  def isSorted
    self.each {|i| return false if self[i] != i}
    true
  end

end

def listOfIntegers(size)
  (0...size).to_a
end

def scramble(a)
  a.each_index { |i| a.swap(i, rand(a.size))}
end

def scrambledListOfIntegers(size)
  scramble(listOfIntegers(size))
end

def setRandomNumberSeed
  srand(1)
end

def cpuTime
  times = Time.times
  times[0] + times[1]
end

def executionTime
  startTime = cpuTime
  yield
  endTime = cpuTime
  endTime - startTime
end

# Modified from algorithm at: 
# http://www.la.unm.edu/~mbrettin/algorithms/quiksort.html

#BEGIN-ALGORITHM
def partition(a, first, last)
  pivot = a[first]
  lastS1 = first
  firstUnknown = first + 1
  while firstUnknown <= last do
    if a[firstUnknown] < pivot
      lastS1 += 1
      a.swap(firstUnknown, lastS1)
    end
    firstUnknown += 1
  end
  a.swap(first, lastS1)
  lastS1
end

def quicksort(a, first = 0, last = a.size - 1)
  if first < last 
    pivotIndex = partition(a, first, last)
    quicksort(a, first, pivotIndex - 1)
    quicksort(a, pivotIndex + 1, last)
  end
end
#END-ALGORITHM

setRandomNumberSeed
a = scrambledListOfIntegers(10000)
puts executionTime {quicksort(a)}