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


PYTHON

Latest Articles

Latest from djangocentral

Django 4.1 adds async-compatible interface to QuerySet

The much-awaited pull request for an async-compatible interface to Queryset just got merged into the main branch of Django.Pull Request - https://github.com/django/django/pull/14843 The Django core team has been progressively adding async suppor…
Read more →

3 min read

Making Django Admin Jazzy With django-jazzmin

Django admin is undoubtedly one of the most useful apps of Django. Over the years there has been very little change in the admin app as far as the UX is concerned and it's not a bad thing at all. Django admin was designed to provide a simple and minimali…
Read more →

4 min read