Home » Python » Python programs

# Python program for Insertion Sort

**Insertion Sort in Python**: Here, we are going to learn to implement Insertion sort in an array or list in Python.

Submitted by Soumya Sinha, on December 27, 2020

**Insertion Sort**: Insertion sort is a sorting algorithm that works similarly as we sort playing cards in our hands. The input list is divided into two parts: one is a sorted sublist and the other one is an unsorted sublist. Elements from the unsorted sublist are picked up and placed at their correct suitable position.

**Description**:

This algorithm is almost similar to that of selection sort. The only difference is that in selection sort in each iteration we search for the smallest element in the unsorted sublist and swap it with the first element of the unsorted sublist. But in the case of insertion sort, we pick the first element of the unsorted sublist and place it in its correct final position i.e. we sort the first i elements in each iteration of the outer loop.

Here in this algorithm, the input list is divided into two parts (similar to that of selection sort):

- A sorted sublist (built from left to right) of elements starts at the left end of the list.
- An unsorted sublist of elements occupies the rest of the list.

In each iteration, the algorithm will place an unsorted element in its correct position.

**Pseudocode for Insertion Sort:**

Insertion_Sort(arr): n =len(arr) For i=1 to n: key = arr[i] j=i-1 while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] Decrement j by 1 arr[j+1] = key

**Example:**

Consider an array < 12, 41, 76, 17, 25>.

Initially key = arr[1] = 41. Now we will compare the elements which are present to the left of the key. For each and every element which is greater than the key place it just behind the element smaller than it.

As 41 > 21 we won't make any changes here.

<12, 41, 76, 17, 25>

Now key = arr[2] = 76. We will again repeat the same process but this time we won't make any changes as the elements are already placed at their correct position.

<12, 41, 76, 17,25>

Now key = arr[3] = 17.We will again repeat the same process and this time the element 17 needs to be placed in its correct position at index 1 so we will shift the elements one by one to make space.

<12, 41, 76, 76, 25> (for j = 2)

<12, 41, 41, 76, 25> ( for j= 1)

Now place the key in its correct position.

<12, 17, 41, 76, 25>

Repeat the above step for the last element 25 to obtain the sorted list.

key = arr[4] = 25.

<12, 17, 41, 76, 76>

<12, 17, 41, 41, 76>

Now place the key in its correct position.

<12, 17, 25, 41, 76>

We can see that after each iteration first i+1 element is in sorted order.

**Time Complexity**: O(n^2)

## Python code for Insertion Sort

import sys def insertion_sort(arr): # This function will sort the array in non-decreasing order. n = len(arr) # After each iteration first i+1 elements are in sorted order. for i in range(1, n): key = arr[i] j = i-1 # In each iteration shift the elements of arr[0..i-1], # that are greater than key, to one position ahead # of their current position while j >= 0 and key < arr[j]: arr[j+1] = arr[j] j -= 1 arr[j+1] = key return arr # main code if __name__=='__main__': arr = [24, 17, 66, 33, 72, 47, 68, 41, 105, 30] print("Sorted array: ") print(insertion_sort(arr))

**Output:**

Sorted array: [17, 24, 30, 33, 41, 47, 66, 68, 72, 105]

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions