Insertion Sort

Insertion Sort

Insertion sort is one of the simplest method to sort an array. In this method the element are inserted at their appropriate place .Hence is the name insertion sort.

An example of an insertion sort occurs in evryday life while playing cards. To sort the card in your hand you extract a card. shift the remaining cards. And then insert the extracted card in the correct place.This process repeated until all the cards are in the correct sequence.

Algorithm of Insertion sort

insertionSort(array)
  mark first element as sorted
  for each unsorted element X
    'extract' the element X
    for j <- lastSortedIndex down to 0
      if current element j > X
        move sorted element to the right by 1
    break loop and insert X here
end insertionSort

Working of Insertion sort algorithm

Suppose the elements of array are –

 

Insertion Sort Algorithm

 

Firstly, the first two elements are compared im sort.

 

Insertion Sort Algorithm

 

Here, 12 is smaller than 31. That is  both elements are in ascending order. So, 12 is stored in a sorted sub-array.

 

Insertion Sort Algorithm

 

Now, move to the next 2 elements and compare between them.

 

Insertion Sort Algorithm

 

Here, 31 is greater than 25. So, 31 is at incorrect position. Now, replace 31 with 25. Along with swapping, it will  check it with all elements in the sorted array.

For now, the sorted array has only one element, i.e. 12. So, 12 is smaller than 25. So, the sorted array remains sorted after the swapping.

 

Insertion Sort Algorithm

 

Now, 2 elements in the sorted array are 12 and 25. Move forward to the next elements 31 and 8.

 

Insertion Sort Algorithm

 

Both 31 and 8 are unsorted. So, swap them.

 

Insertion Sort Algorithm

 

After swapping, elements 25 and 8 are not sorted.

 

Insertion Sort Algorithm

 

So, swap them.

 

Insertion Sort Algorithm

 

Now, elements 12 and 8 are not sorted.

 

Insertion Sort Algorithm

 

So, swap this two elemnt

Insertion Sort Algorithm

 

Now, the sorted array has three elements that are 8, 12 and 25. Move to the next element they are 31 and 32.

 

Insertion Sort Algorithm

 

Hence, they are already sorted. Now, the sorted array contains 8, 12, 25 and 31.

 

Insertion Sort Algorithm

 

Move forward to the next elements they are 32 and 17.

 

Insertion Sort Algorithm

 

32 is greater than 17. So, swap them.

 

Insertion Sort Algorithm

 

Swapping makes 31 and 17 not sorted. So, swap the both element.

 

Insertion Sort Algorithm

 

Now, swapping makes 25 and 17  not sorted. So, perform swapping.

 

Insertion Sort Algorithm

 

Now, the array is completely sorted.

Insertion sort complexity

1. Time Complexity

 

Case Time Complexity
Best Case O(n)
Average Case O(n2)
Worst Case O(n2)

2. Space Complexity

 

Space Complexity O(1)
Stable YES

 

 

Program of insertion sort in C

#include <stdio.h>

// Function to print an array
void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

void insertionSort(int arr[], int size) {
  for (int step = 1; k < size; k++) {
    int key = array[k];
    int j = k - 1;

   // For descending order, change key<arr[j] to key>arr[j].
    while (key < arr[j] && j >= 0) {
      arr[j + 1] = arr[j];
      --j;
    }
    arr[j + 1] = key;
  }
}

// Driver code
int main() {
  int data[] = {9, 5, 1, 4, 3};
  int size = sizeof(data) / sizeof(data[0]);
  insertionSort(data, size);
  printf("Sorted array in ascending order:\n");
  printArray(data, size);
}

Output

Sorted array in ascending order:
1 3 4 5 9 

 

Program of insertion sort in C++

#include <iostream>
using namespace std;

void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}

void insertionSort(int arr[], int size) {
  for (int k = 1; k < size; k++) {
    int key = arr[k];
    int j = k - 1;

    
    // For descending order, change key<arr[j] to key>arr[j].
    while (k < arr[j] && j >= 0) {
      arr[j + 1] = arr[j];
      --j;
    }
    arr[j + 1] = key;
  }
}

// Driver code
int main() {
  int data[] = {9, 5, 1, 4, 3};
  int size = sizeof(data) / sizeof(data[0]);
  insertionSort(data, size);
  cout << "Sorted array in ascending order:\n";
  printArray(data, size);
}

Output

Sorted array in ascending order:
1 3 4 5 9

Program of insertion sort in Python

def insertionSort(array):

    for step in range(1, len(array)):
        key = arr[k]
        j = k - 1
        

        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j = j - 1
        
        arr[j + 1] = key


data = [9, 5, 1, 4, 3]
insertionSort(data)
print('Sorted Array in Ascending Order:')
print(data)

Output

Sorted Array in Ascending Order:
[1, 3, 4, 5, 9]

Program of insertion sort in Java

import java.util.Arrays;

class InsertionSort {

  void insertionSort(int arr[]) {
    int size = arr.length;

    for (int k = 1; k < size; k++) {
      int key = arr[k];
      int j = k - 1;

      // For descending order, change key<arr[j] to key>arr[j].
      while (j >= 0 && key < arr[j]) {
        arr[j + 1] = arr[j];
        --j;
      }

      arr[j + 1] = key;
    }
  }

  // Driver code
  public static void main(String args[]) {
    int[] data = { 9, 5, 1, 4, 3 };
    InsertionSort is = new InsertionSort();
    is.insertionSort(data);
    System.out.println("Sorted Array in Ascending Order: ");
    System.out.println(Arrays.toString(data));
  }
}

Output

Sorted Array in Ascending Order: [1, 3, 4, 5, 9]

 

Insertion Sort Applications

  • The array is has a small number of elements
  • There are only a few elements left to be sorted

 

Also read, Selection sort

 

Share this post

Leave a Reply

Your email address will not be published. Required fields are marked *