Insertion Sort

Insertion sort is an algorithm to sort elements in ascending or descending order.

This approach virtually splits the array into two parts: an sorted array and a unsorted array.

Sorted array contains the element in sorted order. Unsorted array contains the element to be sorted.

The element from an unsorted array is taken one by one and placed or inserted at the correct position in the sorted array. This process is called as insertion sort.

Video Lecture

Insertion Operation

Algorithm

InsertionSort(arr[1]..arr[n])

Input: Array arr contains n elements in unsorted order.

Output: Array arr contains n elements in sorted order.

Step 1: Initially assume arr[1] as sorted array and remaining elements arr[2..n] as unsorted array.

Step 2: Take arr[1] as sorted array.

Step 3: Take value one by one from arr[2] to arr[n] and assign to current value, where i varies from 2 to n.

Step 4: Consider arr[i] as current value & assign current value = arr[i].

Step 5: Compare current value with its predecessor.

Step 6: If the predecessor is greater than the current value, move predecessor to next location in forward direction.

Step 7: If the predecessor is lesser than the current value, insert the current value in the empty location.

Step 8: Repeat steps 3 to 7.

Step 9: Output sorted array.

Working of insertion algorithm - Example

Insertion Sort Code

                    
#include <stdio.h>


    /* Function to sort an array using insertion sort */
    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;
        }
    }
    
    /* Function to print the array */
    void printArray(int arr[], int n) {
        for (int i = 0; i < n; i++)
            printf("%d ", arr[i]);
        printf("\n");
    }
    
    int main() {
        int n;
    
        // Get the size of the array from the user
        printf("Enter the number of elements: ");
        scanf("%d", &n);
    
        // Define the array with a size determined by the user
        int arr[n];
    
        // Get the elements of the array from the user
        printf("Enter the elements of the array:\n");
        for (int i = 0; i < n; i++) {
            scanf("%d", &arr[i]);
        }
    
        // Sorting the array using InsertionSort
        InsertionSort(arr, n);
    
        // Printing the sorted array
        printf("Sorted array: ");
        printArray(arr, n);
    
        return 0;
    }

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

        // 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 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;
}

                    
public class InsertionSort {

    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 main(String[] args) {
        int[] array = {12, 11, 13, 5, 6};

        System.out.println("Original array:");
        for (int i : array) {
            System.out.print(i + " ");
        }

        insertionSort(array);

        System.out.println("\n\nSorted array:");
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

                    
def insertion_sort(arr):
    for i in range(1, len(arr)):
        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 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

def print_array(arr):
    for i in arr:
        print(i, end=" ")
    print()

if __name__ == "__main__":
    arr = [12, 11, 13, 5, 6]
    insertion_sort(arr)
    print("Sorted array:")
    print_array(arr)

Analysis of Insertion Sort

The iterative approach is applied to implement the insertion sort algorithm.

Iterative: The insertion sort algorithm uses a loop to iterate through the array and insert each element into its correct position in the sorted part of the array.

Characteristics of Insertion Sort:

This algorithm is one of the simplest algorithms with a simple implementation.

Basically, insertion sort is efficient for small data values.

Insertion sort is adaptive in nature, i.e., it is appropriate for data sets that are already partially sorted.

Insertion sort is an in-place sorting algorithm.

Time Complexity of Insertion Sort

Complexity Analysis of Insertion Sort:

Time Complexity : O(n^2)

Time Complexity of Insertion Sort:

The worst-case time complexity of the Insertion sort is O(n^2).

The average case time complexity of the Insertion sort is O(n^2).

The time complexity of the best case is O(n).

Space Complexity of Insertion Sort:

The auxiliary space complexity of Insertion Sort is O(1).