Insertion Sort Algorithm with Space & Time Complexity

by

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Learn Bubble Sort Algorithm with Space & Time Complexity analysis.

Keep Learning.

Insertion Sort Algorithm

  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.
  4. Repeat step 3 until the key element is greater than its predecessor.
  5. The array is now sorted.

Insertion sort has a time complexity of O(n^2) in its worst-case scenario.

Insertion sort is a simple sorting algorithm that works well for small or mostly sorted arrays. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. It is also an in-place sorting algorithm, which means it sorts the array in place without requiring any additional memory.

To implement insertion sort in code, we can use a loop to iterate over the array, and an inner loop to compare the current element to its predecessor and swap them if necessary.

Here’s an example implementation in C++
#include<iostream>
using namespace std;

int Insertion_sort(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;
    }

    cout<<"After Sorting: ";
    for(int i=0; i<n; i++)
    {
        cout<<A[i]<<' ';
    }
}

int main(){
   int arr[] = {43,31,26,29,12};

   int n = sizeof(arr)/sizeof(arr[0]);

   Insertion_sort(arr,n);


return 0;
}

Complexity Analysis

Time Complexity
  • In best case scenario, Runtime Complexity: O(n)
  • In worst case scenario, Runtime Complexity: O(n^2)
  • In average case scenario, Runtime Complexity: O(n^2)
Space Complexity

Since there is no extra space required to implement the sorting, that’s why space complexity is O(1).

Thanks For Visiting. Keep Learning.

Leave a Comment