Insertion Sort Algorithm

Example of Insertion Sort Algorithm

Let’s take an example to understand Insertion Sort Algorithm:
Take an array A[] = [ 7, 5, 4, 2 ]

Since 7 is the first element that has no other element to be compared with, it remains at its position. Now when on moving towards 4, 7 is the largest element in the sorted list and greater than 4. So, move 4 to its correct position, i.e., before 7. Similarly, with 5, as 7 (the largest element in the sorted list) is greater than 5, we will move 5 to its correct position. Finally, for 2, all the elements on the left side of 2 (sorted list) are moved one position forward as all are greater than 2, and then two is placed in the first position. Finally, the given array will result in a sorted array.

Implementation of Insertion Sort

• C
• C++
• Python
• Java
• JavaScript
• PHP
• C#

C

#include <stdio.h>

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

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);
    printArray(arr, n);

    return 0;
}

You can also try this code with Online C Compiler

Run Code

C++

#include <iostream>
using namespace std;

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

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

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

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);
    printArray(arr, n);

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

def print_array(arr):
    print(" ".join(map(str, arr)))

arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print_array(arr)

You can also try this code with Online Python Compiler

Run Code

Java

public class InsertionSort {
    public static void insertionSort(int arr[]) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void printArray(int arr[]) {
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6};
        insertionSort(arr);
        printArray(arr);
    }
}

You can also try this code with Online Java Compiler

Run Code

JavaScript

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

function printArray(arr) {
    console.log(arr.join(" "));
}

let arr = [12, 11, 13, 5, 6];
insertionSort(arr);
printArray(arr);

You can also try this code with Online Javascript Compiler

Run Code

PHP

<?php
function insertionSort($arr) {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;

        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
    return $arr;
}

function printArray($arr) {
    echo implode(" ", $arr) . "\n";
}

$arr = [12, 11, 13, 5, 6];
$arr = insertionSort($arr);
printArray($arr);
?>

You can also try this code with Online PHP Compiler

Run Code

C#

using System;

class InsertionSortExample
{
    static void InsertionSort(int[] arr)
    {
        int n = arr.Length;
        for (int i = 1; i < n; i++)
        {
            int key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    static void PrintArray(int[] arr)
    {
        foreach (int item in arr)
            Console.Write(item + " ");
        Console.WriteLine();
    }

    static void Main()
    {
        int[] arr = { 12, 11, 13, 5, 6 };
        InsertionSort(arr);
        PrintArray(arr);
    }
}

Output

5 6 11 12 13

Insertion Sort Complexity

In both the worst and average scenarios, where 'n' is the number of elements, Insertion Sort has an O(n^2) time complexity. This is because it could, in the worst case, involve nested loops for swaps and comparisons. But in the best scenario (when the list is already sorted), it has an efficient time complexity of O(n).

Since Insertion Sort doesn't need extra memory in proportion to the input size, its space complexity is O(1). Sorting in place or rearranging elements within the current array without allocating new memory. Although Insertion Sort is straightforward and appropriate for small datasets, it loses efficiency when applied to larger datasets compared to more advanced sorting algorithms like Quick Sort or Merge Sort.

Features of Insertion Sort

There are several characteristics of Insertion Sort are discussed below:

• Insertion Sort is efficient for smaller data sets but can be inefficient for larger data sets.
   
• Insertion Sort is an adaptive algorithm means it can be used for arrays that are partially sorted appropriately.
   
• Easy and Simple Implementation is also one of the characteristics because every beginner can learn this sorting algorithm.
   
• The space complexity is lesser as we don't have to create extra memory other than the given array of elements that are to be sorted.
   
• In the best case, where the array is already sorted, Time Complexity will be linear O(n).

Advantages of Insertion Sort Algorithm

• Simple Implementation: Insertion sort is straightforward to implement and understand, making it a good choice for beginners learning sorting algorithms.
   
• Efficient for Small Datasets: For small arrays or lists, insertion sort performs well compared to more complex algorithms due to its low overhead.
   
• Stable Sorting: Insertion sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements, which is beneficial for certain applications.
   
• Adaptive: The algorithm is adaptive, meaning it performs better on partially sorted data. It requires fewer comparisons and swaps, reducing the time complexity in such cases.
   
• Low Memory Usage: Insertion sort requires minimal additional memory, making it suitable for systems with limited memory resources, as it sorts in place.
   
• Online Algorithm: Insertion sort can sort a list as it receives it, allowing for dynamic data handling where new elements can be added during the sorting process.

Disadvantages of Insertion Sort Algorithm

• Inefficiency on Large Datasets: Insertion sort has a time complexity of O(n²) in the average and worst cases, making it inefficient for large datasets compared to more advanced sorting algorithms like quicksort or mergesort.
   
• More Comparisons and Swaps: The algorithm may require many comparisons and swaps, leading to longer execution times for larger lists, especially when elements are in reverse order.
   
• Limited Use Cases: While it is effective for small or partially sorted arrays, insertion sort is not suitable for larger datasets, limiting its practical applications in some scenarios.

Applications of Insertion Sort Algorithm

• Small Datasets: Insertion sort is often used for small datasets where its simplicity and efficiency outweigh the drawbacks of its time complexity.
   
• Partially Sorted Data: It is effective for datasets that are already partially sorted, as it can quickly sort them with minimal operations.
   
• Real-Time Systems: Due to its online sorting capability, insertion sort can be used in real-time systems where data is received in a stream and needs immediate sorting.
   
• Adaptive Sorting: In scenarios where elements are frequently added or removed, such as in dynamic data handling, insertion sort can efficiently maintain sorted order.
   
• Sorting Linked Lists: Insertion sort can be particularly efficient for linked lists, as it can easily insert elements without the need for additional memory allocation.
   
• Educational Purposes: Insertion sort is commonly taught in computer science courses to introduce students to basic sorting algorithms and concepts, providing a foundation for understanding more complex algorithms.

Frequently Asked Questions

What is insertion sort steps?

A straightforward sorting algorithm is the insertion sort. Its steps involve repeatedly moving an element from a list's unsorted section to the appropriate spot in the sorted section.

What is the purpose of insertion sorting?

Insertion sorting is used to reorder items in an array into ascending or descending order. It accomplishes this by repeatedly placing elements in the appropriate positions.

What is the difference between selection sort and insertion sort in C?

Selection sort repeatedly selects the smallest element from the unsorted portion and swaps it with the first unsorted element. Insertion sort builds a sorted array by repeatedly inserting the next element into its correct position within the sorted portion.

What is an example of insertion sort?

An example of insertion sort is sorting the array 5,2,9,1,5The algorithm starts with the second element and inserts it into its correct position in the sorted part, resulting in 1,2,5,5,9.

What is the logic of the insertion sorting algorithm? 

The logic of the insertion sort algorithm involves iterating through the array, picking each element and comparing it with the elements in the sorted part. It places the selected element in the correct position by shifting larger elements to the right.

Conclusion

Insertion sort isn’t a particularly efficient algorithm, but it is easy to understand and relatively straightforward to write up. There are a handful of different ways to implement it, and I encourage you to take the tests I provided and try to find a different way to implement it.

In this article, we discussed what Insertion sort is, The algorithm of insertion sort, The working of insertion sort, The implementation of Insertion Sort in C, C++, Java, and Python, and the characteristics of Insertion Sort. 

Recommended Reading - 

• Selection Sort in C
   
• Sorting in Data Structure
   
• Bubble Sort Program in C
   
• Topological sort