3 min read

You have played card games in our hands in the same insertion sort works. It is a simple sorting algorithm.

Simple word looks interesting to you. It seems to be beginner level concept. Ya, You are thinking right about this algorithm.

Just wait a minute, Read algorithm for more confidence

Algorithm for Insertion Sort

// Sort an lst[] of size n
insertion_sort(lst)
Loop from i = 1 to n-1.
      Pick element lst[i] and then insert it into sorted sequence lst[0…i-1]

Oh, Programming is simple then its look like 🙂

Insertion Sort in Python Code

# Insertion Sort Published on Freshlybuilt.com
def insertion_sort(lst):
    # Traverse through 1 to len(lst)
    for i in range(1, len(lst)):
        # Move elements of lst[0..i-1], that are 
        # greater than next_elem, to one position ahead 
        # of their current position  
        j = i - 1  
        next_elem = lst[i]

        # Compare the current element with next one
        while lst[j] > next_elem and j >= 0:
            lst[j + 1] = lst[j]
            j = j - 1

        lst[j + 1] = next_elem
        print("Iteration number {i}:", lst)

    return lst


def main():
    lst = [8, 17, 3, 9]
    print("Initial Unsorted List:", lst)
    insertion_sort(lst)
    print("After Sorting:", lst)


if __name__ == "__main__":
    main()

Output

Initial Unsorted List: [8, 17, 3, 9]
After Sorting: [3, 8, 9, 17]

Okay, But do you have something else for explanation of insertion sort?

Ya, Control Flow Chart( Flowchart) for insertion sort in Python Waiting for your reading.

Insertion Sort in Python Flowchart

We have 1:50 min Youtube video for insertion sort in python with given code. Our Main focus is to produce all video less than 5 min 🙂

Insertion sort in python (Simplest video with Source code / algorithm)

Some Facts about Insertion Sort

Time ComplexityO(n*2)
Auxiliary SpaceO(1)
Sorting In PlaceYes
StableYes
OnlineYes
Algorithmic Paradigm Incremental Approach
Boundary Cases:It will takes maximum time to sort if elements are sorted in reverse order. And Insertion Sort takes minimum time (Order of n) when elements are already sorted.

Use of Insertion Sort

  •  Insertion sort is used when a number of elements are small.
  • It can also be useful when the input array is almost sorted, only a few elements are misplaced incomplete big array.

What is Binary Insertion Sort?

Insertion Sort can use binary search to reduce the number of comparisons in normal insertion sort. Binary Insertion Sort uses binary search to find the proper location to insert the selected item at each iteration. In normal insertion, sorting takes O(i) (at ith iteration) in the worst case. We can reduce it to O(log) by using binary search.

The algorithm, as a whole, still has a running worst-case running time of O(n2) because of the series of swaps required for each insertion.

If you liked my blog, Please like and share it with your friend 🙂

4+

Vishal Sharma

Currently pursuing Computer Science degree from G.B Pant Government Engineering college, New Delhi.

0 Comments

Leave a Reply