04. Insertion Sort

Algorithm Pseudocode

  1. Partition the array into two subarrays - the first value will be the "sorted" array, and the others will be in an "unsorted" array.
  2. Take the first value x in the unsorted array and store into a temp.
  3. Moving down the list in the sorted array, shift over every element greater than x.
  4. Insert x and repeat.

Visualization

Here's a nifty animation for your better learning.

Characteristics

Insertion sort is the best choice when data is nearly sorted or the problem size is small. Thus, it's a good choice for higher divide-and-conquer sorting algorithms such as merge sort and quick sort.

Furthermore, it is considered to have low overhead since it avoids executing unneccesary lines of code.

Insert sort is stable sorting algorithm.

Complexity

If our array is already sorted, only n-1 comparisons are used. In the worst case, n(n-1)/2 comparisons are used. Time: O(n2) Space: O(1)

Implementation in Java

Here's a sample implementation written in Java. Note that it extends the Sort.java class.

import java.util.Arrays;
 
public class InsertionSort extends Sort {
 
  public static void main(String[] args) {
 
    int[] testInt = {1,6,2,3,6,7,4,2,5};
 
    insertionSort(testInt);
    System.out.println(Arrays.toString(testInt));
  }
 
  public static void insertionSort(int[] test) {
 
    /**
     * The array will be partitioned to two subarrays - the sorted
     * and unsorted. The first element will be in our sorted subarray.
     */
    for (int i = 1; i < test.length; i++) {
 
      // Store the element to insert
      int temp = test[i];
 
      /** 
       * For every element in our sorted subarray that is greater 
       * than the temp, shift elements over one. 
       */
      for (int j = i-1; j >= 0; j--) {
        if (temp < test[j]) {
          test[j+1] = test[j];
        } else {
          test[j+1] = temp;
          break;
        }
      }
 
    }
 
  }
 
}

Ace your Technical Interview

Introduction to Algorithms

Ace your Technical Interview Try Algorithms

Introduction to Algorithms uniquely combines rigor and comprehensiveness. The book covers a broad range of algorithms in depth, yet makes their design and analysis accessible to all levels of readers. The algorithms are described in English and in a pseudocode designed to be readable by anyone who has done a little programming.

$ Check price
9999Amazon 4.5 logo(418+ reviews)

More Algorithms resources

Aching back from coding all day?

Inversion Therapy Table

Aching back from coding all day? Try Back Problems

Stretch out your back and relieve your back muscles with inversion therapy. This device counteracts the forces of gravity on the body by decompressing and elongating the spine. By using this product just ten minutes a day, you can be well on your way to improved circulation and posture while relieving muscle aches, back pain and stress.

$$ Check price
119.98119.98Amazon 4.5 logo(1,700+ reviews)

More Back Problems resources

Ad