Insertion Sort Algorithm in Data Structures

The idea behind Insertion Sort Algorithm in Data Structures is quite similar to the way we sort cards in a hand game. We choose an unsorted element and place it at its correct position i.e., the position, where the elements to the right of it are greater than the element and the elements to the left, is smaller than the element.

First, we assume that the element at the first position is already sorted and we start comparing the elements after it. We will now diagrammatically understand this algorithm.

Let us assume the array given below with elements {9,3,12,18,5}

As we had assumed that the first element is already sorted so we will take the second element and compare it with other elements.

We will take element 3 and place it before 9 as it is less than 9.

Now, we will take the next element,i.e., 12 but it is already placed at its correct position.

After that, we will check for element 18, but it’s also placed in its correct position.

Now, we will check for the last element i.e., 5, and place it in its correct position shifting all the elements that will appear after it to the right.

So, now the array is turned to be sorted.

We will now understand the codes for this algorithm –

#include <iostream>

using namespace std;

void printArray(int array[], int size) {

  for (int i = 0; i < size; i++) {

    cout << array[i] << " ";

  }

  cout << endl;

} 

void insertionSort(int array[], int size) {

  for (int step = 1; step < size; step++) {

    int key = array[step];

    int j = step - 1;

    while (key < array[j] && j >= 0) {

      array[j + 1] = array[j];

      --j;

    }

    array[j + 1] = key;

  }

}

int main() {

  int data[] = {9, 3,12,18,5};

  int size = sizeof(data) / sizeof(data[0]);

  insertionSort(data, size);

  cout << "Sorted array in ascending order:\n";

  printArray(data, size);

}

Now we will check for the time complexities of the Insertion Sort Algorithm –

Best Time Complexity for Insertion Sort Algorithm– O(n)

Average Time Complexity for insertion Sort Algorithm– O(n²)

Worst Time Complexity for Insertion Sort Algorithm– O(n²)

The best time complexity occurs when the array is already sorted. In this case, only the outer loop will run. So thereby giving the time complexity of O(1).

The space complexity for of Insertion Sort Algorithm is O(1).

So, in this article, we learned about one more sorting algorithm which is insertion sort which is commonly used when the array consists of a small number of elements. Because of the small number of elements, only a few comparisons to the left are made.

Try these quizzes

Stacks in Data Structures and Algorithms MCQ Test

Array in Data Structures and Algorithms MCQ Test