Insertion Sort

This sorting algorithm works by repeatedly inserting elements into their correct position in an array.

Insertion sort is a simple sorting algorithm that works similarly to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed in the correct position in the sorted part.

Question statement: https://www.codingninjas.com/studio/problems/insertion-sort_3155179

Notes: https://drive.google.com/file/d/10zLQIWEn55nwhFOrHybqnxexf96AX1LE/view

void InsertionSort(int n, vector<int> &arr){
    for(int i = 1; i < n; i++){
        // for rounds 1 to n-1
        //Here we assume 0 index value as sorted
        
        int temp = arr[i];
        int j = i-1;

        for(; j >= 0; j--){
            if(arr[j] > temp) // {1, 4, 2, 3} 
                // Shifting j index value forward by 1
                arr[j+1] = arr[j]; // now array becomes {1, 4, 4, 3} 2 is already stored in temp 
            else 
                break;
        }
        swap(arr[j+1], temp);
    }
}

Space Complexity: constant O(1)

Time complexity:O(n^2)

// 1st round - 1 Comp

// 2nd round - 2 Comp...

// (nth - 1) Round - (n-1) comp 

Best case: Already Sorted = {1, 2, 3, 4,} T.C = O(n)

// total comparisons (n-1) 

Worst Case:Reversed Array = {4, 3, 2, 1} T.C = O(n^2)