COMP1927 - Insertion Sort

Insertion Sort works by comparing each element to the elements in the sorted list before it, and bubbling (swapping it with the element, recomparing, reswapping, etc) it into place.

Type

Adaptive (as the number of swaps changes depending on pre-sortedness)
Stable
In-Place

Complexity

Insertion sort has an O(n2) average and worst case complexity (where it's reverse sorted), an O(n) best case (1 comparison per item).

Example

insertion%20%2B%20sort_thumb%5B1%5D.jpg

Code

void insertionSort (int array[], int length) {
 
   int i;
   int unsorted = 0;
   int temp;
   int placed;
 
   for (unsorted = 0; unsorted < length; unsorted++) {
      placed = FALSE;
      for (i = (unsorted-1); (i >= 0) && (!placed); i--) {
         if (array[unsorted] < array[i]) {
            temp = array[unsorted];
            array[unsorted] = array[i];
            array[i] = temp;
            unsorted--;
         } else {
            placed = TRUE;
         }
      }    
   }
 
}