Insertion Sort in Python

Insertion Sort Algorithm

Let us look at the algorithm of Insertion sort.

1. Take an unsorted list with ‘n’ elements.

2. Divide the list into two parts. Start with marking the input array's first element as the sorted part's only element. The other list elements are part of the unsorted array.

3. Now, add other elements to the sorted array one by one. Start by adding the following element to the sorted list.

4. Compare the new element with each element of the left part of the list one by one from right to left. Wherever an element is found smaller than the current element, place the current element to the right of it. Also, push other elements of the left part of the list greater than the current element to the right by one position each. This way, the current element is in its correct position for the list's left-side (sorted) part. 

It can be viewed as follows:

for i from (1,n):
	j=i-1;
	while(arr[j]> arr[i] and j>=0):
		arr[j+1]=arr[j];
		j=j-1;
	arr[j+1]=arr[i]; 

You can also try this code with Online Python Compiler

Run Code

5. Repeat steps 2, 3 and 4 until each list element is traversed and positioned correctly. The final list is the sorted list of elements of the input array. 

Let's understand with an example.

Example of Insertion Sort Algorithm

Suppose we have a list as follows:

[9, 4, 2, 3, 7]

Here, we denote elements with three colors as follows:

We can sort this array using Insertion Sort using the above-mentioned algorithm.

• While iterating through the array, ‘i’ will represent the index of the current element.
   
• ‘j’ will represent the index of the element just smaller than the current element. In case, there is no such element, ‘j’ will stop at position -1.
   

First, we make the first element as part of the sorted array.

After making the first element as the only element of the sorted part of the list, the list will be as follows:

Now, we will add the second element to the sorted part. For this, ‘j’ points to position ‘-1’ so, we have to swap the first and second elements. Swap a[j+1] and a[i].

Hence, the array will be as follows:

Now, we will add the third element to the sorted array. For this, ‘j’ points to position ‘-1’ so, we must push '4' and '9' to the right by one position and insert '2' at the first position.

Hence, the array will be as follows:

Now, we will add '3' to the sorted array. For this, ‘j’ points to position ‘0’ so, we must push 4 and 9 to the right by one position and insert '3' after '2'.

Hence, the array will be as follows:

Now, we will add '7' to the sorted array. For this, ‘j’ points to position ‘2’ so, we must push '9' to the right by one position and insert '7' after '4', i.e., swap '9' and '7'.

Finally, we have the sorted array as follows:

Implementation

Let us now see the implementation of Insertion sort in Python.

def insertion_sort(nums):
    for i in range(1,len(nums)):
        curr=nums[i]
        j=i-1
        while nums[j]>curr and j>=0:
            nums[j+1]=nums[j]
            j-=1
        nums[j+1]=curr

nums=[]
n=int(input("Enter the number of elements: "))
print("Enter elements of the array: ")
for i in range(0,n):
    x=int(input())
    nums.append(x)

print("Original array: ")
print(nums)
insertion_sort(nums)
print("Sorted array: ")
print(nums)

You can also try this code with Online Python Compiler

Run Code

Output: 
As we can see, we took the input array which was unsorted, and we got an output array as a sorted one using insertion sort in Python.

Explanation

In this code, we use two nested ‘for’ loops for sorting.

• The first loop iterates over each element of the array linearly.
   
• The second loop searches for the element in the sorted part of the array which is just smaller than the current element. Then, the current element is placed right after it, and all the other elements in the sorted part which are greater than the current element shift to the right by one position.

Time Complexity

Since we have two nested ‘for’ loops running in the program, the time complexity of insertion sort for:

1. Worst case:- O(n²)
    
2. Average case:- O(n²) 
    
3. Best case:- O(n)

The worst-case time complexity of the Insertion sort is O(n²) because the worst case is when the list is sorted in reverse order. Hence, two nested ‘for’ loops run for each element, and the complexity increases.

Similarly, try to think of the reason for the time complexity of the best case to be O(n). We will discuss its reason at the end of this article.

Space Complexity

Since we only use one extra variable for sorting in Insertion sort, and if we exclude the space required for the input array, the space complexity of Insertion sort is O(1).

Advantages of Insertion Sort

There are certain advantages of Insertion Sort as follows:

• Being an in-place sorting algorithm, the extra memory required for this algorithm is minimal.
   
• This technique is a simple sorting algorithm that performs well when we apply it to small lists.
   
• It maintains the relative order of elements with the same value in the input and final sorted list. Hence, it is a stable sorting algorithm.

Disadvantages of Insertion Sort

There are some disadvantages of the Insertion sort as follows:

• Its worst-case time complexity is O(n²) which is not good compared to other sorting algorithms like merge sort.
   
• It does not cope well with large data sets. It is only efficient for small data sets.
   
• It does not perform well as some other sorting techniques like quicksort, merge sort, and heap sort for larger data sets.

Frequently Asked Questions

What is insertion sort Python?

Insertion sort in Python is a comparison-based sorting algorithm that iterates through a list, taking one element at a time and placing it in its correct sorted position within the list, making it suitable for small data sets due to its O(n^2) time complexity.

How does insertion sort works?

Insertion sort iterates through a list, taking one element at a time and inserting it into its proper sorted position within the list, shifting larger elements to make space. It repeats this process until the entire list is sorted.

What is the insertion sort algorithm for strings?

Insertion sort for strings is a simple sorting algorithm that arranges an array of strings in ascending order. It iterates through the array, comparing and inserting each string in its correct position within the sorted portion of the array.

Conclusion

Sorting algorithms are widely used in programming. These algorithms are a must for solving a significant portion of problems. Insertion sort is a practical and beneficial algorithm. In this article, we have studied Insertion sort in Python, its algorithm, implementation, time and space complexity, features, and limitations.

Now, let us discuss why the best-case time complexity of the Insertion sort is O(n). It is such because the best case is when the list is already sorted. Hence, each element will only be visited once.

Recommended Readings:

• Convert String to List Python
• Insertion Sort Algorithm
• Binary Insertion Sort
• Insertion Sort for Singly Linked List
• How to Implement Quick Sort in Python?