#!/usr/bin/env ruby
# shellsorter.rb: a simple (toy) implementation of shellsort, version 0.1
# Copyright 2008 Sudarshan S. Chawathe.
# License: GNU GPL version 3; see http://www.gnu.org/copyleft/gpl.html
# For a description of the shellsort algorithm , refer to a data-structures 
# textbook, such as "Data Structures & Problem Solving using Java" by 
# Mark Allen Weiss, Addison Wesley, 2002.

class ShellSorter

  def self.sort(a = [3, 1, 2])
    numComp = 0
    len = a.length
    k = len/2
    while(k > 0.0)
      # Increment = k. We sort all k-sequences (sequences of elements
      # k-apart) using insertion sort over all k-sequences concurrently.
      for i in k..len-1 do
        t = a[i]
        j = i
        while( (j >= k) && (a[j-k] > t) ) do
          numComp += 1
          a[j] = a[j-k]
          j -= k
        end
        ++numComp
        a[j] = t;
      end
      k = (k/(k == 2 ? 2 : 2.2)).floor # "divide by 2.2" increment sequence
    end
    return numComp
  end

  def self.randomArray(len = 10)
    a = []
    if(len<0) then len = 0 end
    for i in 0..len-1 do
      a[i] = (rand*len).floor
    end
    return a;
  end

  def self.test(len = 10, show = false)
    a = randomArray(len)
    if(show) then puts "  In: " + a.join(" ") end
    c = sort(a)
    if(show) 
      puts " Out: " + a.join(" ") 
      puts "comp: #{c}"
    end
  end

end

if __FILE__ == $0
  ShellSorter.test(20, true)
end