Insertion Sort

Repeatedly take elements from unsorted subarray and insert in sorted subarray

Introduction

Insertion Sort is a straightforward comparison-based sorting algorithm that builds the sorted portion of the array incrementally. Starting with the first element as "sorted," it repeatedly takes the next element from the unsorted portion and "inserts" it into its correct position within the sorted section by shifting elements as needed. This process continues until the entire array is sorted. While simple and efficient for small or nearly sorted datasets, Insertion Sort has a time complexity of 𝑂(𝑛²) in the average and worst cases.

How Insertion Sort Works?

1

Start with the first element

The first element is inherently "sorted."

2

Pick the next element

Move to the next element in the array (the first element of the unsorted section).

3

Compare and shift

Compare this element with elements in the sorted section. Shift the elements in the sorted section that are greater than this element one position to the right.

4

Insert the element

Place the picked element into its correct position in the sorted section.

5

Repeat

Repeat the process for all elements in the unsorted section until the array is fully sorted.

Implementation of Insertion Sort

// insertionsort.cpp
#include <iostream>
#include <vector>
using namespace std;
void insertionSort(vector<int> &v)
{
int n = v.size(); 
for (int i = 1; i < n; i++)
{
    int current_ele = v[i];
    int j = i - 1;
    while (j >= 0 && v[j] > current_ele){
        v[j+1]=v[j];
        j--;
    }
    v[j+1]=current_ele;
}
return;
}
int main()
{
vector<int> v{7, 2, 1, 5, 3, 6, 7};
insertionSort(v);
for(int ele:v){
    cout<<ele<<" ";
}
}

Time Complexity

  • Best Case:O(n), When the array is already sorted or nearly sorted.
  • Average Case:O(n*n), When the array is in random order.
  • Worst Case: O(n*n),When the array is sorted in descending order.

Space Complexity

  • Constant Space:O(1)
  • Space Complexity:O(1)