# Support Our Site

To ensure we can continue delivering content and maintaining a free platform for all users, we kindly request that you disable your adblocker. Your contribution greatly supports our site's growth and development.

# Insertion Sort In Python

## 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.

PYTHON

# Latest Articles

Latest from djangocentral

## How to Use Subquery() in Django With Practical Examples

In the realm of web development, Django stands as a powerful and versatile framework for building robust applications. One of the key aspects of developing efficient and optimized web applications is handling database queries effectively. In this article…

## DRF Serializer: Handling OrderedDict and Converting It to a Dictionary or JSON

In Django Rest Framework (DRF) tests, when you access serializer.data, you might encounter an OrderedDict instead of a regular dictionary. This behavior is intentional and reflects the design of DRF's serialization process.Understanding the Problem The u…

## Django Rest Framework CheetSheet: Mastering API Development

Django Rest Framework (DRF) is a powerful toolkit that makes building robust and scalable web APIs with Django a breeze. Whether you're a seasoned Django developer or a newcomer, having a comprehensive cheat sheet at your disposal can be a game-changer. …