#!/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 combsort(a)
  b = a
  gap = b.size
  loop do
    gap = gap * 10 / 13
    gap = 11 if gap == 9 || gap == 10
    gap = 1 if gap < 1
    swapped = false
    (b.size - gap).times do |i|
      j = i + gap
      if b[i] > b[j]
	b.swap(i, j)
	swapped = true
      end
    end
    break if gap == 1 && !swapped
  end
  b
end
#END-ALGORITHM

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