3_buble.rb

#!/usr/bin/ruby
require 'openssl'
class Array
  def quick_sort
    if ($n==500 && $log<700) || ($n==2000 && $log<3000) || ($n==4000 && $log<6000) || ($n==6000 && $log<8500) || ($n==8000 && $log<11000) || ($n==10000 && $log<14000)
      $log+=1
      return self if length <= 1
      base = pop 
      smaller, bigger = partition { |e| e < base }
      push base
      smaller.quick_sort + [base] + bigger.quick_sort
    else
      raise "big"
    end 
  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)
    #fill_reverse(n)
    start_time=Time.now
    sort(n)
    #$a=$a.quick_sort
=begin
    if $cookies==false
      begin
        $a=$a.quick_sort
      rescue
        $a=$a.merge_sort
        $cookies=true
      end
    else
      $a=$a.merge_sort
    end










=end
=begin
    if $cookies==false
      begin
        $a=$a.quick_sort
      rescue SystemStackError
        $a=$a.merge_sort
        $cookies=true
      end
    else
      $a=$a.merge_sort
    end
=end
    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