This is another simple sorting algorithm, that inspects one elment at a time and finds the proper insertion point for it. It’s advantage is that everything on the left side of the list is always sorted as it traverses through the list.

It’s very simple to implement. It is efficient for small lists. It works well for nearly sorted data.

steps

  1. iterate through each item in the list.
  2. continue swapping the current element to as close to the start of the list as possible.

example

In this example, we iterate through the list forward. As we inspect each element, we move through the list backward until we find the best insertion point for the element.

class InsertionSort
  def sort(items)
    items.size.times do |n|
      j = n
      while j >= 0 do
        if (items[j] <=> items[j+1]) == 1
          items[j], items[j+1] = items[j+1], items[j]
        end
        j-=1
      end
    end
    items
  end
end
comments powered by Disqus