Algorithm

1. Start with the second element (index 1) of the array.
2. Compare the second element with the first element. If the second element is smaller, swap them.
3. Move to the third element (index 2) and compare it with the elements to its left, moving backward until you find an element smaller than it or reach the beginning of the array.
4. Insert the third element into its correct position.
5. Repeat steps 3-4 for the remaining elements in the array, moving from left to right.
6. The array is now sorted.

Code Examples

#1 Insertion Sort Algorithm implement in Python

Code - Python Programming

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

# Example usage:
my_list = [12, 11, 13, 5, 6]
insertion_sort(my_list)
print("Sorted array:", my_list)
Copy The Code & Try With Live Editor

#2 Insertion Sort Algorithm implement in Java

Code - Java Programming

public class InsertionSort {

    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6};
        
        System.out.println("Original array:");
        printArray(array);

        insertionSort(array);

        System.out.println("\nSorted array:");
        printArray(array);
    }

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

            // Move elements of array[0..i-1] that are greater than key
            // to one position ahead of their current position
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j = j - 1;
            }
            array[j + 1] = key;
        }
    }

    public static void printArray(int[] array) {
        for (int i = 0; i  <  array.length; ++i) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}
Copy The Code & Try With Live Editor

#3 Insertion Sort Algorithm implement in C

Code - C Programming

#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;

        // Move elements of arr[0..i-1] that are greater than key to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

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

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

    printf("Original array: ");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}
Copy The Code & Try With Live Editor

#4 Insertion Sort Algorithm implement in C++

Code - C++ Programming

#include <iostream>
#include <vector>

void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i  <  n; ++i) {
        int key = arr[i];
        int j = i - 1;

        // Move elements of arr[0..i-1] that are greater than key to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6};
    
    std::cout << "Original array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << "\n";

    insertionSort(arr);

    std::cout << "Sorted array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << "\n";

    return 0;
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration

Insertion Sort Data Structure and Algorithm