3_quick.rb

#!/usr/bin/ruby
require 'openssl'
class Array
  def quick_sort
    return self if length <= 1
    base = pop
    smaller, bigger = partition { |e| e < base }
    push base
    smaller.quick_sort + [base] + bigger.quick_sort
  end
  def merge_sort
    tmp = self.dup
    return tmp if tmp.length <= 1
    a, b = self.half.map { |e| e.merge_sort }
    merge(a, b)
  end
  def half
    mid = length/2
    return slice(0...mid), slice(mid..-1)
  end

  def merge(a, b)
    res = []
    until a.empty? && b.empty?
      res <<
      case
      when a.empty? then b.shift
      when b.empty? then a.shift
      when a.first < b.first then a.shift
      else b.shift
      end
    end
    res
  end
end
class N2Sort
  def initialize(n)
    $a=Array.new(n)
  end
  def fill_reverse(n)
    initialize(n)
    n.times do |i|
      $a[i]=n-1
    end
  end
  def fill_random(n)
    initialize(n)
    n.times do |i|
      $a[i]=rand(1000000000)
    end
  end
  def sort(n)
    (0..n-1).each { |i|
      z=$a[0]
      (0..n-2-i).each { |j|
        x,y = z,$a[j+1]
        if x>y then
          $a[j],z = y,x
        else
          $a[j],z = x,y
        end
      }
      $a[n-1-i]=z
    }
  end

  def verify(n)
    (0..n-2).each { |i|
      if($a[i]>$a[i+1]) then
        return false
      end
    }
    return true
  end
  def measure(n)
    $log=0
    fill_random(n)
    start_time=Time.now
    $a=$a.quick_sort
    end_time=Time.now
    elapsed_time=(end_time-start_time).to_f()

    return verify(n)?elapsed_time:Float::NAN
  end
end

def run
  nn=[500,2000,4000,6000,8000,10000]
  s=N2Sort.new(nn[-1])
  $cookies=false
  nn.each { |n|
    $nloops=(nn[-1]/n).to_i()
    $n=n
    print n.to_s()+""
    5.times {
      print "\t"
      print s.measure(n)
    }
    print "\n"
  }
end

run