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.
- worst case: O(n^2) (this is really bad for large lists)
- iterate through each item in the list.
- continue swapping the current element to as close to the start of the list as possible.
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