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!
