Introduction to Insertion Sort in Python

Introduction

Insertion sort is a simple yet efficient sorting algorithm that builds the final sorted array one element at a time. It is an in-place comparison-based sorting algorithm that works well for small input sizes or partially sorted arrays. Insertion sort is easy to understand and implement, making it a popular choice in various scenarios.

How Insertion Sort Works

Insertion sort works by dividing the array into two parts: the sorted part and the unsorted part. Initially, the sorted part contains only the first element, and the rest of the array is considered unsorted. The algorithm repeatedly takes the next unsorted element and inserts it into its correct position in the sorted part.

To insert an element into the sorted part, the algorithm compares it with each element in the sorted part, moving elements to the right until it finds the correct position. This process continues until the entire array is sorted.

Visual Representation of Insertion Sort

The following steps will assist you in grasping the workings of insertion sort by providing an example with an array.

Iteration 1

Iteration 2

Iteration 3

Python Implementation of Insertion Sort

Now let’s see how we can implement the insertion sort algorithm in Python:

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1

        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key

# Example usage
arr = [64, 25, 12, 22, 11]
insertion_sort(arr)
print("Sorted array:", arr)

In this implementation, we define a function `insertion_sort` that takes an array as input and sorts it in-place. The variable `n` stores the length of the array. We iterate over the array starting from the second element (`i = 1`), as the first element is considered already sorted.

Inside the loop, we store the current element `arr[i]` in the variable key. We initialize`j` as `i – 1` to compare key with the elements in the sorted part. The while loop compares key with each element from `arr[j]` to `arr[0]`. If an element is greater than `key`, we move it one position ahead to make room for `key`.

Once we find the correct position for `key` or reach the beginning of the sorted part, we insert `key` at `arr[j + 1]`. This process continues until all elements are in their respective positions.

Complexity Analysis of Insertion Sort

1. Time Complexity

2. Space Complexity

Overall, insertion sort’s time complexity makes it less efficient than some other sorting algorithms like merge sort or quicksort, which have an average-case time complexity of O(n log n). However, insertion sort can still be efficient for small input sizes or partially sorted arrays. Its simplicity and low space complexity make it a reasonable choice in certain scenarios.

Conclusion

Insertion sort is a simple yet effective algorithm for sorting small input sizes or partially sorted arrays. It has a time complexity of O(n^2) in the worst case and performs well for small arrays. Although there are more efficient sorting algorithms available, understanding insertion sort can provide a foundation for understanding more complex sorting algorithms.

By implementing insertion sort in Python, you can gain a deeper understanding of the algorithm and its inner workings.