amber tunnell

puts 'my thoughts on the magic that is code'

Sorting Algorithms Series: Insertion Sort

| Comments

Like Bubble Sort, Insertion Sort is a simple sorting algorithm.

Insertion Sort works by iterating up the current array, placing the current element into the correct place in the new sorted array.

  1. First, take the first element of the unsorted array out of the array and put it into an empty new array.
  2. Take the next element out of the unsorted array and place it into the new array. If it is smaller than the first element in the new array, swap them. If not, leave it at the end.
  3. Take the next element out of the array and put it at the end of the new array. If it is larger than the previous end element, leave it. If not, iterate through the array until you find its correct position and insert it there.
  4. Continue this process until your original array is empty and you have a new completely sorted array.

insertion sort video

While more efficent than Bubble Sort, Insertion Sort still has the same average and worse case time complexity of O(n2). Like Bubble Sort, it is very inefficient for large data sets, but rather efficient for small data sets or data sets already mostly sorted (the best case time complexity is O(n)).

Implementation of Insertion Sort in Ruby.

Insertion Sort in Ruby
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class InsertionSort

  def initialize(array)
    @array = array
    @sorted_array = []
  end

  def sort
    j = 0
    while @array.length > 0
      @sorted_array << @array.shift
      if @sorted_array.length > 1 && @sorted_array[j-1] > @sorted_array[j]
        @sorted_array.each.with_index do |n, i|
          if @sorted_array[i] > @sorted_array[-1]
            @sorted_array[i], @sorted_array[-1] = @sorted_array[-1], @sorted_array[i]
          end
          if (@sorted_array[i] <  @sorted_array[-1]) && (@sorted_array[i+1] > @sorted_array[-1])
            @sorted_array.insert(i+1, @sorted_array[-1])
            @sorted_array.slice!(-1)
          end
        end
      end
      j+=1
    end
    @sorted_array
  end
end

print InsertionSort.new([4,1,6,3,5,2]).sort #=> [1, 2, 3, 4, 5, 6]

And in JavaScript:

Insertion Sort in JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

function insertionSort(array) {
    var sortedArray = [];

    for (var i = 0; i < array.length; i++) {

        sortedArray.push(array[i]);
        var len = sortedArray.length;

        if ((len > 1) && (sortedArray[len - 1] < sortedArray[len - 2])) {
            for (var j = 0; j < len; j++) {
                if ((len === 2) && (sortedArray[j] > sortedArray[len - 1]))
                {
                    var first = sortedArray[j];
                    var second = sortedArray[len - 1];

                    sortedArray[j] = second;
                    sortedArray[len - 1] = first;
                }
                else if ((sortedArray[j] <= sortedArray[len - 1])
                && (sortedArray[len - 1] <= sortedArray[j + 1]))
                {
                    //Insert the new element where it belongs.
                    sortedArray.splice(j + 1, 0, sortedArray[len - 1]);
                    // Delete it from the end of the array.
                    sortedArray.splice(sortedArray.length - 1, 1);
                }
            }
        }
    }
    return sortedArray;

}

insertionSort([4, 1, 2, 6, 3, 5]); //=> [1, 2, 3, 4, 5, 6]

This is the second post in a series of posts on various sorting algorithms in computer science. See the entire series here.

Comments