## Tuesday, August 9, 2011

### 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.

```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!