Python Program for Insertion Sort Algorithm

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:

1. Start by assuming the first element is already sorted
2. Pick the next element (referred to as the “key”) and compare it with the elements in the sorted portion of the array
3. Shift all elements larger than the key to the right to create space
4. Insert the key into its correct position
5. 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:

1. 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.
2. Key Initialization (key = arr[i]): The current element to be inserted into the sorted portion is stored in the variable key.
3. Index Tracking (j = i – 1): “j” points to the last element of the sorted portion, used to compare with the key.
4. 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.
5. 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:

1. 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(n²)
     • Each element must be compared with all previous elements and shifted
   • Average Case: O(n²)
2. Space Complexity:
   • Auxiliary Space: O(1)
     • The algorithm sorts the array in-place without requiring extra memory