Dual Pivot QSort in Ruby Benchmarked

Benchmarking (cont'd from other file)

1.upto(7) do |order_of_magnitude|
  quantity_of_items_to_sort = 10 ** order_of_magnitude

  items_to_sort = Array.new(quantity_of_items_to_sort) {|index| rand(quantity_of_items_to_sort)}

  sorted_with_qsort = nil

  time_with_built_in_qsort = Benchmark.realtime do
    sorted_with_qsort = items_to_sort.sort
  end

  sorted_with_dpqsort = nil

  time_with_dpqsort = Benchmark.realtime do
    sorted_with_dpqsort = items_to_sort.dpqsort
  end

  sorted_with_yo_mamas_qsort = nil

  time_with_yo_mamas_qsort = Benchmark.realtime do
    sorted_with_yo_mamas_qsort = items_to_sort.yo_mamas_qsort
  end

  puts " - Sorting #{quantity_of_items_to_sort} items"
  puts "   - Builtin = #{time_with_built_in_qsort}"
  puts "   - DPQsort = #{time_with_dpqsort}"
  puts "   - Yo Mama's QSort = #{time_with_yo_mamas_qsort}"
  puts ""
end

Dual Pivot QSort in Ruby Benchmarked

#!/usr/bin/env ruby                                                                                                                                                                                                                    
                                                                                                                                                                                                                                       
require 'benchmark'                                                                                                                                                                                                                    
                                                                                                                                                                                                                                       
class Array                                                                                                                                                                                                                            
  def dpqsort                                                                                                                                                                                                                          
    less_than_small = []                                                                                                                                                                                                               
    greater_than_big = []                                                                                                                                                                                                              
    those_in_between = []                                                                                                                                                                                                              
                                                                                                                                                                                                                                       
    small = shift                                                                                                                                                                                                                      
    big = shift                                                                                                                                                                                                                        
                                                                                                                                                                                                                                       
    if small > big                                                                                                                                                                                                                     
      temp = big                                                                                                                                                                                                                       
      big = small                                                                                                                                                                                                                      
      small = temp                                                                                                                                                                                                                     
    end                                                                                                                                                                                                                                
                                                                                                                                                                                                                                       
    each do |item|                                                                                                                                                                                                                     
      if item < small                                                                                                                                                                                                                  
        less_than_small << item                                                                                                                                                                                                        
      elsif item > big                                                                                                                                                                                                                 
        greater_than_big << item                                                                                                                                                                                                       
      else                                                                                                                                                                                                                             
        those_in_between << item                                                                                                                                                                                                       
      end                                                                                                                                                                                                                              
    end                                                                                                                                                                                                                                
                                                                                                                                                                                                                                       
    sorted_less_than_small = less_than_small.length > 1 ? less_than_small.dpqsort : less_than_small                                                                                                                                    
    sorted_greater_than_big = greater_than_big.length > 1 ? greater_than_big.dpqsort : greater_than_big                                                                                                                                
    sorted_those_in_between = those_in_between.length > 1 ? those_in_between.dpqsort : those_in_between                                                                                                                                
                                                                                                                                                                                                                                       
    sorted_less_than_small + [small] + sorted_those_in_between + [big] + sorted_greater_than_big                                                                                                                                       
  end                                                                                                                                                                                                                                  
                                                                                                                                                                                                                                       
  def yo_mamas_qsort                                                                                                                                                                                                                   
    less_than = []                                                                                                                                                                                                                     
    greater_than = []                                                                                                                                                                                                                  
    pivot = shift                                                                                                                                                                                                                      
                                                                                                                                                                                                                                       
    each do |item|                                                                                                                                                                                                                     
      if item < pivot                                                                                                                                                                                                                  
        less_than << item                                                                                                                                                                                                              
      else                                                                                                                                                                                                                             
        greater_than << item                                                                                                                                                                                                           
      end                                                                                                                                                                                                                              
    end                                                                                                                                                                                                                                
                                                                                                                                                                                                                                       
    sorted_less_than = less_than.length > 1 ? less_than.yo_mamas_qsort : less_than                                                                                                                                                     
    sorted_greater_than = greater_than.length > 1 ? greater_than.yo_mamas_qsort : greater_than                                                                                                                                         
                                                                                                                                                                                                                                       
    sorted_less_than + [pivot] + sorted_greater_than                                                                                                                                                                                   
  end                                                                                                                                                                                                                                  
end