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 endHeap 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 endThe 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!

## No comments:

Post a Comment