Insertion Sort Algorithm in Python

In this source code example, we will write a code to implement the Insertion Sort algorithm in Python.

Insertion Sort Algorithm Overview

Insertion sort is a simple sorting algorithm that sorts an array or a list of elements by repeatedly inserting a new element into a partially sorted list until the entire list is sorted. The algorithm works by iterating through the list, comparing each element to the previous one, and swapping them if they are in the wrong order.

Here is the step-by-step process for the insertion sort algorithm:
  1. Start by assuming that the first element of the array is already sorted.
  2. Iterate through the remaining elements of the array from left to right.
  3. For each element, compare it to the elements that come before it in the array, from right to left.
  4. If the element is smaller than the previous element, swap them.
  5. Continue to compare the element to the previous elements until it is in its correct position in the sorted list.
  6. Repeat steps 2 through 5 until the entire list is sorted.
Here is an example of how insertion sort works on the array [5, 2, 4, 6, 1, 3]:
  1. Start with the first element, 5, which is already sorted.
  2. Compare the second element, 2, to the first element, 5. Since 2 is smaller, swap them, giving us [2, 5, 4, 6, 1, 3].
  3. Compare the third element, 4, to the second element, 5. Since 4 is smaller, swap them, giving us [2, 4, 5, 6, 1, 3].
  4. Compare the fourth element, 6, to the third element, 5. Since 6 is larger, we leave it in place.
  5. Compare the fifth element, 1, to the fourth element, 6. Since 1 is smaller, we swap them, giving us [2, 4, 5, 1, 6, 3].
  6. Compare the fifth element, 1, to the third element, 5. Since 1 is smaller, we swap them, giving us [2, 4, 1, 5, 6, 3]. We repeat this process until 1 is in its correct position at the beginning of the list, giving us [1, 2, 4, 5, 6, 3].
  7. Repeat steps 4 through 6 for the sixth element, 3, until the entire list is sorted, giving us [1, 2, 3, 4, 5, 6].

Python Program to Implement Insertion Sort Algorithm

In this Python program, we will take input from the User or console and print the result to the output:
def insertion_sort(collection: list) -> list:
   
    for insert_index, insert_value in enumerate(collection[1:]):
        temp_index = insert_index
        while insert_index >= 0 and insert_value < collection[insert_index]:
            collection[insert_index + 1] = collection[insert_index]
            insert_index -= 1
        if insert_index != temp_index:
            collection[insert_index + 1] = insert_value
    return collection


if __name__ == "__main__":
    user_input = input("Enter numbers separated by a comma:\n").strip()
    unsorted = [int(item) for item in user_input.split(",")]
    print(f"{insertion_sort(unsorted) = }")

Output:

Enter numbers separated by a comma:
20,10,15,5,3,2,1
insertion_sort(unsorted) = [1, 2, 3, 5, 10, 15, 20]
This is a Python code for an implementation of the insertion sort algorithm.

The function insertion_sort() takes a list as its input, performs the insertion sort algorithm on the list, and returns the sorted list. The function has only one parameter, which is a list of unsorted integers.

The insertion sort algorithm is performed using a for loop that iterates over the collection starting from index 1 to the end of the collection. For each iteration, the current value and index are stored in the variables insert_value and insert_index, respectively.

Then, a while loop is used to iterate backward from the current index to the beginning of the collection to find the correct position of the current element. The while loop compares the current element with the elements before it and shifts them from one position to the right until it finds the correct position to insert the current element.

Finally, the sorted list is returned by the function.

The if __name__ == "__main__": block is used to test the insertion_sort() function. It prompts the user to enter a list of integers separated by commas, splits the input string to form a list of integers, and passes the list to the insertion_sort() function. The sorted list is then printed to the console using an f-string.

Related Algorithms in Python