Insertion Sort

Introduction

Today, I’m going to be introducing you to a sort algorithm called, Insertion Sort. But for us to get to that, I’m going to tell you a few things about sorting.

What is Sorting?

…is a question my father once asked me. That sure is one good question. I’m sure at least some of you are wondering so, too. 🤔 To answer that question, I’m going to say that sorting is a process of ordering items (arranging things on some basis) or characterizing items (grouping things with similar features).

What do people use sorting for?

Since I already introduced you to sorting, I might as well tell you what you use sorting for. In my last blog, I introduced you to Binary Search. It is a search algorithm that finds an item in a sorted array. Now, have you guessed what people use sorting for? 🤷 I’ll tell you anyway. Sorting is important for the performance of algorithms (such as search algorithms, like Binary Search, and merge algorithms). It is often also useful for creating readable output and canonicalizing data.

Introduction to Insertion Sort

Now that we’ve learned some things about sorting, we’re going to learn about a sort algorithm called, Insertion Sort.

What is Insertion Sort?

In order to learn how to code insertion sort, we first have to know what it is and does. So, According to Wikipedia, Insertion Sort is an uncomplicated sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Yet, insertion sort provides several advantages😄:

1. Simple implementation.
2. It is efficient for (quite) small data sets.
3. It is more efficient in practice than most other simple quadratic algorithms such as bubble sort
4. Adaptive, it is efficient for data sets that are already substantially sorted.
5. Stable; it does not change the relative order of elements with equal keys.
6. In-place; it only requires a constant amount O(1) of additional memory space
7. Online; it can sort a list as it receives it.

What does Insertion Sort do?

“Insertion Sort in Action”

Insertion Sort

Now, we’re going to learn what it does. “What does it do, anyway?” So, what insertion sort basically does is it repeats and develops a sorted list. Each time, it takes in one input element. At each repetition, insertion sort removes one element from the original list. It then finds the correct location in the sorted list and inserts it right there. It repeats again and again until no input elements are left. According to Wikipedia, Sorting is typically done in-place, by iterating up the array, growing the sorted list before it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position.

Here is a video that may help you understand insertion sort better. Take a look if you want to:

Your Task

Your Task: Given an unsorted arr[] of n elements, write a function that sorts the arr using the Insertion Sort algorithm.

Starting at arr[1], compare the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If the value is larger, leave the element in place and move to the next. But if the value is smaller, find the correct position in the sorted list and shift all the larger values up to make a space, and insert it into that position.

Recommended: Please solve it on your own first, before moving on to the solution.

Solution

Here is the solution (Python 3):

def insertion_sort(arr): 
    for i in range(1,len(arr)): 
        x = arr[i]
        j = i
        while j - 1 >= 0 and x < arr[j - 1]: 
            arr[j] = arr[j-1] 
            j -= 1
        arr[j] = x
    return arr

Now, I’m going to create an array/list and check my function:

arr = [10, 6, 3, 2.4, 8, 5, 1, 0, 0.001, 3.1745]
insertion_sort(arr)

Output:

[0, 0.001, 1, 2.4, 3, 3.1745, 5, 6, 8, 10]

Yay!!! My array or list is sorted from least to greatest! So, that means that my function is right! Oh yeah!

Wait… Something just crossed my mind! I’m a bit curious. I don’t know if my function can sort strings, too! Let me experiment! 😊🧪🥼

1. I’m going to create an array of random “strings”:

str_arr = ["manufacture", "monstrous", "hemisphere", "fluctuation", "intervention", "strikebreaker", "prevent", "narrow", "discipline", "spoil"]

2. I’m now going to call my function:

insertion_sort(str_arr)

3. Let’s see the output:

['discipline',
 'fluctuation',
 'hemisphere',
 'intervention',
 'manufacture',
 'monstrous',
 'narrow',
 'prevent',
 'spoil',
 'strikebreaker']

Oh! Okay!!! So, my function can sort arrays with strings, floaters, and even strings!!! Oh, Wow!!! 😲😀

Shell Sort

Visual representation of Shell Sort

D. L. Shell made valuable improvements to the algorithm. The modified version is called Shell Sort. According to Tutorialspoint, Shell sort is a highly efficient sorting algorithm and is based on the insertion sort algorithm. This algorithm avoids large shifts as in the case of insertion sort. If the smaller value is to the far right and has to be moved to the far left.

Start from arr [gap+1]. Compare that number to arr[gap+1-gap]. If you can, float the number up until you cannot. Then, go to arr[gap++] Else, don’t swap anything, and go to arr[gap++] Repeat until you reach the end of the arr. Then, decrease the gap (you can divide the gap in half and that will be the new gap), and do it again. But just make sure the gap, in the end, is 0, which means that it checks two numbers that are just next to each other.

By the way, here are two videos that may help you understand shell sort a bit better:

Another Task

Remember: Start from arr[gap + 1]. Compare that number to arr [gap + 1 -gap]. If you can, float the number up until you cannot. Then, go to arr[gap++] Else, don’t swap anything, and go to arr[gap++] Repeat until you reach the end of the arr. Then, decrease the gap (you can divide the gap in half and that will be the new gap), and do it again. But just make sure the gap, in the end, is 0, which means that it checks two numbers that are just next to each other.

Recommended: Please solve it on your own before going to the solution.

Solution (Python3)

Here’s the solution to the task:

def shell_sort(arr):
    n = len(arr) 
    gap = int(n/2)
    while gap > 0: 
        for i in range(gap,n): 
            temp = arr[i] 
            j = i 
            while j >= gap and arr[j-gap] > temp: 
                arr[j] = arr[j-gap] 
                j -= gap
            arr[j] = temp 
        gap = int(gap/2)
    return arr

Now, to check my function, I’m going to make an array and call it:

arr = [8, 10, 1, 1, 2, 4, 5]
shell_sort(arr)

Output:

[1, 1, 2, 4, 5, 8, 10]

Yay! My array is sorted from least to greatest! That means that my function is correct, again! Woo-hoo!

Sum it up

In conclusion, sorting is a process of ordering items (arranging things on some basis) or characterizing items (grouping things with similar features). Sorting is important for the performance of algorithms (such as search algorithms, like Binary Search, and merge algorithms). It is often also useful for creating readable output and canonicalizing data. Insertion Sort is an uncomplicated sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Yet, insertion sort provides several advantages😄. Insertion sort repeats and develops a sorted list. Each time, it takes in one input element. At each repetition, insertion sort removes one element from the original list. It then finds the correct location in the sorted list and inserts it right there. It repeats again and again until no input elements are left. Sorting is typically done in-place, by iterating up the array, growing the sorted list before it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position. D. L. Shell made substantial improvements to the algorithm. The modified version is called Shell Sort. It’s basically the same thing but it sorts with gaps.