Insertion Sort
Table of Contents
|
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
- Start with the second element in the array.
- If larger than the previous element, the element stays where it currently is.
- 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.
- Place the element in the vacant space.
- Repeat steps 2-5 for each of the remaining elements in the array.
Visual Insertion Sort
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.