#!/usr/bin/ruby -w

class Array
  def qsort
    return self if length <= 1
    x, *xs = self
    xs.select { |y| y <= x }.qsort + [x] + xs.select{ |y| y > x }.qsort
  end
  
  def mergesort
    return self if length <= 1
    a = self[0..(length - 1) / 2].mergesort
    b = self[(length + 1) / 2,length].mergesort
    res = []
    while a.length > 0 && b.length > 0
      res << (a[0] < b[0] ? a : b).slice!(0)
    end
    res + (a.length > 0 ? a : b)
  end
  
  def insertionsort
    a = self.dup
    0.upto(a.length - 1) do |i|
      i.upto(a.length - 1) do |j|
        a[i], a[j] = a[j], a[i] if a[j] < a[i]
      end
    end
    a
  end
  
  def bubblesort
    a = self.dup
    0.upto(a.length) do |j|
      done = 1
      (a.length - 2).downto(j) do |i|
        a[i], a[i + 1], done = a[i + 1], a[i], nil if a[i + 1] < a[i]
      end
      return a if done
    end 
  end
end

# Functionality test
a = (1..20).map {rand(10)}
puts a.join
puts a.qsort.join
puts a.mergesort.join
puts a.insertionsort.join
puts a.bubblesort.join

# Timing test
def time
  t = Time.now
  yield
  return Time.now - t
end

a = (1..1000).map {rand(10)}
puts time {a.qsort}
puts time {a.mergesort}
puts time {a.insertionsort}
puts time {a.bubblesort}