Insertion sort

Introduction:

This is a comparison based sort where we insert ith element into the sorted subarry a[0 .. i-1] at the correct place such that a[0 i] is sorted.

Problem Statement:

Sort an array of n integers

Algorithm

1. In this we kind of assume that subarry a[0 .. i-1] is sorted and insert a[i] in the array at correct place.

2. We run step on input array from i = 0 to n .

Pseudo code :

insertion_sort(a[], n):
    i = 1
    while i < n:
        // sort a[0.. i] i.e., place a[i] in correct place
        temp = a[i]
        j = i-1
        while j >= 0 and a[j] > temp :
            a[j+1] = a[j]
            j--
        a[j+1] = temp  // correct position
        i++

Code :

    #include <bits/stdc++.h>
    using namespace std;

    void insertion_sort(int a[], int n)
    {
        int i = 1; // single element array is sorted (base case)
        while (i < n)
        {
            int temp = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > temp) // finding correct index to place  this element
            {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = temp; // place it
            i++;
        }
    }

    int main()
    {
        int n;
        cout << "Enter n: ";
        cin >> n;
        int a[n];
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        insertion_sort(a, n);
        for (int i = 0; i < n; i++)
        {
            cout << a[i] << " ";
        }
        printf("\n");
    }

Complexity Analysis :

The complexity is \(O(n^2)\) since code has to run maximum n times with each time O(n) complexity for inserting element at correct place in sorted array

best case is \(O(n)\)