Algorithm Adventures 2: Insertion Sort

… because sometimes you just need to sort things the old-fashioned way.

Last time we hung out with Bubble Sort, the party was… well, let’s just say it was a bit dull.

But fear not, because today we’re getting wild with Insertion Sort! It’s like Bubble Sort’s slightly cooler, more efficient cousin who knows how to have a good time.

Sure, it may not be the fastest or fanciest sorting algorithm out there, but sometimes you just need to keep it simple and sorted. So, grab a drink and let’s see what Insertion Sort is all about!

What is a Insertion Sort?

Insertion Sort is a simple sorting algorithm that is more efficient than Bubble Sort.

It works by iterating through an array and shifting elements to their proper positions one at a time.

While it still has a worst-case time complexity of O(n²), Insertion Sort performs better than Bubble Sort in almost all cases, making it a more practical choice for sorting small to medium-sized arrays.

How it works

Let’s dive into how insertion sort works. Consider the following collection of letters: E, B, D, A, C.

To sort this collection in alphabetical order using insertion sort, we would start by comparing the second element “B” with the first element “E”. Since “B” is smaller than “E”, we swap them, resulting in the collection “B, E, D, A, C”.

Next, we compare the third element “D” with the second element “E”. Since “D” is smaller than “E”, we swap them, resulting in the collection “B, D, E, A, C”.

We continue this process by comparing the fourth element “A” with the third element “E”. Since “A” is smaller than “E”, we swap “A” with “E”, then compare “A” with “D”, “B”, and “C” in order to find the correct position for it.

Finally, we compare the last element “C” with the previous elements and move it to the correct position in the sorted collection. The final sorted collection is “A, B, C, D, E”.

Here is a PHP implementation of insertion sort:

<?php

function insertionSort($arr) {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;

        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j = $j - 1;
        }
        $arr[$j + 1] = $key;
    }
    return $arr;
}

// Example usage
$arr = array(5, 3, 8, 4, 2);
echo "Unsorted array: ";
echo implode(", ", $arr);
echo "\n";

// output
// Unsorted array: 5, 3, 8, 4, 2

$arr = insertionSort($arr);
echo "Sorted array: ";
echo implode(", ", $arr);
echo "\n";

// output
// Sorted array: 2, 3, 4, 5, 8

Insertion sort has a similar worst-case time complexity of O(n²) like bubble sort, which means as the size of the collection grows, the amount of time it takes to sort the collection grows at an exponential rate.

However, in practice, insertion sort can be more efficient than bubble sort for smaller collections because it only requires one swap per element.

Is it usefull?

Well, unlike bubble sort, insertion sort can be quite useful in certain scenarios, particularly when sorting small or partially sorted collections, as its time complexity is slightly better than bubble sort

Insertion sort is also a good algorithm to study for those learning about sorting algorithms, as it provides a clear and intuitive approach to sorting. It is particularly useful for students who are transitioning from simple to more complex algorithms.

For example, it is often used in online sorting where new elements are added to a collection one at a time, and the collection must remain sorted.

However, for larger collections, there are definitely stronger sorting algorithms out there that can do the job faster than you can say “insertion sort”. As we mentioned in a previous article, algorithms like Merge sort and Quicksort are much more efficient in handling larger collections.

What’s next?

In our journey through sorting algorithms, we have covered some of the slowest ones so far. Now, we are approaching the last of the slow sorting algorithms — selection sort.

Once we explore selection sort, we will finally dive into the realm of faster sorting algorithms. These faster algorithms can handle larger collections more efficiently and are widely used in modern computer systems.

Check out other sorting algorithm in this series

Algorithm Adventures 1: Bubble Sort