#!/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 bubblesort(a)
  loop do
    swapped = false
    (a.size - 1).times do |i|
      j = i + 1
      if a[i] > a[j]
	a.swap(i, j)
	swapped = true
      end
    end
    break if !swapped
  end
end
#END-ALGORITHM

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