Insertion Sort: The Hermit Crab way

Picture a beach where a group of hermit crabs are searching for their perfect shells. Each crab carefully checks where they belong and inserts themselves in just the right spot. In the world of algorithms, this process is known as Insertion Sort.

In this article, we’ll explore how Insertion Sort works by gradually sorting elements, one step at a time, just like hermit crabs finding their place. By the end, you’ll be an expert at this smooth sorting technique and ready to tackle some interesting challenges!

Simple Insertion Sort – The Hermit Crabs' Approach

Insertion Sort 101 – Sorting One by One

Insertion Sort works by building a sorted list, one element at a time. Like how a hermit crab slowly inserts itself into the perfect shell, this algorithm takes each element and compares it with the ones before it, inserting it into the correct position.

Step-by-Step Example with Code

Let’s take a list of hermit crabs’ shell sizes: [8, 4, 9, 3, 6].

First Crab (4):
The first crab (size 8) is already sorted, so the second crab (size 4) compares itself with 8. Since 4 is smaller, it inserts itself before 8.
List becomes: [4, 8, 9, 3, 6]
Second Crab (9):
The next crab (size 9) compares itself with the crabs before it. Since 9 is larger than both 4 and 8, it stays in its current position.
List remains: [4, 8, 9, 3, 6]
Third Crab (3):
The crab with shell size 3 checks all crabs before it: 9, 8, and 4. Since 3 is smaller than all of them, it shifts them right and inserts itself at the start.
List becomes: [3, 4, 8, 9, 6]
Fourth Crab (6):
The crab with shell size 6 compares itself with 9, 8, and 4. Since 6 is larger than 4 but smaller than 8, it inserts itself between 4 and 8.
List becomes: [3, 4, 6, 8, 9]

Now all the hermit crabs are perfectly sorted in their ideal order!

Code Snippets for Simple Insertion Sort

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
    return arr

# Example usage
shell_sizes = [8, 4, 9, 3, 6]
print(insertion_sort(shell_sizes))

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

// Example usage
let shellSizes = [8, 4, 9, 3, 6];
console.log(insertionSort(shellSizes));

#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;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int shellSizes[] = {8, 4, 9, 3, 6};
    int n = sizeof(shellSizes) / sizeof(shellSizes[0]);
    insertionSort(shellSizes, n);
    for (int i = 0; i < n; i++)
        cout << shellSizes[i] << " ";
    return 0;
}

Optimized Insertion Sort – Faster Hermit Crabs

Optimizing Insertion Sort with a Binary Search

For larger datasets, Insertion Sort can be made faster by using binary search to find the correct insertion point instead of linearly checking each element. This minimizes the number of comparisons needed to find the right spot.

Let’s see how this optimization works with the list [8, 4, 9, 3, 6]:

First Crab (4): Binary search finds the correct position for 4, which is before 8, so 4 is inserted before 8.
List becomes: [4, 8, 9, 3, 6]
Second Crab (9): Binary search determines that 9 is already in the correct spot.
List remains: [4, 8, 9, 3, 6]
Third Crab (3): Binary search finds that 3 should be placed at the start of the list.
List becomes: [3, 4, 8, 9, 6]
Fourth Crab (6): Binary search finds that 6 belongs between 4 and 8.
List becomes: [3, 4, 6, 8, 9]

Python Code for Optimized Insertion Sort (with Binary Search):

def binary_search(arr, val, start, end):
    if start == end:
        if arr[start] > val:
            return start
        else:
            return start + 1
    if start > end:
        return start
    mid = (start + end) // 2
    if arr[mid] < val:
        return binary_search(arr, val, mid + 1, end)
    elif arr[mid] > val:
        return binary_search(arr, val, start, mid - 1)
    else:
        return mid

def insertion_sort_optimized(arr):
    for i in range(1, len(arr)):
        val = arr[i]
        j = binary_search(arr, val, 0, i - 1)
        arr = arr[:j] + [val] + arr[j:i] + arr[i+1:]
    return arr

Time and Space Complexity – How Efficient is Insertion Sort?

Time Complexity:

Worst Case (O(n²)): When the list is in reverse order, each hermit crab has to compare itself with every other crab, leading to a quadratic number of comparisons.
Best Case (O(n)): If the list is already sorted, Insertion Sort only needs to compare each element once.

Space Complexity:

Space Complexity (O(1)): Insertion Sort only needs a small amount of extra space for storing the key while shifting elements, making it space-efficient.

Drawbacks and Real-World Applications

Drawbacks of Insertion Sort

Inefficiency for Large Datasets: Due to its O(n²) worst-case time complexity, Insertion Sort is not ideal for large datasets.
More Comparisons: Without optimization, the number of comparisons can become excessive for larger lists.

Real-World Applications of Insertion Sort

Small or Nearly Sorted Data: Insertion Sort works exceptionally well on small datasets or those that are nearly sorted.
Online Algorithms: Insertion Sort is great for online algorithms where data arrives piece by piece and needs to be sorted incrementally.

Challenge Time – Test Your Skills!

Challenge: Sorting Sea Shells
You’re organizing seashells by size. Use Insertion Sort to arrange them: [8, 4, 9, 3, 6].
Challenge: Organizing Inventory
You’re managing a small inventory system for a beach store. Use Insertion Sort to organize the item prices: [12, 9, 20, 5, 18].

Think you’ve mastered Insertion Sort? Try out the challenges and share your solutions!

Conclusion: The Hermit Crabs Have Mastered Insertion Sort!

With careful steps and optimized comparisons, the hermit crabs have taught us the beauty of Insertion Sort. You’ve learned how to implement, optimize, and apply this algorithm, and now you’re ready for your next sorting adventure.

Ready for the next sorting algorithm? Subscribe and get notified when we tackle Selection Sort!

The Hermit Crab's Line-Up

Table of contents