Hi everyone! In this article, we’ll guide you through the Python program for insertion sort algorithm. With it’s examples, approach, code, dry run & detailed explanation with complexity analysis.
So, here’s the [Problem Link] to begin with.
Problem Statement of the Python Program for Insertion Sort Algorithm:
The task is to complete the “insertsort()” function which is used to implement Insertion Sort.
Examples:
Example 1:
Input: arr[] = [4, 1, 3, 9, 7]
Output: [1, 3, 4, 7, 9]
Explanation: The sorted array will be [1, 3, 4, 7, 9].
Example 2:
Input: arr[] = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Explanation: The sorted array will be [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].
Example 3:
Input: arr[] = [4, 1, 9]
Output: [1, 4, 9]
Explanation: The sorted array will be [1, 4, 9].
Constraints:
- 1 <= arr.size() <= 1000
- 1 <= arr[i] <= 1000
You might also like our article on Selection Sort Algorithm in Python.
Approach:
Insertion Sort is a simple sorting algorithm that builds the final sorted array one element at a time. It works by dividing the array into a sorted & an unsorted portion.
Each element from the unsorted portion is picked & inserted into the correct position within the sorted portion.
Key Steps in the Approach:
- Start by assuming the first element is already sorted
- Pick the next element (referred to as the “key”) and compare it with the elements in the sorted portion of the array
- Shift all elements larger than the key to the right to create space
- Insert the key into its correct position
- Repeat this process for all elements in the array
Code:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
Code Explanation:
- Outer Loop (for i in range(1, len(arr))): Iterates through the array starting from the second element (index 1), as the first element is assumed to be sorted.
- Key Initialization (key = arr[i]): The current element to be inserted into the sorted portion is stored in the variable key.
- Index Tracking (j = i – 1): “j” points to the last element of the sorted portion, used to compare with the key.
- Inner While Loop (while j >= 0 and arr[j] > key):
- This loop shifts elements in the sorted portion to the right as long as they are greater than the key.
- The loop terminates when j < 0 or when an element smaller than or equal to the key is found.
- Element Insertion (arr[j + 1] = key): Once the correct position for the key is found, it is placed in that position.
Also learn Bubble Sort Algorithm in Python.
Dry Run:
Let’s perform a dry run of the insertion sort algorithm using the list of integers nums = [10, 18, 8, 20, 21, 9]. The process will be explained step by step through images to provide a clear and detailed understanding of how insertion sort works.
Complexity Analysis:
- Time Complexity:
- Best Case (Already Sorted Array): O(n)
- The inner loop does not execute since no shifting is needed
- Worst Case (Reverse Order Array): O(n2)
- Each element must be compared with all previous elements and shifted
- Average Case: O(n2)
- Best Case (Already Sorted Array): O(n)
- Space Complexity:
- Auxiliary Space: O(1)
- The algorithm sorts the array in-place without requiring extra memory
- Auxiliary Space: O(1)