I decided to take on sorting as this week’s technical blog topic. I’ve done some sorting algoritem in Ruby in the past, this gives me the chance to do a couple more. Enough talking, I like staring at the sorting animation on Wiki to get an idea how to write these codes, so let’s just jump right into examples.

Selection sort

Pretty animation:

Selection animation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def selection_sort(arry)
  (0..(arry.size-1)).each do |i|
    (i..(arry.size-1)).each do |j|
      min = arry[i]
      if min >= arry[j]
        arry[i], arry[j] = arry[j], arry[i]
      end
    end
  end
  arry
end

Insertion Sort

Pretty animation:

Insertion Sort

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def insertion_sort(arry)
  (0..(arry.size-1)).each do |i|
    j = i - 1
    while j>=0
      if arry[i] < arry[j]
        arry[i],arry[j] = arry[j],arry[i]
      end
      j -= 1
    end
  end
  arry
end

Notice the similarity between selection and interstion sort?

Bubble Sort

Pretty animation:

Bubble Animation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def bubble_sort(arry)
  sorted = false
  until sorted
    sorted = true
    (arry.size-1).times do |idx|
      if arry[idx] > arry[idx+1]
        arry[idx], arry[idx+1] = arry[idx+1], arry[idx]
        sorted = false
      end
    end
  end
  arry
end

Quick Sort

Pretty animation:

Quick Animation

1
2
3
4
5
6
7
def quick_sort arr
  return arr if arr.length <= 1
  middle = arr.pop
  less = arr.select { |x| x < middle }
  more = arr.select { |x| x >= middle }
  quick_sort(less) + [middle] + quick_sort(more)
end

Merge Sort

Pretty animation:

Merge Animation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def merge_sort(array)
  return array if array.length <= 1
  middle_idx = array.length/2
  left = merge_sort(array[0, middle_idx])
  right = merge_sort(array[middle_idx..-1])
  merge(left, right)
end

def merge(left, right)
  return left if right.empty?
  return right if left.empty?
  if left.first < right.first
    [left.first] + merge(left[1..-1], right)
  else
    [right.first] + merge(left, right[1..-1])
  end
end

Merge_sort has a helper method merge, but it feels very similar to quick sort, don’t you think?

Will probably update this post with more sorting algoritems once I figure out how to write them as codes.