Insertion Sort Implementation in Python

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It works by iterating over an input array, removing one element at a time, and then inserting it into the correct position in a new sorted array. Insertion Sort is an efficient algorithm for small lists, but it becomes inefficient for larger lists. In this article, we will discuss how to implement Insertion Sort in Python, how the algorithm works, its time and space complexities, and provide examples with detailed explanations.

How Insertion Sort Works

The Insertion Sort algorithm starts by assuming that the first element in the list is sorted. It then compares each subsequent element with the sorted elements and inserts it into its correct position in the sorted list. The Insertion Sort algorithm builds the sorted list one element at a time.

The steps involved in implementing Insertion Sort can be summarized as follows:

1. Assume that the first element in the list is sorted
2. Iterate over the remaining unsorted elements in the list
3. For each unsorted element, compare it with the sorted elements and insert it into the correct position in the sorted list
4. Repeat steps 2-3 until the entire list is sorted

Insertion Sort Implementation

Here is the implementation of Insertion Sort in Python:

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

In this implementation, we define a function called insertion_sort that takes a list of integers as input. The function then uses a loop to iterate over the list and insert each element into its correct position in the sorted list. The loop starts at the second element (index 1) because the first element is already sorted.

Inside the loop, we use a variable called current_value to store the value of the current element. We also use a variable called j to keep track of the index of the last element in the sorted part of the list.

The while loop then compares the current_value with the elements in the sorted part of the list. If an element is greater than the current_value, it is shifted one position to the right to make room for the current_value. This process continues until the current_value is in the correct position in the sorted list.

Finally, the current_value is inserted into its correct position in the sorted list, and the loop continues with the next unsorted element.

Time Complexity

The time complexity of Insertion Sort is O(n^2), where n is the number of elements in the list. This means that for a list of n elements, Insertion Sort will perform n^2 operations. In the best-case scenario, when the list is already sorted, Insertion Sort will perform n-1 comparisons and 0 swaps. In the worst-case scenario, when the list is in reverse order, Insertion Sort will perform (n^2 – n)/2 comparisons and swaps. The average-case time complexity of Insertion Sort is also O(n^2).

Insertion Sort is an efficient algorithm for small lists but becomes inefficient for larger lists. In fact, Insertion Sort is one of the slowest sorting algorithms for large lists. However, because Insertion Sort is a stable sorting algorithm and has a low memory requirement, it is still useful in certain situations.

Space Complexity

The space complexity of Insertion Sort is O(1), which means that the algorithm uses a constant amount of extra space in addition to the input list. This is because the algorithm performs the sorting in-place, i.e., it does not use any additional data structures to store the sorted list.

Examples

Let’s look at some examples of how Insertion Sort works:

Example 1:

arr = [4, 2, 1, 5, 3]
insertion_sort(arr)
print(arr)

Output:

[1, 2, 3, 4, 5]

In this example, we have an unsorted list [4, 2, 1, 5, 3]. After applying the Insertion Sort algorithm, the list is sorted in ascending order, and the output is [1, 2, 3, 4, 5].

Example 2:

arr = [1, 2, 3, 4, 5]
insertion_sort(arr)
print(arr)

Output:

[1, 2, 3, 4, 5]

In this example, we have a sorted list [1, 2, 3, 4, 5]. After applying the Insertion Sort algorithm, the list remains sorted, and the output is still [1, 2, 3, 4, 5].

Example 3:

arr = [5, 4, 3, 2, 1]
insertion_sort(arr)
print(arr)

Output:

[1, 2, 3, 4, 5]

In this example, we have a reverse-sorted list [5, 4, 3, 2, 1]. After applying the Insertion Sort algorithm, the list is sorted in ascending order, and the output is [1, 2, 3, 4, 5].

Conclusion

In this article, we discussed how to implement Insertion Sort in Python, how the algorithm works, its time and space complexities, and provided examples with detailed explanations. Insertion Sort is a simple and efficient algorithm for small lists, but it becomes inefficient for larger lists. However, because Insertion Sort is a stable sorting algorithm and has a low memory requirement, it is still useful in certain situations. We hope that this article has been informative and helpful in understanding the Insertion Sort algorithm.