Insertion Sort in Descending Order in Python

1. Introduction

In this blog post, we will learn how to write a Python program to sort an array of integers in a Descending Order using the Insertion Sort algorithm.

Insertion Sort is a straightforward comparison-based sorting algorithm. It builds the final sorted list one item at a time. Think of it like playing cards, where you continuously insert a card among a group of sorted cards. For this guide, we'll focus on sorting in descending order using Python.

2. Program Overview

1. insertion_sort(): The primary function that implements the insertion sort algorithm in descending order.

2. print_list(): A utility function to display the contents of the list.

3. A sample list to test the sorting process.

3. Code Program

def insertion_sort(arr):
    # Traverse from 1 to len(arr)
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        # Move elements of arr[0...i-1], that are
        # smaller 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

def print_list(arr):
    for i in arr:
        print(i, end=" ")
    print()

# Driver code to test the functions
if __name__ == "__main__":
    arr = [64, 34, 25, 12, 22, 11, 90]
    print("Original list is:")
    print_list(arr)

    insertion_sort(arr)

    print("\nSorted list in descending order is:")
    print_list(arr)

Output:

Original list is:
64 34 25 12 22 11 90 

Sorted list in descending order is:
90 64 34 25 22 12 11 

4. Step By Step Explanation

1. insertion_sort(): This function uses the Insertion Sort technique to sort the list in descending order. The logic is to iteratively take one element from the input data, compare it to the elements in the sorted segment of the list, and then insert it in its correct position.

2. print_list(): A helper function to display list elements.

3. Driver code: Demonstrates the functionality using a sample list.

Insertion sort's simplicity makes it a good choice for small lists. Despite its O(n^2) time complexity for the average and worst-case scenarios, it's more efficient in practice compared to other O(n^2) algorithms, like Bubble Sort, for small datasets.