Posted on Jan 9, 2025 | Coding

Insertion Sort

Introduction

Insertion Sort is a sorting algorithm which process one element at a time, ensuring that elements encountered before the current element are already sorted i.e. you are inserting element in a sorted array.
Let's take example of a card game, you pick one card at a time, placing each card in its correct position according to already sorted cards in your hand.

Complexity

Best Case Time Complexity: O(n) (when the array is already sorted)
Average Case Time Complexity: O(n²)
Worst Case Time Complexity: O(n²)
Space Complexity: O(1) (in-place sorting)

Algorithm Steps

Begin with the second element of the array, treating the first element as a sorted subarray.
Compare the current element with the elements in the sorted subarray.
Shift the elements in the sorted subarray that are greater than the current element to one position to the right.
Insert the current element into its correct position in the sorted subarray.
Repeat steps 2 to 4 for all elements until the entire array is sorted.

Example

Let's take an example of array whose elements are:[5][3][8][4][2]

Pass 1:

Current element: 3.
Compare Current element to all elements left of it until you find element that is smaller than Current element.
Since, 3<5, shift 5 one position to the right.
- Current array: [_][5][8][4][2].
Since, there are no more elements to compare, insert Current element at the blank space.
Array after Pass 1: [3][5][8][4][2].

Pass 2:

Current element: 8.
Compare Current element to all elements left of it until you find element that is smaller than Current element.
Since, 8>5, we will stop the shifting process.
- Current array: [3][5][8][4][2].
Array after Pass 2: [3][5][8][4][2].

Pass 3:

Current element: 4
Compare Current element to all elements left of it until you find element that is smaller than Current element.
Since, 4<8, shift 8 one position to the right.
- Current array: [3][5][_][8][2].
Since, 4<5, shift 5 one position to the right.
- Current array: [3][_][5][8][2].
Since, 4>3, we will stop the shifting process.
-Current array: [3][_][5][8][2].
Insert Current element at the blank space.
Array after Pass 3: [3][4][5][8][2].

Pass 4:

Current element: 2
Compare Current element to all elements left of it until you find element that is smaller than Current element.
Since, 2<8, shift 8 one position to the right.
- Current array: [3][4][5][_][8].
Since, 2<5, shift 5 one position to the right.
- Current array: [3][4][_][5][8].
Since, 2<4, shift 4 one position to the right.
- Current array: [3][_][4][5][8].
Since, 2<3, shift 3 one position to the right.
- Current array: [_][3][4][5][8].
Since, there are no more elements to compare, insert Current element at the blank space.
Array after Pass 4: [2][3][4][5][8].

Final Sorted Array: [2][3][4][5][8].

Key Observations

Comparisons: Each element is compared to the previous elements in the sorted subarray until the correct position is found.
Shifting: Elements greater than the current element are shifted one position to the right to create space for the insertion.
Insertion: The current element is placed in its correct position in the sorted subarray.
Adaptive Nature: The algorithm takes advantage of already sorted subarrays, reducing the number of comparisons and shifts.
Stability: Insertion sort maintains the relative order of elements with equal keys, making it a stable sorting algorithm.

Advantages

Easy to grasp and implement.
Performs well with small data sets or those that are already mostly sorted.
Takes advantage of existing order in the data, achieving nearly linear time complexity in the best-case scenario.
Maintains the relative order of equal elements, which is crucial for certain applications.

Disadvantages

With an average and worst-case time complexity of O(n^2), it’s not suitable for large lists.
Involves more element movements compared to some other algorithms, potentially decreasing the lifespan of elements in systems with limited write cycles.

Code in C:

#include<stdio.h>
void main(){
     int arr[100]; // consider the size of an array  100
     int n;
     printf("Enter the number of elements:\n");
     scanf("%d",&n); 
     printf("Enter the elements of the array:\n");
     for(int i=0; i<n; i++){
         scanf("%d",&arr[i]);
     }
     
     // printing unsorted array--
        printf("unsorted array: ");
        for(int i=0; i<n; i++){
            printf("%d",arr[i]);
        }
        
        // Insertion Sort
       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;
    }
       
       // Sorted array-
        printf("Sorted array: ");
        for(int i=0; i<n; i++){
            printf("%d",arr[i]);
        }
}

Code in C++:

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cout << "Enter the number of elements: "<<endl;
    cin >> n;
    int arr[n];
    cout << "Enter the elements of the array: "<<endl;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "unsorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    // Insertion Sort
    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;
    }
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

Code in Java:

import java.util.Scanner;

class Solution{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in); // for scanning the input
        System.out.println("Enter the number of elements:");
        int n = sc.nextInt();
        
        // initialize the array--
        int[] arr = new int[n];
        
        System.out.println("Enter the elements:");
        for(int i = 0; i<n; i++){
            arr[i] = sc.nextInt;
        }
        
        // printing unsorted array--
        System.out.print("unsorted array: ");
        for(int i=0; i<n; i++){
            System.out.print(arr[i]+" ");
        }
        
        // Insertion sort--
        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;
        }
        
        // printing sorted array--
        System.out.print("Sorted array: ");
        for(int i=0; i<n; i++){
            System.out.print(arr[i]+" ");
        }
    }
}

Output

Enter the number of elements: 
5
Enter the elements of the array: 
5 3 8 4 2
unsorted array: 5 3 8 4 2 
Sorted array: 2 3 4 5 8

More on Sorting:

5 Reactions

1 Bookmarks