Insertion Sort

Insertion Sort

You are given an array containing 𝑁 integers. Your task is to implement the Insertion Sort algorithm to sort this array.

Example:

Input:=6,array = {13, 46, 24, 52, 20, 9}

Output: 9, 13, 20, 24, 46, 52

Solution:

Note: Don't jump directly to the solution, try it out yourself first.

Approach: 

The goal is to sort an array using the insertion sort algorithm. The key idea is to build a sorted section of the array one element at a time. Here’s a step-by-step breakdown of the approach:

• Selection: Iterate through each element in the unsorted array.

• Insertion: For each selected element, place it in its correct position within the already sorted section of the array. This requires comparing the selected element to the elements in the sorted section.

• Shifting: If necessary, shift elements in the sorted section to make room for the new element by using a while loop that performs swaps until the correct position is found.

Dry Run:

• The purple color represents the unsorted array.
• The yellow color represents the current element that needs to be placed in the appropriate position.
• The green color represents the sorted array.

Outer loop iteration 1(selected index i = 0): The element at index i=0 is 13 and there is no other element on the left of 13. So, currently, the subarray up to the first index is sorted as it contains only element 13.

Outer loop iteration 2(selected index i = 1):

The selected element at index i=1 is 46. Now, we will try to move leftwards and put 46 in its correct position. Here, 46 > 13 and so 46 is already in its correct position. Now, the subarray up to the second index is sorted.

Outer loop iteration 3(selected index i = 2):

The selected element at index i=2 is 24. Now, we will try to move leftwards and put 24 in its correct position. Here, the correct position for 24 will be index 1. So, we will insert 24 in between 13 and 46. We will do it by swapping 24 and 46. Now, the subarray up to the third index is sorted.

Outer loop iteration 4(selected index i = 3):

The selected element at index i=3 is 52. Now, we will try to move leftwards and put 52 in its correct position. Here, the correct position for 52 will be index 3. So, we need not swap anything. Now, the subarray up to the fourth index is sorted.

Outer loop iteration 5(selected index i = 4):

The selected element at index i=4 is 20. Now, we will try to move leftwards and put 20 in its correct position. Here, the correct position for 20 will be index 1. So, we need to swap adjacent elements until 20 reaches index 1. Now, the subarray up to the fifth index is sorted.

Outer loop iteration 6(selected index i = 5):

The selected element at index i=5 is 9. Now, we will try to move leftwards and put 9 in its correct position. Here, the correct position for 9 will be index 0. So, we need to swap adjacent elements until 9 reaches index 0. Now, the whole array is sorted.

CODE  

#include<iostream>
using namespace std;

void insertion_sort(int arr[], int n) {
    for (int i = 0; i <= n - 1; i++) {
        int j = i;
        while (j > 0 && arr[j - 1] > arr[j]) {
            int temp = arr[j - 1];
            arr[j - 1] = arr[j];
            arr[j] = temp;
            j--;
        }
    }

    cout << "After Using insertion sort: " << "\n";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

int main()
{
    int arr[] = {13, 46, 24, 52, 20, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Before Using insertion Sort: " << endl;
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;

    insertion_sort(arr, n);
    return 0;
}

OUTPUT  

Before insertion sort:
13 46 24 52 20 9
After insertion sort:
9 13 20 24 46 52

Time complexity: O(N*N), (where N = size of the array), for the worst, and average cases.
Reason: If we carefully observe, we can notice that the outer loop, say i, is running from 0 to n-1 i.e. n times, and for each i, the inner loop j runs from i to 1 i.e. i times. For, i = 1, the inner loop runs 1 time, for i = 2, the inner loop runs 2 times, and so on. So, the total steps will be approximately the following: 1 + 2 + 3 +......+ (n-2) + (n-1). The summation is approximately the sum of the first n natural numbers i.e. (n*(n+1))/2. The precise time complexity will be O(n2/2 + n/2). Previously, we have learned that we can ignore the lower values as well as the constant coefficients. So, the time complexity is O(n2). Here the value of n is N i.e. the size of the array.

Space Complexity: O(1)

Best Case Time Complexity: 

The best case occurs if the given array is already sorted. And if the given array is already sorted, the outer loop will only run and the inner loop will run for 0 times. So, our overall time complexity in the best case will boil down to O(N), where N = size of the array.