Benchmarking a quicksort algorithm designed to handle duplicates.

quicksort_benchmark.rb

require 'benchmark'

class RubyQuicksort

  def self.prepare(number_of_items)
    time_taken = Benchmark.realtime{ generate_random_array number_of_items }
    puts "Took #{time_taken}s to generate an array of #{number_of_items} random items"
  end

  def self.generate_random_array(number_of_items)
    @array = []
    for i in 0..number_of_items-1 do
      @array << 1 + rand(100000)
    end
    @array
  end

  def self.array
    @array
  end

  def self.quicksort(lo=nil, hi=nil)
    unless lo && hi
      lo = 0
      hi = @array.count - 1
    end
    return if hi <= lo
    pivot_index = partition_index(lo, hi)
    quicksort(lo, pivot_index - 1)
    quicksort(pivot_index + 1, hi)
  end

  def self.partition_index(lo, hi)
    left = lo + 1
    right = hi
    while true
      while @array[left] <= @array[lo] && left > lo
        left += 1
        break if left >= hi
      end
      while @array[right] >= @array[lo] && right > lo
        right -= 1
      end
      break if left >= right || @array[left] == @array[right]
      swap(left, right)
    end
    swap(right, lo)
    right
  end

  def self.swap(x, y)
    @array[x], @array[y] = @array[y],@array[x]
  end

end

n = 100000
RubyQuicksort.prepare(n)
time_taken = Benchmark.realtime { RubyQuicksort.quicksort }
puts "Took #{time_taken}s to quicksort #{n} items"