Insertion Sort: A Simple Sorting Algorithm

Introduction

Imagine you have a deck of cards and you want to arrange them in order from smallest to largest. You take one card at a time and place it in its correct position among the already sorted cards. This is exactly how Insertion Sort works! Let’s learn about it step by step.

History

Insertion Sort is one of the simplest and oldest sorting algorithms. It is believed to have been conceptualized by John von Neumann, a brilliant mathematician and computer scientist, while studying sorting methods. Although no exact date is recorded for its invention, it has been around since the early days of computer science.

Time Complexity

Best Case (already sorted list): O(n)
Worst Case (reversed list): O(n²)
Average Case: O(n²)

This means that for small datasets, Insertion Sort works efficiently, but for large datasets, it can be slow compared to other sorting algorithms.

How Does It Work?

The algorithm works by dividing the list into two parts: a sorted part and an unsorted part. It repeatedly picks the first element of the unsorted part and inserts it into the correct position in the sorted part.

Example: Sorting [5, 3, 4, 1, 2]

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

Step 1: Start with the first element

Sorted part: [5]

Step 2: Insert 3 into the sorted part

Compare 3 with 5, and place 3 before 5.
Array: [3, 5]

Step 3: Insert 4

Compare 4 with 5: 4 is smaller.
Compare 4 with 3: 4 is larger.
Place 4 between 3 and 5.
Array: [3, 4, 5]

Step 4: Insert 1

Compare 1 with 5, 4, and 3: 1 is smaller than all.
Place 1 at the start of the sorted part.
Array: [1, 3, 4, 5]

Step 5: Insert 2

Compare 2 with 5, 4, and 3: 2 is smaller than 3 but larger than 1.
Place 2 between 1 and 3.
Array: [1, 2, 3, 4, 5]

Final Sorted Array

[1, 2, 3, 4, 5]

And voila! The list is sorted.

Pseudocode

Here’s the step-by-step logic in pseudocode format:

InsertionSort(array):
    for i from 1 to length(array):
        key = array[i]
        j = i - 1
        while j >= 0 and array[j] > key:
            array[j + 1] = array[j]
            j = j - 1
        array[j + 1] = key

C++ Code

Here’s the C++ implementation:

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

    cout << "Original Array: ";
    printArray(arr, n);

    insertionSort(arr, n);

    cout << "Sorted Array: ";
    printArray(arr, n);

    return 0;
}

Summary

Insertion Sort is a simple algorithm that’s easy to understand and implement. It’s not the fastest for large datasets but works well for small ones. Now that you know how it works, try implementing it yourself with different examples. Happy coding!

GeekJuggernaut