Python Program for Insertion Sort

Last Updated on October 18, 2023 by Ankit Kochar

Insertion sort in Python stands as a straightforward sorting algorithm where, in each iteration, a newly introduced element finds its appropriate sorted position. This algorithm demonstrates remarkable efficiency when applied to smaller arrays.

What is Insertion Sort?

The insertion sort algorithm operates by repeatedly choosing an unsorted element from the array and inserting it into its correct position within the already sorted portion of the array.

For example, if we have a list of employee names in the unsorted order. Let’s see how to sort that list using the insertion sort algorithm. First, you could start by considering the first employee name as being sorted, and then comparing each subsequent employee name to the employee names already considered sorted, shifting employee names as necessary to make room for the new employee name, until the new employee name is in its proper place in the sorted list. You would repeat this process for each employee’s name in the list until all the employee names are sorted and in the correct order. This process is similar to the way insertion sort works for sorting an array, as it repeatedly selects an element and inserts it into the correct position relative to the elements before it.

Working of the Insertion Sort with an Example

Let’s take an example to understand the insertion sort algorithm.

arr = [40, 30, 50, 10, 20]

We will consider the above example and see how the insertion sort algorithm works.

First pass:
We will consider the first element of the array to be sorted and compare the first element with the second element.

In this case, the first element 40 is greater than the second element 30 so 30 is not at its correct position. Now, we will swap 40 and 30.

In this array, 30 is a part of the sorted sub-array.

Second pass:
In this pass, we will move one step ahead and compare the next two elements. We will compare the second element 40 and the third element 50.

In this case, the third element 50 is already greater than the second element 40 so we will not perform any swap. Now, the second element 40 is also part of the sorted sub-array.

Third pass:
In this pass, we will move one step ahead and compare the next two elements. We will compare the third element 50 and the fourth element 10.

Here, 50 and 10 are not at its the right position, Thus, we will swap both the elements.

After performing the swap, we will compare 10 with 40 and they are also not at its right position. So we will swap both the elements.

Now, we will compare 10 and 30 and we can see that they are not in the correct position. Thus, we will swap both the elements.

In this array, we can see that 10 is at its correct position.

Fourth pass:
In this pass, we will move one step ahead and compare the next two elements. We will compare the fourth element 50 and the fifth element 20.

Here, 50 and 20 are not at its the right position, Thus, we will swap both the elements.

After performing the swap, we will compare 20 with 40 and they are also not at its right position. So we will swap both the elements.

Now, we will compare 20 and 30 and we can see that they are not in the correct position. Thus, we will swap both the elements.

Now, we can see that the array is sorted.

Algorithm of the Insertion Sort:

Below is the algorithm of the insertion sort.

insertion_sort(array):
    for i from 1 to length(array) - 1:
        j = i
        while j > 0 and array[j-1] > array[j]:
            swap(array[j], array[j-1])
            j = j - 1
    return array

Explanation of the above pseudo-code:

• The function insertion_sort(array) takes an array as its input.
• The outer loop for i from 1 to length(array) – 1 iterate over each element in the array starting from the second element. The purpose of this loop is to select an unsorted element from the array and insert it into its correct position in the sorted portion of the array.
• The inner while loop performs the insertion and shifting of elements in the sorted portion of the array. The loop starts with the j variable being set to the current value of i.
• The condition while j > 0 and array[j-1] > array[j] checks if j is greater than 0 and if the element array[j-1] is greater than array[j]. If this condition is true, it means that the current element is not in its correct position in the sorted portion of the array, and it needs to be inserted.
• The swap(array[j], array[j-1]) function swaps the current element array[j] with the previous element array[j-1]. This shifts the previous element one position to the right, making room for the current element to be inserted.
• The j variable is decremented by 1 using j = j – 1. This allows the inner loop to continue checking the previous elements in the sorted portion of the array until the current element is in its correct position.
• The inner loop continues until the condition while j > 0 and array[j-1] > array[j] is false, indicating that the current element is in its correct position in the sorted portion of the array.
• The outer loop continues until all elements in the unsorted portion of the array have been inserted into their correct positions in the sorted portion of the array.
• The sorted array is returned as the result of the function insertion_sort(array)

Insertion Sort Python Program

Now, we will learn how to write the insertion sort python program.

# insertion sort python program

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

array = [40, 30, 50, 10, 20]
print("Array before the Insertion Sort :", array)

sorted_array = insertion_sort(array)

print("Array after the Insertion Sort :", sorted_array)

Output:

Array before the Insertion Sort : [40, 30, 50, 10, 20]
Array after the Insertion Sort : [10, 20, 30, 40, 50]

In the above insertion sort python code, we have taken an unsorted array. After that, we have sorted that array using the insertion sort python function. In the output, we can see that after performing the insertion sort array is sorted.

Time Complexity: O(n^2)
Space Complexity: O(1)

Conclusion:
In conclusion, the Python program for insertion sort is a fundamental sorting algorithm that efficiently organizes an array by repeatedly selecting unsorted elements and placing them in their proper positions within the sorted part of the array. It is a valuable tool for sorting data and can be implemented easily in Python or other programming languages.

FAQs Related to Insertion Sort in Python

Some of the FAQs related to Insertion Sort in Python are discussed below:

1. What is the time complexity of the insertion sort algorithm in Python?
The time complexity of the insertion sort algorithm is O(n^2) in the worst and average cases, where "n" represents the number of elements in the array. In the best case (when the array is already sorted), the time complexity is O(n).

2. Can insertion sort be used for sorting large datasets efficiently?
Insertion sort is most efficient for small to moderately sized datasets. For large datasets, more advanced sorting algorithms like quicksort or mergesort are generally preferred due to their better performance characteristics.

3. How do I implement the insertion sort algorithm in Python?
You can implement the insertion sort algorithm in Python using a simple loop that iterates through the array and repeatedly swaps elements until the array is sorted. There are many online resources and tutorials available to guide you through the implementation process.

4. Is insertion sort a stable sorting algorithm?
Yes, insertion sort is considered a stable sorting algorithm. This means that it maintains the relative order of equal elements in the sorted array.

5. What are the advantages of using insertion sort in Python?
Insertion sort is relatively easy to understand and implement. It performs well on small datasets or nearly sorted arrays. It also has low memory overhead compared to some other sorting algorithms.