Sorting Algorithms in Ruby

Having enjoyed excellent posts on sorting algorithms I wanted to share my implementation of common sorting algorithms in Ruby. There are some great visualizations of sorting algorithms especially on Mike Bostock's blog such as the Fisher-Yates Shuffle, merge sort, and quick sort. Taking a leaf out of Jesse La Russo's blog below are my implementations of common sorting algorithms in Ruby.

Insertion Sort

  1. Begin at the second element. Compare the element to the element prior. Swap if less than the element prior.
  2. Increment by one element. Compare this element to prior two elements. Insert accordingly.
  3. Continue incrementing by one element and comparing that element to all prior sorted elements until the list is fully sorted.
def insertion_sort(list)  
  (1...list.length).each do |i| 
      k = i
      while k > 0 && list[k] < list[k-1]
        list[k], list[k-1] = list[k-1], list[k]
        k -= 1
      end
  end
  list
end  

Selection Sort

  1. Start at first element of unsorted list. Look for the smallest element in the list. Swap with left most unsorted element.
  2. Move to the second element. Swap with smallest element of this unsorted list.
def selection_sort(list)  
  (0...list.length).each do |i|
    k = i

    (i+1...list.length).each do |j|
      k = j if list[j] < list[k]
    end

    if k != i
      list[i],list[k] = list[k],list[i] 
    end
  end
  list
end  

Bubble Sort

  1. Start at first element. Compare adjacent pairs. Swap if out of order.
  2. Iterate through the list repeatedly. Each iteration requires one less comparison.
def bubble_sort(list)  
  begin

    swapped = false
    (1...list.length).each do |i|

      if list[i] < list[i-1]
        list[i], list[i-1] = list[i-1],list[i]
        swapped = true
      end

    end

  end until !swapped
  list
end  

Shell Sort

(Insertion sort on sublists or sublists of elements allowing swap of elements far apart.)

  1. Determine sublists by splitting the list in half repeatedly.
  2. Insertion sort of the elements in each sublist.
  3. When the sublist is one or zero elements long then the list is sorted.
def shell_sort(list)  
  gap = list.length/2
  while gap > 0

    # Insertion Sort
    (gap...list.length).each do |i|
      k = i
      while k >= gap && list[k] < list[k-gap]
        list[k], list[k-gap] = list[k-gap], list[k]
        k -= gap
      end
    end

    gap /= 2
  end
  list
end  

Merge Sort

  1. Divide the unsorted list into sublists around a pivot.
  2. Recursively call merge sort on the sublists.
  3. Merge the results of the recursive calls.
def merge_sort(list)  
  return list if list.length <= 1
  left = []
  right = []
  pivot = list.length / 2

  list.each_with_index do |e,i|
    left << e if i < pivot
  end

  list.each_with_index do |e,i|
    right << e if i >= pivot
  end

  left = merge_sort(left)
  right = merge_sort(right)

  merge(left, right)
end

def merge(left, right)  
  result = []
  while left.length > 0 || right.length > 0
    if left.length > 0 && right.length > 0
      result << (left[0] <= right[0] ? left.shift : right.shift)
    elsif left.length > 0
      result << left.shift
    else
      result << right.shift
    end
  end
  result
end  

Heap Sort

  1. Build a heap out of the data. The heap is a tree data structure where the parent node is always greater than or equal to its child nodes across the entire heap.
  2. Remove the root of the heap and insert in sorted array. Reconstruct heap and repeat.
def heap_sort(list)  
  count = list.length

  heapify(list, count)

  last = count - 1
  while last > 0
    p "#{list[last]}, #{list[0]}"
    list[last], list[0] = list[0], list[last]
    last -= 1
    sift_down(list,0,last)
  end

  list
end

def heapify(list, count)  
  start = (count - 2) / 2

  while start >= 0
    sift_down(list,start,count-1)
    start -= 1
  end
end

def sift_down(list, start, last)  
  root = start

  while root * 2 + 1 <= last
    child = root * 2 + 1
    swap = root

    swap = child if list[swap] < list[child]
    if child + 1 <= last && list[swap] < list[child+1]
      swap = child + 1 
    end
    if swap != root
      list[root], list[swap] = list[swap], list[root]
      root = swap
    else
      return
    end
  end
end  

Quick Sort

  1. Divide list into two smaller lists.
  2. Pick a pivot.
  3. Reorder list so that all elements less than the pivot come before it and all elements greater than the pivot come after it.
  4. Recursively apply steps 2 and 3 to the sublists until base case of size 0 or 1 lists is reached.
def quick_sort(list)

  return list if list.length <= 1

  pivot = list[list.length/2]

  less, greater = list.partition {|e| e < pivot}

  quick_sort(less) + [pivot] + quick_sort(greater)

end  
Show Comments