Insertion Sort In Python

2 min read

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.Insertion Sort In Python

Insertion Sort Program In Python

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 input
l = [54, 26, 93, 17, 77, 31, 44, 55, 20]


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


Latest Articles

Latest from djangocentral

Capturing Query Parameters of request.get in Django

In Django, the request object contains a variety of information about the current HTTP request, including the query parameters. Query parameters are a way to pass additional information in the URL and are used to filter or sort data. The request object p…
Read more →

2 min read

Understanding related_name in Django Models

In Django, related_name is an attribute that can be used to specify the name of the reverse relation from the related model back to the model that defines the relation. It is used to specify the name of the attribute that will be used to access the relat…
Read more →

2 min read