Insertion Sort : An Explanation and Implementation

Insertion Sort is a simple, yet powerful algorithm for sorting data. The algorithm works by taking one element at a time from an unsorted list and inserting it into a sorted list in the correct position. In this article, we will learn how the Insertion Sort algorithm works and its implementation in Python. Refer the below-animated visualization of insertion sort:

Insertion Sort – animation Explanation [Source: Wiki]

How Insertion Sort Works:

The Insertion Sort algorithm works as follows:

Take an unsorted list of n elements.
Pick the first element and insert it into a sorted list.
Take the next element and insert it into the sorted list in the correct position.
Repeat step 3 until all elements have been inserted into the sorted list.

The key to the Insertion Sort algorithm is in step 3. To insert an element into a sorted list, we compare it with the elements already in the sorted list, starting from the rightmost element. If the element is smaller than the element to its left, we swap them. We continue this process until the element is in the correct position.

Step-by-step Explanation of Insertion sort

Let’s take a closer look at how the algorithm works with an example:

Suppose we have an unsorted list [5, 2, 4, 6, 1, 3].
We start by picking the first element, 5, and inserting it into a sorted list [5].
We then take the second element, 2, and compare it with 5. Since 2 is smaller than 5, we swap them, and the sorted list becomes [2, 5].
We then take the third element, 4, and insert it into the sorted list.
We compare 4 with 5 and swap them, giving us [2, 4, 5].
We continue this process until we have a sorted list of all elements.

How to implement insertion sort in Python

def insertionSort(arrayToSort):
    """
    Complexity:
        best    :   O(n)
        average :   O(n^2)
        worst   :   O(n^2)
    parameters:
        arrayToSort: Array to be sorted

    returns:
        sorted array
    """
    for i in range(1, len(arrayToSort)):
        j = i
        while j > 0 and arrayToSort[j] < arrayToSort[j - 1]:
            arrayToSort[j], arrayToSort[j - 1] = arrayToSort[j - 1], arrayToSort[j]
            j -= 1
    return arrayToSort


if __name__ == "__main__":
    array = [2, 5, 1, 5, 8, 9, 0, 10]
    print(insertionSort(array))

Conclusion:

In summary, Insertion Sort is a simple and efficient algorithm for sorting data. It works by inserting each element into a sorted list in the correct position. While Insertion Sort is less efficient than Merge Sort for large datasets, it can be more efficient than Bubble Sort for small datasets. It is important to choose the appropriate sorting algorithm depending on the size of the dataset and the specific use case.

Welcome to the Algo-World

Are you interested in learning about different types of algorithms and how they can be implemented in Python? Are you preparing for technical interviews with companies like Google, Facebook, Amazon, and other top tech companies? Then you’ve come to the right place! Welcome to our new blog on algorithms in Python.

Know more