Implement Insertion Sort with Time complexity

Insertion Sort
Spread the love

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The procedure of the insertion sorting algorithm is that the given array is divided into two parts. There are the sorted array and unsorted array. We select a value from the unsorted part and then put it on the sorted side.

Algorithm of Insertion Sort

To sort an array of size n in ascending order: 
1: Iterate from arr[1] to arr[n] over the array. 
2: Compare the current element (key) to its predecessor. 
3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Read More : How to implement interpolation search using recursion

Let’s see the following code.


def insertion_sort_asc(A, n):
    for i in range(1, n):
        temp = A[i]
        j = i-1
        while j >= 0 and A[j] >= temp:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = temp

Well, this function takes two parameters. The first parameter is our given array and the second parameter is the size of the array. Inside the function, we have to execute a loop from one index to the previous index of array length. Then take a variable and store the value of A[i]. After then take another variable and store i – 1.

Well, now you have to execute another loop, and its conditions are j value is greater than or equal to zero as well as A[j] value is greater than temp value. After then exchange the value of A[j+1] with A[j]. Then decrease the length of j. Finally, out the second loop and exchange the value of A[j+1] with temp. And our work has been done.

The time complexity of insertion sort is O(n^2).

Full Code in Python

def insertion_sort_asc(A, n):
    for i in range(1, n):
        temp = A[i]
        j = i-1
        while j >= 0 and A[j] >= temp:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = temp


def insertion_sort_dsc(A, n):
    for i in range(1, n):
        temp = A[i]
        j = i-1
        while j >= 0 and A[j] <= temp:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = temp


arr = [5, 1, -8, 4, 2, 3]
len = len(arr)

print(arr)
insertion_sort_dsc(arr, len)
print(arr)

Learn Laravel

Full Code of Insertion sort in C++

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

void print_array(int A[], int n)
{
    cout << endl;
    for (int i = 0; i < n; i++)
    {
        cout << A[i] << " ";
    }
    cout << endl;
}
void selection_sort_asc(int A[], int n)
{
    for (int i = 1; i < n; i++)
    {
        int temp = A[i];
        int j = i - 1;

        while (j >= 0 && A[j] >= temp)
        {
            A[j + 1] = A[j];
            j--;
        }

        A[j + 1] = temp;
    }
}
void selection_sort_dsc(int A[], int n)
{
    for (int i = 1; i < n; i++)
    {
        int temp = A[i];
        int j = i - 1;

        while (j >= 0 && A[j] < temp)
        {
            A[j + 1] = A[j];
            j--;
        }

        A[j + 1] = temp;
    }
}
int main()
{
    int A[] = {3, 4, 1, 2, 10};
    int n = 5;
    print_array(A, n);
    selection_sort_asc(A, n);
    print_array(A, n);
    return 0;
}

Github Link: https://github.com/AR-Shahin/Data_Structure_and_Algorithm

Read More Artical : Implement Quick Sort using Python and C++ & Time complexity

Spread the love

About Anisur Rahman Shahin

Hello. My name is Shahin. I'm a tech enthusiast guy. Personally, I’m Optimistic and always in hurry kinda person. I'm a freelance web developer. I am working at Zakir Soft as Laravel Developer. My Portfolio website: https://devshahin.com/

View all posts by Anisur Rahman Shahin →

Leave a Reply

Your email address will not be published.