Insertion Sort Algorithm

[qingquan-li]

1. What is Insertion Sort Algorithm

Insertion sort is a simple and intuitive sorting algorithm that works by gradually building a sorted portion within the input array. It is particularly efficient for small or partially sorted datasets. The algorithm functions by iterating through the array, comparing each element to the ones already sorted, and inserting it into the correct position.

In summary, the main steps of the insertion sort algorithm are:

1. Start with the second element in the array, assuming the first element is already sorted.
2. Compare the current element with the elements in the sorted portion, moving from right to left.
3. Shift elements greater than the current element one position to the right.
4. Insert the current element into its correct position in the sorted portion.
5. Repeat steps 2-4 for all elements in the array.

The time complexity of insertion sort is O(n) in the best case, when the array is already sorted, and O(n²) in the worst and average cases. Despite its quadratic time complexity, insertion sort is a good choice for small datasets or when the data is partially sorted, as it minimizes the number of required comparisons and shifts.

2. How it Works

Example: Sort the array "5,2,6,3,1,4" in ascending order using insertion sort.

5	|	2	6	3	1	4
2	5	|	6	3	1	4
2	5	6	|	3	1	4
2	3	5	6	|	1	4
1	2	3	5	6	|	4
1	2	3	4	5	6	|

3. Code for the Insertion Sort Algorithm

InsertionSort.cpp

#include <iostream>

void insertionSort(int array[], int size) {
    // Start iterating from the second element in the array.
    for (int currentIndex = 1; currentIndex < size; currentIndex++) {
        int currentValue = array[currentIndex];
        int sortedIndex = currentIndex - 1;

        // Iterate through the sorted portion from right to left.
        // If the current sorted element is greater than currentValue,
        // shift it one position to the right.
        while (sortedIndex >= 0 && array[sortedIndex] > currentValue) {
            array[sortedIndex + 1] = array[sortedIndex];
            sortedIndex--;
        }

        // Insert the currentValue into the correct position in the sorted portion.
        array[sortedIndex + 1] = currentValue;
    }
}

int main() {
    int array[] = {5, 2, 6, 3, 1, 4};
    // If the array has 6 integer elements and each integer occupies 4 bytes of memory,
    // then sizeof(array) would return 24 bytes (6 elements * 4 bytes per element)
    // and sizeof(array[0]) would return 4 bytes.
    int size = sizeof(array) / sizeof(array[0]);

    insertionSort(array, size);

    for (int i = 0; i < size; i++) {
        std::cout << array[i] << " ";
    }

    return 0;
}

InsertionSort.java

public class InsertionSort {

    // Method to perform insertion sort
    public static void insertionSort(int[] arr) {
        for (int currentIndex = 1; currentIndex < arr.length; currentIndex++) {
            int currentValue = arr[currentIndex];
            int sortedIndex = currentIndex - 1;

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

    // Method to print the array
    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 = {2, 8, 4, 3, 1, 6, 3};
        insertionSort(arr);
        printArray(arr);  // 1 2 3 3 4 6 8 
    }
}

insertion_sort.py

def insertion_sort(arr):
    for current_index in range(1, len(arr)):
        current_value = arr[current_index]
        sorted_index = current_index - 1

        while sorted_index >= 0 and arr[sorted_index] > current_value:
            arr[sorted_index + 1] = arr[sorted_index]
            sorted_index -= 1

        arr[sorted_index + 1] = current_value


A = [2, 8, 4, 3, 1, 6, 3]
insertion_sort(A)
print(A)  # output: [1, 2, 3, 3, 4, 6, 8]

4. Time Complexity

Example: Given array: [5, 4, 3, 2, 1]

						Comparisons
5	|	4	3	2	1	1: (5, 4)
4	5	|	3	2	1	2: (5, 3), (4, 3)
3	4	5	|	2	1	3: (5, 2), (4, 2), (3, 2)
2	3	4	5	|	1	4: (5, 1), (4, 1), (3, 1), (2, 1)
1	2	3	4	5	|

Comparisions are made in this (worst) case is 1 + 2 + 3 + 4 =10.

Comparisions are made in the worst case is: 1 + 2 + 3 + ... + (n - 1). (n is the number of array elements.)

As we know, 1 + 2 + 3 + ... + n = n * (n+1) / 2. So, the formula of the comparisons in the worst case is: (n - 1) * ( n - 1 + 1) / 2 = (n - 1) * n / 2

Using Big-O notation, the worst-case time complexity of insertion sort is:

lim n -> ∞ (n - 1) * n / 2 = lim n -> ∞ (n² -n) / 2 = n²

O(n²)