Sorting out Ruby

These days, writing your own sort is something that happens to most programmers only in their Data Structures and Algorithms classes (and again on job interviews). The rest of the time you get to use whatever sort method your standard library/API/framework provides and for most purposes it proves adequate, especially with the sort of computational horsepower available even on handheld devices these days.

Having said that, I wound up writing a toy class in Ruby that implements five different sorts (bubble, quick, insertion, shell and merge). Just on the offchance that this is useful to someone some day (when doing their DS&A coursework, for example), here is the listing:

#require 'profile'

class Sorter
  attr_accessor :array

  def initialize(array)
    @array = Array.new(array)
  end

  def bubblesort()
    n = @array.length
    begin
      newn = 0
      for i in 0..(n-2) do
        if @array[i] > @array[i+1]
          @array[i], @array[i+1] = @array[i+1], @array[i]
          newn = i +1
        end
      end
      n = newn
    end while n > 1
  end

  def quicksort()
    def partition(array, left, right, pivot_index)
      pivot_value = array[pivot_index]
      array[pivot_index], array[right] = array[right], array[pivot_index]
      store_index = left
      for i in left..right-1 do
        if array[i] <= pivot_value
          array[i], array[store_index] = array[store_index],array[i]
          store_index += 1
        end
      end
      array[store_index], array[right] = array[right], array[store_index]
      return store_index
    end
    def qsort(array, left, right)
      if right > left
        pivot_index = left + ( right - left ) / 2
        pivot_new_index = partition(array, left, right, pivot_index)
        qsort(array, left, pivot_new_index - 1)
        qsort(array, pivot_new_index + 1, right)
      end
    end
    qsort(@array, 0, @array.length - 1)
  end

  def shellsort()
    increment = Float(@array.length/2).round
    while increment > 0 do
      for i in increment..@array.length-1 do
        j = i
        temp = @array[i]
        while j >= increment and @array[j-increment] > temp do
          @array[j] = @array[j-increment]
          j -= increment
        end
        @array[j] = temp
      end
      increment = Float(increment/2.2).round
    end
  end

  def insertionsort()
    for i in 1..@array.length-1 do
      value = @array[i]
      j = i - 1
      done = false
      begin
        if @array[j] > value
          @array[j + 1] = @array[j]
          j -= 1
          if j < 0
            done = true
          end
        else
          done = true
        end
      end until done
      @array[j + 1] = value
    end
  end

  def mergesort()
  def msort(lo,hi)
    if lo < hi
    mid = (lo+hi)/2
    msort(lo,mid)
    msort(mid+1,hi)
    merge(lo,mid,hi)
    end
  end
  def merge(lo,mid,hi)
    i,j = 0,lo
    aux = Array.new
    while j <= mid
    aux[i] = @array[j]
    i += 1
    j += 1
    end
    i=0
    k=lo
    while k < j and j <= hi
    if aux[i] <= @array[j]
      @array[k] = aux[i]
      k += 1
      i += 1
    else
      @array[k] = @array[j]
      k += 1
      j += 1
    end
    end
    while k < j
    @array[k] = aux[i]
    k += 1
    i += 1
    end
  end
  msort(0,@array.length-1)
  end
end

sort_this = [ 0,7,9,7,4,1,4,5,4,2,8 ]
sorts = ["bubblesort","quicksort","shellsort","insertionsort","mergesort"]
sorterobject = Sorter.new(sort_this)

for sorttype in sorts do
  sortermethod = sorterobject.method(sorttype)
  sortermethod.call()
  puts sorttype
  print sort_this, " => ", sorterobject.array, "\n"
  sorterobject.array = Array.new(sort_this)
end