Insertion Sort

Insertion sort is a popular shorting algorithm, similar to selection sort the unsorted list or array is divided into to two parts, left part being sorted which is initially empty and the right part being unsorted which at the very beginning is the entire list.

At each iteration element from the unsorted list is inserted at the appropriate position in the sorted part. This process continues until the entire list is sorted. Basically, we are iterating over the element of the sorted list until the correct position is found.

Since the items of the unsorted part are continuously inserted at appropriate positions at the sorted list therefore named Insertion sort.

How Insertion Sort Works

Insertion Sort works by dividing the array into two parts: a sorted subarray and an unsorted subarray. At the beginning, the sorted subarray contains only the first element of the array.

Then, the algorithm repeatedly takes the first element from the unsorted subarray and inserts it into its correct position in the sorted subarray.
The steps for the Insertion Sort algorithm are as follows:

1. Iterate through the array from the second element to the last element.
2. For each element, compare it with the elements in the sorted subarray, moving larger elements to the right. Insert the current element into the correct position in the sorted subarray.
3. Insertion Sort Program In Python.

Python Implementation of Insertion Sort

Here's the Python code for implementing Insertion Sort:

def instertion_sort(seq):
    for slice_end in range(len(seq)):
        pos = slice_end
        # inserting elements at correct position
        while pos > 0 and seq[pos] < seq[pos - 1]:
            (seq[pos], seq[pos - 1]) = (seq[pos - 1], seq[pos])
            pos = pos - 1

# test inputl = [54, 26, 93, 17, 77, 31, 44, 55, 20]
instertion_sort(l)print(l)

Output:

[17, 20, 26, 31, 44, 54, 55, 77, 93]

In the above function outer for loop is iterating over every element of the list from index 0 to the end of the list, the inner while loop swaps the values and inserts them to their appropriate positions this keeps on continuing until the entire list is sorted.

Time Complexity

The worst-case time complexity of the Insertion Sort algorithm is O(n^2), where n is the number of elements in the array. However, it performs well on small datasets or nearly sorted datasets, making it a good choice for such scenarios.

Conclusion

Insertion Sort is a basic sorting algorithm that is easy to understand and implement. While it may not be the most efficient sorting algorithm for large datasets, it is still a valuable tool to have in your programming toolkit. Understanding how Insertion Sort works can provide insights into the fundamentals of sorting algorithms.

In this article, we covered the Insertion Sort algorithm and provided a Python implementation for sorting an array using this algorithm. By experimenting with the code and understanding its inner workings, you can gain a deeper understanding of sorting algorithms and their applications.

Remember that there are more efficient sorting algorithms available for larger datasets, but learning about Insertion Sort is a great starting point for exploring the world of sorting algorithms in computer science.