Insertion Sort Program in Python

Python - Insertion Sort

In this tutorial, we will implement the Insertion Sort Algorithm in Python. Insertion Sort is a simple and efficient sorting algorithm that builds the final sorted list one item at a time. It is much like sorting playing cards in your hands.

The algorithm works by taking each element from the unsorted portion and inserting it into its correct position in the sorted portion of the list.

Insertion Sort Algorithm

The algorithm for Insertion Sort is as follows:

  1. Start with the second element of the list (the first element is already sorted).
  2. Compare the current element with the element in the sorted portion of the list (the elements before the current element).
  3. If the current element is smaller than the element in the sorted portion, shift the larger elements to the right to make space for the current element.
  4. Insert the current element in the correct position in the sorted portion.
  5. Repeat the process until the entire list is sorted.

Python Program

def insertion_sort(nlist):
    for i in range(1, len(nlist)):
        current_element = nlist[i]
        j = i - 1
        while j >= 0 and current_element < nlist[j]:
            nlist[j + 1] = nlist[j]
            j -= 1
        nlist[j + 1] = current_element

#input list
alist = [12, 11, 13, 5, 6]
print('Input List\n', alist)

#sort list
insertion_sort(alist)
print('Sorted List\n', alist)

Explanation:

  1. The outer loop starts from the second element and iterates over the entire list.
  2. For each element, the program compares it with the elements before it (in the sorted portion) using a while loop.
  3. If the current element is smaller than the elements before it, the program shifts the larger elements one position to the right.
  4. Finally, the current element is inserted in its correct position.

Output

Input List
 [12, 11, 13, 5, 6]
Sorted List
 [5, 6, 11, 12, 13]

Optimizing Insertion Sort

Although Insertion Sort is an efficient algorithm for small datasets, it has a time complexity of O(n^2) in the worst case. However, we can optimize the algorithm to stop early if the list is already partially sorted by detecting when no shifting is required during an iteration.

Optimized Python Program

def insertion_sort(nlist):
    for i in range(1, len(nlist)):
        current_element = nlist[i]
        j = i - 1
        shifted = False
        while j >= 0 and current_element < nlist[j]:
            nlist[j + 1] = nlist[j]
            j -= 1
            shifted = True
        if shifted:
            nlist[j + 1] = current_element

#input list
alist = [12, 11, 13, 5, 6]
print('Input List\n', alist)

#sort list
insertion_sort(alist)
print('Sorted List\n', alist)

Explanation of Optimization:

  1. The optimization introduces a flag variable shifted to check whether any elements were shifted during the inner loop.
  2. If no elements were shifted, the algorithm stops early, thus avoiding unnecessary comparisons.

Output

Input List
 [12, 11, 13, 5, 6]
Sorted List
 [5, 6, 11, 12, 13]

Summary

In this tutorial, we learned how to implement the Insertion Sort algorithm in Python. We discussed how the algorithm works by shifting elements and inserting the current element into its correct position. We also introduced an optimization to detect early stops and demonstrated how Insertion Sort can handle lists with negative values.

Python Libraries