Insertion Sort Algorithm

In this tutorial, you will learn how insertion sort functions. Likewise, you will discover working instances of insertions sort in C, C++, Java, and Python.

What is Insertion Sort Algorithm?

• It is one of the most effortless and beast power sorting algorithm

• Insertion sort is used to sort elements in one or the other ascending or descending order

• In insertion sort, we keep a sorted part and unsorted part

• It works much the same as playing a card game i.e, picking one card and sorting it with the cards that we have in our hand as of now

• With each iteration, one item is moved from the unsorted segment to the sorted segment

• The first element is picked and is viewed as sorted

• After this, we begin picking from the second element forward and compare and elements in the sorted area

• We continue to move the elements from the sorted area individually until a proper area is found for that element

• This measure is proceeded until all elements have been exhausted

---

Insertion sort works also as we sort cards in our hand in a card game.

We assume that the first card is now sorted at that point, we select an unsorted card. On the off chance that the unsorted card is more prominent than the card in hand, it is set on the right in any case, to the left. Similarly, other unsorted cards are taken and put in their right spot.

A comparative methodology is used by insertion sort.

Insertion sort is a sorting algorithm that puts an unsorted element at its reasonable spot in every iteration.

---

How Insertion Sort Works?

Assume we need to sort the accompanying array.

• 

1. The first element in the array is thought to be sorted. Require the second element and store it independently in key.

Compare key and the first element. On the off chance that the primary element is more prominent than key, then key is set before the first element.

• 

2. Presently, the initial two elements are sorted.

Take the third element and compare it and the elements on its left. Set it simply behind the element smaller than it. On the off chance that there is no element smaller than it, then place it toward the start of the array.

• 

3. Also, place each unsorted element at its correct position.

• 

• 

---

Insertion Sort Algorithm

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

---

Python, Java, and C/C++ Examples

Python

# Insertion sort in Python


def insertionSort(array):

    for step in range(1, len(array)):
        key = array[step]
        j = step - 1
        
        # Compare key with each element on the left of it until an element smaller than it is found
        # For descending order, change key<array[j] to key>array[j].        
        while j >= 0 and key < array[j]:
            array[j + 1] = array[j]
            j = j - 1
        
        # Place key at after the element just smaller than it.
        array[j + 1] = key


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

Java

// Insertion sort in Java

import java.util.Arrays;

class InsertionSort {

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

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

      // Compare key with each element on the left of it until an element smaller than
      // it is found.
      // For descending order, change key<array[j] to key>array[j].
      while (j >= 0 && key < array[j]) {
        array[j + 1] = array[j];
        --j;
      }

      // Place key at after the element just smaller than it.
      array[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));
  }
}

C

// Insertion sort in C

#include <stdio.h>

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

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

    // Compare key with each element on the left of it until an element smaller than
    // it is found.
    // For descending order, change key<array[j] to key>array[j].
    while (key < array[j] && j >= 0) {
      array[j + 1] = array[j];
      --j;
    }
    array[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);
}

C++

// Insertion sort in C++

#include <iostream>
using namespace std;

// Function to print an array
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;

    // Compare key with each element on the left of it until an element smaller than
    // it is found.
    // For descending order, change key<array[j] to key>array[j].
    while (key < array[j] && j >= 0) {
      array[j + 1] = array[j];
      --j;
    }
    array[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);
}

---

Complexity

Time Complexities

• Worst Case Complexity: O(n²)

Assume, an array is in ascending order, and you need to sort it in descending order. For this situation, the worst scenario complexity happens.

Every element must be compared and every one of different elements in this way, for each nth element, (n-1) number of comparisons are made.

Subsequently, the all out number of comparisons = n*(n-1) ~ n²

• Best Case Complexity: O(n)

At the point when the array is sorted, the external loop runs for n number of times while the internal loop doesn’t run by any means. In this way, there is just n number of comparisons. Accordingly, complexity is straight.

• Average Case Complexity: O(n²)

It happens when the elements of an array are in jumbled order (neither ascendind nor descending).

Space Complexity

Space complexity is O(1) on the grounds that an additional variable key is used.

---

Insertion Sort Applications

The insertion sort is used when:

• the array has few elements
• there are a couple of elements left to be sorted

---

Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.

Sorting and Searching Algorithms