Python Program to Implement Insertion Sort

Insertion Sort in Python is basically the insertion of an element from a random set of numbers, to its correct position where it should actually be, by shifting the other elements if required.

Write a Python program to sort a list by using insertion sort.

function insertion_sort(arr):
    for i in range(1, length(arr)):
        key = arr[i]
        j = i - 1
 
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j = j - 1
 
        arr[j + 1] = key

The insertion_sort function takes an array as input and performs the insertion sort algorithm. It starts iterating from the second element (i = 1) and compares it with the elements in the sorted portion (j = i – 1) from right to left. If an element is greater than the key, it is shifted one position to the right. Finally, the key is inserted into its correct position within the sorted portion.

Here’s a step-by-step example of how the Insertion Sort algorithm works on the list [2, 4, 1, 5, 8, 0]:

• Step 1: Initial state: [2, 4, 1, 5, 8, 0]
• Step 2: Start with the second element (4) and compare it with the first element (2). Since 4 is greater, no swap is needed.
  State: [2, 4, 1, 5, 8, 0]
• Step 3: Move to the next unsorted element (1). Compare it with the sorted portion (2, 4) and insert it in the correct position.
  State: [1, 2, 4, 5, 8, 0]
• Step 4: Repeat the process for the next unsorted element (5).
  State: [1, 2, 4, 5, 8, 0]
• Step 5: Repeat the process for the next unsorted element (8).
  State: [1, 2, 4, 5, 8, 0]
• Step 6: Repeat the process for the next unsorted element (0). Compare it with the sorted portion (1, 2, 4, 5, 8) and insert it in the correct position.
  State: [0, 1, 2, 4, 5, 8]
• Step 7: The entire list is now sorted: [0, 1, 2, 4, 5, 8].

By iteratively considering one element at a time and inserting it into the correct position within the sorted portion of the list, the Insertion Sort algorithm gradually builds a sorted list.

Here is the source code of a Python program to implement insertion sort. The program output is shown below.

def insertion_sort(alist):
    for i in range(1, len(alist)):
        temp = alist[i]
        j = i - 1
        while (j >= 0 and temp < alist[j]):
            alist[j + 1] = alist[j]
            j = j - 1
        alist[j + 1] = temp
 
 
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
insertion_sort(alist)
print('Sorted list: ', end='')
print(alist)

1. Define the function insertion_sort that takes a list (alist) as input.
2. Start a loop that iterates from the second element (i = 1) to the end of the list (len(alist)).
3. Assign the value of the current element to a temporary variable (temp).
4. Set the initial index for comparison as the previous element (j = i – 1).
5. Enter a nested loop that continues while the index is greater than or equal to 0 and the temporary value is less than the element at the current index (temp < alist[j]).
6. Within the nested loop, shift the element at the current index one position to the right (alist[j + 1] = alist[j]).
7. Decrement the index by 1 (j = j – 1).
8. After exiting the nested loop, insert the temporary value into its correct position in the sorted portion of the list (alist[j + 1] = temp).
9. Outside the function, prompt the user to enter a list of numbers, which are stored as a string and split into individual elements.
10. Convert the elements from strings to integers using a list comprehension.
11. Call the insertion_sort function, passing the converted list as an argument.
12. Print the sorted list.

Time Complexity: O(n²)
The time complexity of the code is O(n²), where n is the number of elements in the input list.

Space Complexity: O(1)
The space complexity is O(1) since it uses a constant amount of additional space.

Testcase 1: Here, the elements are entered in random order.

 
Enter the list of numbers: 2 4 1 5 8 0
Sorted list: [0, 1, 2, 4, 5, 8]

Testcase 2: In this scenario, the elements are entered in reverse sorted order.

Enter the list of numbers: 5 4 3 2 0 -1
Sorted list: [-1, 0, 2, 3, 4, 5]

Testcase 3: In this case, the user enters the list of numbers as “3 4 1 4 5 0 7”, and the program will output:

Enter the list of numbers: 3 4 1 4 5 0 7
Sorted list: [0, 1, 3, 4, 4, 5, 7]

To practice programs on every topic in Python, please visit “Programming Examples in Python”.