Insertion Sort

Definition

Insertion sort is a sorting algorithm that moves each element in an array backwards until it finds its proper place. Insertion sort performs particularly well on small arrays and arrays that are almost ordered.

Algorithm

  1. Start with the second element in the array.
  2. If larger than the previous element, the element stays where it currently is.
  3. If it is less keep checking elements to the left until the element we are sorting is greater than or equal the one to it's left while shifting each of the elements that are greater one space to the right.
  4. Place the element in the vacant space.
  5. Repeat steps 2-5 for each of the remaining elements in the array.

Visual Insertion Sort

flickr:3009478710

Code

public static void insertionSort(int[] x){
    int toSort = 0;
    int position = 0;
 
    for(int i = 1; i < x.length; i++){
        toSort = x[i];
        for (position = i-1; position >= 0 && toSort < x[position]; position--){
            x[position+1] = x[position];
        }
        x[position+1] = toSort;
    }
}

Runtime

Best Case

The best case scenario will occur when the array is already in correct order. In this case, the program will test each number against the one before it and find that it is already in the correct position, thus giving a runtime of O(n).

Worst Case

The worst case scenario will occur when the array is in reverse order. Here, the program will have to move each element all the way back to the beginning of the array, thus giving a runtime of O(n2).

Advantages

  • Very fast when dealing with small arrays.
  • Fast when array is mostly ordered.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License