Insertion Sort

Insertion sort is a sorting algorithm that while quite inefficient, it is O(n^2), it is really simple to implement. In principle, it involves looping over the array, checking if the current value is greater than the previous value, and if it isn’t we insert it into the ‘correct’ spot of the previously sorted values. This means our invariants are that at the start of the loop all element to the left of i are already sorted.

Algorithm

#include <iostream>  
  
int array[] = {1, 4, 2, 9, 3, 0};  
int n = sizeof(array) / sizeof(array[0]);  
  
int main() {  
    int i = 1; // i starts at the second element  
    for(i; i < n; i++) { //for each element in the array  
        int key = array[i]; //we assign the element to be swapped at i  
        int j = i - 1; // we assign the previous index j, the start of the array to be checked against  
        while(j >= 0 && key < array[j]) { //we then perform an insert on the already sorted array  
            array[j + 1] = array[j]; // we shift elements to the right. This overwrites the value to be shifted, so that's why we need to keep it in the key local.  
            j--; //decrement, we're going backwards into the already sorted array  
        }  
  
        array[j + 1] = key; // we reinsert it when the loop is done, i.e j represents the value of the value where key < j is no longer true  
    }  
    for(int i = 0; i < n; i ++) {  
        std::cout << "Array is: " << array[i] << std::endl;  
    }  
  
}