Sorting Algorithms — Insertion Sort

Hi everyone! Welcome to my article on Sorting Algorithms part 4. In this blog, we’ll explore a most commonly used sorting algorithm; Insertion Sort. Let’s dive in!

If you want to know the basics of Sorting Algorithms, you can check out my article on Sorting Algorithms part 1 — Introduction to Sorting Algorithms.

Concept

Insertion Sort is a simple and intuitive comparison-based sorting algorithm. It works similarly to the way you might sort playing cards in your hands. The algorithm builds the final sorted array one item at a time, with each item being placed in its correct position relative to the already sorted items.

Steps

1. Start with the first element, considering it as a sorted sub-array of size one.
2. Take the next element and compare it with elements in the sorted sub-array.
3. Shift elements in the sorted sub-array to the right to create the correct position for the new element.
4. Insert the new element into its correct position.
5. Repeat the process for all elements in the array.

Implementation

Here’s a simple Java implementation of Insertion Sort:

public class InsertionSort {

    // Method to perform Insertion Sort
    public static void insertionSort(int[] array) {
        int n = array.length;
        
        // Loop through each element in the array starting from the second element
        for (int i = 1; i < n; i++) {
            int key = array[i];
            int j = i - 1;
            
            // Move elements of the sorted sub-array that are greater than the key to one position ahead
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j = j - 1;
            }
            // Insert the key at its correct position
            array[j + 1] = key;
        }
    }

    // Main method to test the Insertion Sort
    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6};

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

        // Sort the array using Insertion Sort
        insertionSort(array);

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

Explanation

1. Initialization: The method insertionSort takes an integer array as input.
2. Outer Loop: The outer loop starts from the second element and iterates through the array.
3. Inner Loop: The inner loop compares the current element (key) with elements in the sorted sub-array. It shifts the elements that are greater than the key to the right.
4. Insertion: After finding the correct position, the key is inserted into the sorted sub-array.
5. Main Method: The main method initializes an array, prints it, sorts it using Insertion Sort, and then prints the sorted array.

Complexity of Insertion Sort

Time Complexity

1. Best Case: O(n)

• The best case occurs when the array is already sorted. In this case, the algorithm only makes n−1n-1n−1 comparisons and no shifts.

2. Average Case: O(n²)

• On average, Insertion Sort needs to perform n2/4n²/4n2/4 comparisons and shifts.

3. Worst Case: O(n²)

• The worst case occurs when the array is sorted in reverse order. In this scenario, the algorithm makes n(n−1)/2n(n-1)/2n(n−1)/2 comparisons and shifts.

Space Complexity: O(1)O(1)O(1)

• Insertion Sort is an in-place sorting algorithm, meaning it only requires a constant amount of additional memory space.

Summary

Insertion Sort is an intuitive and simple sorting algorithm that builds a sorted array one element at a time by inserting each new element into its correct position. It is efficient for small datasets or nearly sorted arrays, but it becomes less efficient for larger datasets due to its quadratic time complexity.

I hope this blog has helped you understand the Insertion Sort algorithm, its implementation and its complexity.

Thank you for reading! If you have any questions or feedback, feel free to leave a comment below. Happy coding!