Sorting algorithms in Ruby

If you wish to learn sort algorithms, this is the best website to visit. Bad news for English speakers is that this site is written in Japanese.

The author of the website uses Java for his sample code. I could write Java code but I am not a big fan of it since Java forces me to type too much (Who wants to type "HashMap<nteger, Boolean> map = new HashMap<Integer, Boolean>()" when you can do the same task by typing "map = {}" in Ruby?). So I rewrote his sample programs in Ruby.

There are three interesting algorithms: heap sort, merge sort and quick sort. They are the most efficient ones among all the sorting algorithms.

Let's start with heap sort.

class HeapSort
def initialize
@heap = []
end

def push(item)
@heap << item
    i = @heap.size
    j = i / 2
    while i > 1
      if @heap[i - 1] < @heap[j - 1]
        t = @heap[i - 1]
         @heap[i - 1] = @heap[j - 1]
         @heap[j - 1] = t
       end
       i /= 2 
       j = i / 2
    end
  end 

  def pop
   res = @heap.shift
   return res if @heap.size == 0
   last_item = @heap.pop
   # bring the last item to the root
     @heap.unshift(last_item)
     i = 1
     j = 2
     while j <= @heap.size
       if j < @heap.size && @heap[j - 1] > @heap[j]
       j += 1
    end
    if @heap[i - 1] > @heap[j - 1]
      t = @heap[i - 1]
      @heap[i - 1] = @heap[j - 1]
      @heap[j - 1] = t
    end
    i = j
    j *= 2
  end
  res
end

def run(list)
    list.each do |item|
    push(item)
end

res = []
while item = pop
res << item
    end

    res 
  end
end

Heap sort is a bit tricky in terms of how to maintain a balanced binary tree. It looks complicated especially when you remove the root element from the tree (look at pop() method above). The second algorithm is merge sort.

class MergeSort
  def initialize
  end

  def merge(a1, a2, a)
    i = 0
    j = 0
    while i < a1.size || j < a2.size
      if j >= a2.length || (i < a1.length && a1[i] < a2[j])
        a[i+j] = a1[i]
        i += 1
      else
        a[i+j] = a2[j]
        j += 1
      end 
    end
  end

  def merge_sort(a) 
    if a.size > 1
      m = a.size / 2
      n = a.size - m
      a1 = []
      a2 = []
      0.upto(m - 1) do |i|
        a1[i] = a[i]
      end
      0.upto(n - 1) do |i|
        a2[i] = a[m + i]
      end 
      merge_sort(a1);
      merge_sort(a2);
      merge(a1, a2, a);
    end 
  end 

  def run(list)
    a = list.dup
    merge_sort(a)
    a
  end
end

The idea of merge sort is rather simple. You can implement it with recursion elegantly. And the last one is the queen of sorting algorithms, quick sort.

class QuickSort
  def initialize
  end
  
  def pivot(a, i, j)
    k = i + 1
    while k <= j && a[i] == a[k] 
      k += 1
    end
 
    if k > j  
      return -1 
    end
  
    if a[i] >= a[k] 
      return i
    end
 
    return k
 end

  def partition(a, i, j, x)
    l=i
    r=j
    while l <= r
      while l<=j && a[l] < x  
        l += 1
      end
      while r>=i && a[r] >= x 
        r -= 1
      end
      if l > r 
        break
      end
      t=a[l]
      a[l]=a[r]
      a[r]=t
      l += 1
      r -= 1
    end 
    return l
  end 

  def quick_sort(a, i, j)
    if i == j 
      return
    end
    p = pivot(a, i, j)
    if p != -1
      k = partition(a, i, j, a[p])
      quick_sort(a, i, k - 1)
      quick_sort(a, k, j)
    end 
  end 

  def run(list)
    a = list.dup
    quick_sort(a, 0, a.size - 1)
    a
  end
end

Although finding a pivot is a little tricky, quick sort is a cool algorithm. It is so elaborated that it almost looks like magic.

Usually Java or C/C++ is used to describe algorithms, but Ruby is also great because it can highlight the essence of algorithms with a fewer lines. I LOVE RUBY, MAY RUBY LIVE FOREVER!