Write a Program to Perform Insertion Sort in Python

Introduction

Insertion sort is one of the sort techniques for sorting array-based data. The name insertion is because it inserts the smallest element at the right position in each iteration by comparing it with the data before it(opposite case for the descending order). In this tutorial, you'll learn how to perform insertion sort in python.

How Insertion Sort Works

Step 1

Step 2

Step 3

Algorithm for Insertion Sort

length = Length of the Array
for i in (1 to length - 1)
    item = array[i]
    j = i - 1
    # For desecding order: change '<' to '>'
    while j >= 0 and (item < array[j])
        array[j+1] = array[j]
        j = j - 1
    array[j+1] = item

Code

'''Write a program for insertion sort in python'''
def InsertionSort(array):
    for i in range(1, len(array)):
        item = array[i]
        j = i - 1
        while j >= 0 and (item < array[j]):
            array[j+1] = array[j]
            j -= 1
        array[j+1] = item
# The main function
if __name__ == "__main__":
    arr = [7, 8, 5, 2, 3]
    InsertionSort(arr)
    print("----The Sorted data----")
    print(arr)

Output

----The Sorted data----
[2, 3, 5, 7, 8]

Insertion Sort with user input

Code

'''Program for insertion sort in python with user input'''
def InsertionSort(array):
    for i in range(1, len(array)):
        item = array[i]
        j = i - 1
        while j >= 0 and (item < array[j]):
            array[j+1] = array[j]
            j -= 1
        array[j+1] = item
# The main function
if __name__ == "__main__":
    arr = input("Enter the array data, separated by a comma: ").split(',')
    arr = [int(i) for i in arr]
    InsertionSort(arr)
    print("----The Sorted data----")
    print(arr)

Output

Enter the array data, separated by a comma: 7, 8, 5, 2, 3
----The Sorted data----
[2, 3, 5, 7, 8]

Complexity analysis

There are three conditions the array may have: In ascending order, descending order, or random order. The worst and average case occurs when the array of data is in descending or random order, and the best case occurs when the array is already sorted.

Time Complexity

Worst Case: O(n^2)

Average Case: O(n^2)

Best Case: O(n)

Space Complexity

For all conditions: O(1)