#!/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

#BEGIN-ALGORITHM
def quicksort(a)
  return a if a.size <= 1
  pivot = a[0]
  quicksort(a.select {|value| value < pivot}) + 
    a.select {|value| value == pivot} +
    quicksort(a.select {|value| value > pivot})
end
#END-ALGORITHM

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