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

Ruby Tuesday

Well, Ruby Friday to be precise.

I've been looking at Ruby and Ruby-on-Rails for some cool web development action and have hit on a number of things that bug me. No doubt I'll find find good reasons for them, but at the moment...

 The one thing that really bugs me right now (quite unreasonably so, as it isn't broken, just an odd design decision) is the handling of constants. You define a constant by the mechanism of starting a variable name with a capital letter, so var_name is not a constant whilst Var_name or VAR_NAME is (I prefer all upper-case to make it absolutely screamingly obvious). This isn't a coding convention that the interpreter pays no heed to, it's an actual language convention, but the really annoying part is that a constant isn't constant.

If in Ruby, you try to assign to an already-defined constant, the interpreter will quite happily let you, but at the same time will warn you that you're doing a bad thing. This half-way house to me makes little sense; either a constant should be constant by language enforcement or completely by convention, especially as it is presumably possible to make optimizations in the interpreter if constants are genuinely constant that isn't the case if they might change.

It is said that Ruby follows the principle of least confusion; in this case, I'm not sure this is the case.