Insertion Sort Algorithm Explained (Full Code Included) - Python Algorithm Series for Beginners

In this one we'll cover the insertion sort algorithm.

The insertion sort algorithm breaks a list into two sublists, one with sorted values and the other with unsorted values. We move one unsorted value to the sorted sublist, and compare its value to the values to the left. We move it into the correct position by switching, each time the item to the left is larger.

#InsertionSort #Python #Algorithm

One we have sorted the element, we start the next iteration and sort the next unsorted item in the unsorted sublist.

The Insertion sort algorithm has a complexity of O(n^2) because we're still doing comparisons with two nested lists. However, this one is preferable to the bubble and selection sort algorithms. We take the "best" parts of both of those and combine them to insertion sort.

If you need more of an idea on how we use the Insertion Sort Algorithm, think of how we organize hands of playing cards. When we draw a new card into our hand, we place it in the front, find the position that it would go to within the hand, and then draw the next. The Insertion Sort Algorithm is attempting to do the same thing.

Join The Socials -- Picking Shoutouts Across YouTube, Insta, FB, and Twitter!

Thanks so much for the continued support 5440+ subscribers at the time of writing! Very incredible that I get this opportunity to share content about something I'm passionate about. Thank you for your kind words of encouragement and support. You all are awesome!

*****************************************************************
Full code from the video:

def insertion_sort(list_a):
indexing_length = range(1, len(list_a))
for i in indexing_length:
value_to_sort = list_a[i]

while list_a[i-1] (greater than) value_to_sort and i(greater than)0:
list_a[i], list_a[i-1] = list_a[i-1], list_a[i]
i = i -1
#Sorry - Youtube doesn't allow angled brackets in the description :(

return list_a

print(insertion_sort([7,8,9,8,7,6,5,6,7,8,9,8,7,6,5,6,7,8]))

Packages (& Versions) used in this video:
Python 3.7
Atom Text Editor

*****************************************************************
Code from this tutorial and all my others can be found on my GitHub:

Check out my website:

If you liked the video - please hit the like button. It means more than you know. Thanks for watching and thank you for all your support!!

--- Channel FAQ --

What text editor do you use?

What Equipment do you use to film videos?

What computer do you use/desk setup?

What editing software do you use?
Premiere Pro for video editing
Photoshop for images
After Effects for animations

Do I have any courses available?
Yes & always working on more!

Where do I get my music?
I get all my music from the copyright free Youtube audio library

Let me know if there's anything else you want answered!

-------------------------

Always looking for suggestions on what video to make next -- leave me a comment with your project! Happy Coding!

[maanyapuri]

Oh god, you explain this way better than my Software teacher. Thank you so much!

[Caimille]

Thank you so much for your video! I was having a hard time understanding the insertion sort algorithm and now I have a much better handle on it.

[Aflesyn]

I fell in love with your tutorials, thank you very much for your work! you also have an amazing voice, which makes watching videos especially enjoyable. Love, Jam

[b.f.skinner]

This is the first sorting algorithm I've attempted to learn, this video has been a tremendous help. Thank you

[peterfrancisrobante]

having an explanation that only takes a minute is the best. keep it up!!

[naitikmundra]

Hey guys, optimized version of the code:
def
for i in range(1, len(list_to_be_sorted)):
key = list_to_be_sorted[i]
j = i - 1
while j >= 0 and key < list_to_be_sorted[j]:
list_to_be_sorted[j + 1] = list_to_be_sorted[j]
j -= 1
list_to_be_sorted[j + 1] = key
return list_to_be_sorted

[kvelez]

This is the best video, I finally understood it. You made it very easy, I'll subscribe.

I recreated it, hope it looks good:

list = []#list
limit = int(input("Amount of elements to sort? "))#only int

for _ in range(limit):#repetition
item = input("Type the element: ") #int or str
list.append(item)#addition to the list

for i in range(1, len(list)):#looping through list
value_to_sort = list[i]#element to the right.

while list[i-1] > value_to_sort and i > 0: #compare left to right elements
list[i-1], list[i] = list[i], list[i-1] #Ascending
# list[i-1], list[i] = list[i], list[i-1] #Descending
i -=1
print("List: ", list) #output

[timohelasvuo]

Thanks for the video! Another golden nugget :)

[Captainfeso]

You explained this so well! Even a 10 year old would understand!

[emeryli]

i love your voice, it's so calm, clear and comfortable

[swatiruhela]

So nice explanation .. I was finding insertion sort very tough, but your interpretation made me easy to understand .. Thanks a lot Derrick..

[moritzwolff]

There is an implementation of insertion sort that is almost twice as fast:

def insertion(list):

for i in range(1, len(list)):
temp = list[i]
index = i - 1

while index >= 0 and list[index] > temp:
list[index + 1] = list[index]
index -= 1
list[index + 1] = temp

return list

This is because Derricks implementation needs almost twice as many steps for each iteration of the while-loop compared to the implementation proposed here (two assignment statements: list_a[i] to list_a[i-1] and vice versa). You can confirm this for yourself comparing the running times of both implementations: you will see that the second implementation is almost twice as fast.

[huzaifaalam]

Can't believe i understood all of it in less than 6 minutes THANK YOU

[abhinandanmohanty]

Can you please explain why i=i-1 make the next iteration??

[naiadbaksh]

As much as your explanations are great, your editing makes these videos a cut above the rest! That green screen (?) at the beginning is just *chef's kiss*

[HanisaMohamed]

I can always rely on your videos to give a good explanation! Thanks!!!

[kunalmeshram]

I just went through 10 videos but this video is just got throw too my head and other's were bounces over 🤣 thanks man

[zaedis]

Thank you so much. The material I was given to teach me this only explained the concept and didn't explain the example code at all.

[emmanuelugwu]

if i could like this video a million times i would.. thank you soo much

[AmanSharma-htzq]

Thank you so much, bro. I see the neatest codes in your videos. Keep making videos on more difficult topics.