Insertion Sort in Python

Insertion sort is a sorting algorithm that puts an unsorted element in its proper place in each iteration. In this tutorial, we will perform an Insertion sorting operation to sort an array.

Insertion Sort - A basic Introduction

Insertion sort operates in a similar way to how we sort cards in a card game. We choose an unsorted card since we think the first card is already sorted. If the unsorted card is larger than the one in hand, it goes to the right; otherwise, it goes to the left. Similarly, other unsorted cards are taken and placed in their proper order. Insertion sort takes a similar method.

Let us have a rough understanding of how the Insertion sort operation is performed:

1. The array's initial element is considered to be sorted. Take the second ingredient and put it in a different key.
2. Compare the first element to the key. If the first element is bigger than the key, the first element is put in front of the key.
3. If the element isn't discovered, the return value isn't present.
4. Examine the third element in relation to the ones to its left.
5. It was placed just beneath the element that was smaller than it. Place it at the start of the array if there are no elements smaller than it.
6. Similarly, put each unsorted element in its proper location.

Algorithm of Insertion Sort

As of now, we have a rough understanding of the Insertion sort operation. Let's have a look at the Algorithm followed by code for better understanding:

1. Create a function insetion_sort()
2. Declare a list.
3. Mark the first element as sorted
4. Initialize for loop
5. Iterate each element and extract the locations.
6. Move sorted element right by 1
7. break the loop and insert the key here
8. Print the sorted Array

Python Program of Insertion Sort

As discussed above in the algorithm let us now dive into the programming part of the Insertion sorting operation influenced by the algorithm.

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 = j - 1
            
        # Place key at after the element just smaller than it.
        arr[j + 1] = key

arr = [9, 8, 6, 7, 1]
print("Unsorted Array:", arr)
insertion_sort(arr)
print('Sorted Array: ', arr)

Unsorted Array: [9, 8, 6, 7, 1]
Sorted Array: [1, 6, 7, 8, 9]

Conclusion

In this tutorial, we have performed an Insertion sorting operation in python programming.