Algorithm Implementation/Sorting/Introsort

Ruby

Ruby implementation with simple test

#!/usr/bin/env ruby
#
# Introsort is a version of Quicksort with "introspection".
#
# When Introsort notices that its recursion depth exceeds
# a specified height, it switches over to Heapsort to
# process the (Quicksort) partition it is currently working on.
# In this way the recursion depth does not continue to increase
# as it would with Quicksort. Unconstrained recursion can reduce
# Quicksort's performance to O(n^2), whereas on the same data,
# Introsort guarantees a worst-case performance of O(n*log2(n)).
#
# This version of Introsort switches to Heapsort when its 
# recursion depth reaches 2*(floor(log2(n))).
# See Musser, David (1997). "Introspective Sorting and Selection Algorithms".
# Software: Practice and Experience 27 (8): 983?993. Wiley.
#
# The algorithm for Heapsort is adapted from 
# Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001).
# Introduction to Algorithms, second edition, MIT Press and McGraw-Hill.
#
class Heapsort
  def initialize(ary)
    @ary = ary.dup
    @heap_size = ary.length
  end
  def heapsort
   build_max_heap
   @ary.length.downto(2) {|i|
     swap(1, i) 
     @heap_size -= 1   
     max_heapify(1)
   }
   @ary
  end 
  def build_max_heap
    parent(@heap_size).downto(1) {|i|
      max_heapify(i)
    }
  end
  def max_heapify(i)
    l = left(i)  
    r = right(i)
    largest = (l <= @heap_size and @ary[l-1] > @ary[i-1]) ? l : i
    largest = r if (r <= @heap_size and @ary[r-1] > @ary[largest-1])
    if largest != i
      swap(i, largest)
      max_heapify(largest)
    end
  end 
  def parent(i)
    (i / 2).floor
  end
  def left(i)
    2 * i
  end
  def right(i)
    (2 * i) + 1
  end 
  def swap(i, j)
    @ary[i-1], @ary[j-1] = @ary[j-1], @ary[i-1]
  end
end
def introloop(ary, depth_limit)
  return ary if ary.size <= 1
  return Heapsort.new(ary).heapsort() if depth_limit == 0
  depth_limit -= 1
  pivot = ary.pop
  left, right = ary.partition { |e| e < pivot }
  introloop(left, depth_limit) + [pivot] + introloop(right, depth_limit)
end
def introsort(ary)
  introloop(ary, 2 * (Math.log10(ary.size) / Math.log10(2)).floor)
end 
if $0 == __FILE__
  print introsort([1, 4, 7, 2, 1, 3, 2, 1, 4, 2, 3, 2, 1]).join(", ") + "\n"
  # prints: 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 7 without calling heapsort
  print introsort([13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]).join(", ") + "\n"
  # prints: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
  # and calls heapsort once for subarray [13, 12, 11, 10, 9, 8, 7]
end