OMG! I've only watched a few mins of your video and I can't believe what a great job you did on the explanation and the beauty, pace, and clarity of the presentation! Top-notch! You really need to continue being a Tech Trainer either FT or on the side, as you are VERY GOOD at it!
❤❤❤❤ the simplest video have seen so far that made this so simple. I have watched dozens of videos at a point I said I will never use insertions sort 😅
I have been running away from this Sorting and Searching since 2011(Pre University Years), I am in the 6th year of my career and TIL "SORTING", which is simple and non-scary. Thank you!
aside from readability, which in this case I don't think is a win, you don't need to even define j because if you think about it j is just i, so the code could be written as: def iterative_insertion_sort(arr: list): for i in range(1, len(arr)): while arr[i-1] > arr[i] and i > 0: arr[i-1], arr[i] = arr[i], arr[i-1] i -= 1 This code block passes all my unit tests of which I have 14. I'll list them below. One thing Felix does which I haven't seen anyone else do is instead of comparing right to left he actually compares left to right. I guess it doesn't matter. My mind makes easier send of things as right to left, especially since you're counting down *to the left* in terms of comparisons. Anyway...no need for j. from iterative_insertion_sort import iterative_insertion_sort import pytest def test_alternating_zeroes_and_ones(): arr = [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1] assert iterative_insertion_sort(arr) == sorted(arr) def test_increasing_decreasing(): arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] assert iterative_insertion_sort(arr) == sorted(arr) def test_decreasing_increasing(): arr = [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] + list(range(1, 20)) assert iterative_insertion_sort(arr) == sorted(arr) def test_all_but_one_element_the_same(): arr = [0] * 19 + [1] assert iterative_insertion_sort(arr) == sorted(arr) def test_all_but_one_element_the_same_big_delta(): arr = [1] * 19 + [100] assert iterative_insertion_sort(arr) == sorted(arr) def test_large_range(): arr = [-100] + list(range(1, 20)) assert iterative_insertion_sort(arr) == sorted(arr) def test_very_close_numbers(): arr = [i/10 for i in range(20)] assert iterative_insertion_sort(arr) == sorted(arr) def test_all_negative_numbers(): arr = list(range(0, -5, -1)) assert iterative_insertion_sort(arr) == sorted(arr) def test_mix_of_positive_and_negative(): arr = [-10, 10] * 10 assert iterative_insertion_sort(arr) == sorted(arr) def test_alternating_high_and_low(): arr = [20 - i if i % 2 == 0 else i for i in range(20)] assert iterative_insertion_sort(arr) == sorted(arr) def test_peak_in_the_middle(): arr = [2] * 10 + [3] + [2] * 9 assert iterative_insertion_sort(arr) == sorted(arr) def test_small_range_random_integers(): arr = [5, 3, 0, 4, 0, 4, 4, 0, 4, 0, 0, 0, 0, 4, 1, 0, 1, 4, 3, 5] assert iterative_insertion_sort(arr) == sorted(arr) def test_floating_point_numbers(): arr = [float(i) for i in range(20)] assert iterative_insertion_sort(arr) == sorted(arr) def test_large_value_at_the_beginning(): arr = [1000] + list(range(1, 20)) assert iterative_insertion_sort(arr) == sorted(arr)
I found your code simple but but i dont think it is the correct example of insertion sort. bcz in insertion sort, we pick one element and put it to its correct location, but you kept swapping the element with the previous element until the previous element is not smaller than our main element. So it is technically an example of bubble sort that is executed in the reverse direction. You won't get what im trying to say just by reading my sentence. Therefore look at this example of insertion sort : l1 = [5,1,3,4,2] n = len(l1) for i in range(n): k = l1[i] j = i-1 while k=0 : l1[j+1] = l1[j] j -= 1 else: l1[j+1] = k print('Sorted list: ', l1)
I was told that in insertion sort we don't make a swap and we only move the elements greater than the current to the right next position until we reach the current correct position. Does that explanation make sense? or the swap action is the same that the shift action?
Hey , I had a doubt cuz when I wrote this code it was showing list index out of range also why did we do j=-1 , if we are going from left to right so we are increasing the index we aren't going from right to left?
the reason why j = j -1 is used is probably because,in this algo the elements to the left are always sorted before we move further(towards right),for example li = [2,6,5,1,3,4] here we start the for loop from index 1 i.e from the number '6' and check if the number to the left of '6' is greater than 6,if it is we swap and since 2 is not greater than 6, we do not swap, and since, we do not swap j = j-1 doesn't get triggered in the loop ,now we move further and now j = 2 (since, j = i),we check if the number '6' is greater than the next number, which is '5',since it is,we enter the for loop and swap these two, now as we know j is equal to 2,and we need to check if the number we just swapped is also greater than the number which is left of this newly swapped number, so, we are checking if the number '5' which just now came in the place of '6', is also greater than the number '2',to check this we decrement j by one and since it is decremented, now, j again checks if the number to the left is smaller than the number present at j, since, '5' is greater than '2', no swapping takes place. But as we move, j is equal to 3,and we check if the number to the left of '1', is greater than '1' (mind you,now the li looks like this li = [2,5,6,1,3,4]) since '6' is greater than '1', we swap now the array looks like this li = [2,5,1,6,3,4],as i had told you in the beginning that this algo always has the elemente in the left soretd before it moves forward,but you can see that the array to the left of 3 is not sorted,coz '1' is in the middle when it should be at the beginning, so, we decrease j to 2 again and check if the number to the left of '1' is greater than '1' since,5 is greater than '1' we swap since a swap has happened we further decrease j to 1 and check if the number to the left of '1' is greater than '1' since '2' is greater we swap and we get li = [1,2,5,6,3,4], now we move further in the same way.
Hi. can this even more simpler version works? --> for i in range(0,len(lst)): while (lst[i-1]>lst[i] and i>0): lst[i-1],lst[i]=lst[i],lst[i-1] i-=1 print(lst)
please make more videos like this for more concepts like Job scheduling with Greedy method , Knapsack problems, Travelling salesman Problems etc , it will be very useful for many tech enthusiasts 🙏🏻
i have a question why u'v used while instead we can use for like that : def tri_insertion(L): for i in range(1,len(l)): for j in range(len(l[:i])): if l[i]
why would you call a for loop, which is slower iirc, instead of maybe append value to list then just call the sort on the array? I’m still learning efficiency
the reason why j = j -1 is used is probably because,in this algo the elements to the left are always sorted before we move further(towards right),for example li = [2,6,5,1,3,4] here we start the for loop from index 1 i.e from the number '6' and check if the number to the left of '6' is greater than 6,if it is we swap and since 2 is not greater than 6, we do not swap, and since, we do not swap j = j-1 doesn't get triggered in the loop ,now we move further and now j = 2 (since, j = i),we check if the number '6' is greater than the next number, which is '5',since it is,we enter the for loop and swap these two, now as we know j is equal to 2,and we need to check if the number we just swapped is also greater than the number which is left of this newly swapped number, so, we are checking if the number '5' which just now came in the place of '6', is also greater than the number '2',to check this we decrement j by one and since it is decremented, now, j again checks if the number to the left is smaller than the number present at j, since, '5' is greater than '2', no swapping takes place. But as we move, j is equal to 3,and we check if the number to the left of '1', is greater than '1' (mind you,now the li looks like this li = [2,5,6,1,3,4]) since '6' is greater than '1', we swap now the array looks like this li = [2,5,1,6,3,4],as i had told you in the beginning that this algo always has the elemente in the left soretd before it moves forward,but you can see that the array to the left of 3 is not sorted,coz '1' is in the middle when it should be at the beginning, so, we decrease j to 2 again and check if the number to the left of '1' is greater than '1' since,5 is greater than '1' we swap since a swap has happened we further decrease j to 1 and check if the number to the left of '1' is greater than '1' since '2' is greater we swap and we get li = [1,2,5,6,3,4], now we move further in the same way.
All is fine, but I'm not sure why did you create a 'j' that is 'i'? I removed the 'j' variable and the result is just the same. Is it due to some common or PEP practices or a different Python version?
I think that if you do not write "j = i" what happens is that the while loop starts from the beginning of the list each time (it goes to the right and then to the left for each iteration) so it's less efficient, whereas with "j = i" it starts at "i" position and goes backwards thanks to "j -= 1".
this algorithm is not insertion sort algo ... this IS an Insertion sort : def insertion(d): for i in range(1,len(d)): key = d[i] j = i-1 while j >= 0 and key
j -= 1 means j = j - 1 it is done so that we keep on comparing the value with the left value until the while loop condition become wrong too late haha, but i hope u have already figured it out!
I didn't knew that Felix had started a programming channel apart from his PEWDIEPIE channel. But my doubt, is why is he having so less SUBSCRIBERS......... 😂
Absolutely beautiful ,a simple and concise explanation ,Wish I had teachers like you.
OMG! I've only watched a few mins of your video and I can't believe what a great job you did on the explanation and the beauty, pace, and clarity of the presentation! Top-notch! You really need to continue being a Tech Trainer either FT or on the side, as you are VERY GOOD at it!
I’m reading a book for school and the problem had 2x as much code wayyyyy harder than it had to be… thanks man!!
I found this coding example is the easiest yet most efficient one out there! Thank you Felix!
ive been using your channel to study for coding interviews, most simple explanations out there, ty!
❤❤❤❤ the simplest video have seen so far that made this so simple. I have watched dozens of videos at a point I said I will never use insertions sort 😅
I LOVE YOU SO MUCH MAN YOU'RE A LIFESAVER WISH ME LUCK I HAVE AN EXAM ON TUESDAY
I have been running away from this Sorting and Searching since 2011(Pre University Years), I am in the 6th year of my career and TIL "SORTING", which is simple and non-scary.
Thank you!
You made this look so easy dude ... thanks a lot
only till I watched this video did I know that there are two loops, one to the right and one to the left. Thank you for saving my life
This is literally a lifesaver. Thank u.
A perfect explanation and elegant coding solution
Timestamps/suggested chapters:
0:00 Intro
0:08 Overview
0:31 Example
3:21 Code
7:44 Outro
my man its just a 8 min video
*an @@log8746
Is there any reason you would want to use this instead of the built in sort function in Python?
my stupid ass teacher wants us to think of solutions instead
Job interviews
I was about to ask the same
Timsort op. Look into its implementation, that’s why it’s built in. Done v intelligently
In Java we have function but in interview the ask us to make by ourself
Thank you man . Best explanation , easy to understand
aside from readability, which in this case I don't think is a win, you don't need to even define j because if you think about it j is just i, so the code could be written as:
def iterative_insertion_sort(arr: list):
for i in range(1, len(arr)):
while arr[i-1] > arr[i] and i > 0:
arr[i-1], arr[i] = arr[i], arr[i-1]
i -= 1
This code block passes all my unit tests of which I have 14. I'll list them below. One thing Felix does which I haven't seen anyone else do is instead of comparing right to left he actually compares left to right. I guess it doesn't matter. My mind makes easier send of things as right to left, especially since you're counting down *to the left* in terms of comparisons. Anyway...no need for j.
from iterative_insertion_sort import iterative_insertion_sort
import pytest
def test_alternating_zeroes_and_ones():
arr = [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
assert iterative_insertion_sort(arr) == sorted(arr)
def test_increasing_decreasing():
arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
assert iterative_insertion_sort(arr) == sorted(arr)
def test_decreasing_increasing():
arr = [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] + list(range(1, 20))
assert iterative_insertion_sort(arr) == sorted(arr)
def test_all_but_one_element_the_same():
arr = [0] * 19 + [1]
assert iterative_insertion_sort(arr) == sorted(arr)
def test_all_but_one_element_the_same_big_delta():
arr = [1] * 19 + [100]
assert iterative_insertion_sort(arr) == sorted(arr)
def test_large_range():
arr = [-100] + list(range(1, 20))
assert iterative_insertion_sort(arr) == sorted(arr)
def test_very_close_numbers():
arr = [i/10 for i in range(20)]
assert iterative_insertion_sort(arr) == sorted(arr)
def test_all_negative_numbers():
arr = list(range(0, -5, -1))
assert iterative_insertion_sort(arr) == sorted(arr)
def test_mix_of_positive_and_negative():
arr = [-10, 10] * 10
assert iterative_insertion_sort(arr) == sorted(arr)
def test_alternating_high_and_low():
arr = [20 - i if i % 2 == 0 else i for i in range(20)]
assert iterative_insertion_sort(arr) == sorted(arr)
def test_peak_in_the_middle():
arr = [2] * 10 + [3] + [2] * 9
assert iterative_insertion_sort(arr) == sorted(arr)
def test_small_range_random_integers():
arr = [5, 3, 0, 4, 0, 4, 4, 0, 4, 0, 0, 0, 0, 4, 1, 0, 1, 4, 3, 5]
assert iterative_insertion_sort(arr) == sorted(arr)
def test_floating_point_numbers():
arr = [float(i) for i in range(20)]
assert iterative_insertion_sort(arr) == sorted(arr)
def test_large_value_at_the_beginning():
arr = [1000] + list(range(1, 20))
assert iterative_insertion_sort(arr) == sorted(arr)
I found your code simple but but i dont think it is the correct example of insertion sort. bcz in insertion sort, we pick one element and put it to its correct location, but you kept swapping the element with the previous element until the previous element is not smaller than our main element. So it is technically an example of bubble sort that is executed in the reverse direction. You won't get what im trying to say just by reading my sentence. Therefore look at this example of insertion sort :
l1 = [5,1,3,4,2]
n = len(l1)
for i in range(n):
k = l1[i]
j = i-1
while k=0 :
l1[j+1] = l1[j]
j -= 1
else:
l1[j+1] = k
print('Sorted list: ', l1)
thank you for explaining this in a simple way 🙏🏼
ua-cam.com/video/lzS_DiMlR2Q/v-deo.html
Very clear explanation, thank you so much!
Really nice and clean code! Good work!
I was told that in insertion sort we don't make a swap and we only move the elements greater than the current to the right next position until we reach the current correct position. Does that explanation make sense? or the swap action is the same that the shift action?
Left shifting a digit one by one is equivalent to swapping the digit on left hand side one by one
thanks a lot for this simple code man .......a lot of sites on the internet had to many complicated codes but this one was small and simple :)
7:20 just to correct you. There is a -1 index in Python but it points to the last element.
just amazing man. keep it up!
Hey , I had a doubt cuz when I wrote this code it was showing list index out of range also why did we do j=-1 , if we are going from left to right so we are increasing the index we aren't going from right to left?
the reason why j = j -1 is used is probably because,in this algo the elements to the left are always sorted before we move further(towards right),for example
li = [2,6,5,1,3,4]
here we start the for loop from index 1 i.e from the number '6' and check if the number to the left of '6' is greater than 6,if it is we swap and since 2 is not greater than 6, we do not swap, and since, we do not swap j = j-1 doesn't get triggered in the loop ,now we move further and now j = 2 (since, j = i),we check if the number '6' is greater than the next number, which is '5',since it is,we enter the for loop and swap these two, now as we know j is equal to 2,and we need to check if the number we just swapped is also greater than the number which is left of this newly swapped number, so, we are checking if the number '5' which just now came in the place of '6', is also greater than the number '2',to check this we decrement j by one and since it is decremented, now, j again checks if the number to the left is smaller than the number present at j, since, '5' is greater than '2', no swapping takes place. But as we move, j is equal to 3,and we check if the number to the left of '1', is greater than '1' (mind you,now the li looks like this li = [2,5,6,1,3,4])
since '6' is greater than '1', we swap now the array looks like this li = [2,5,1,6,3,4],as i had told you in the beginning that this algo always has the elemente in the left soretd before it moves forward,but you can see that the array to the left of 3 is not sorted,coz '1' is in the middle when it should be at the beginning, so, we decrease j to 2 again and check if the number to the left of '1' is greater than '1' since,5 is greater than '1' we swap since a swap has happened we further decrease j to 1 and check if the number to the left of '1' is greater than '1' since '2' is greater we swap and we get li = [1,2,5,6,3,4], now we move further in the same way.
@@prashantpareek5863 this should have more likes. basically j is an index used to know how many comparisions needs to be done for each key.
Hi. can this even more simpler version works? -->
for i in range(0,len(lst)):
while (lst[i-1]>lst[i] and i>0):
lst[i-1],lst[i]=lst[i],lst[i-1]
i-=1
print(lst)
he defined a function and you didnt
is "j = i" actually making a new array? Or just defining the value in "I"?
Eloquent, beautiful. Thanks
brilliant!!!
New to coding. Curious why you used i in your for loop and then set j to i instead of just using j to iterate through?
please make more videos like this for more concepts like Job scheduling with Greedy method , Knapsack problems, Travelling salesman Problems etc , it will be very useful for many tech enthusiasts 🙏🏻
Very nice, just what I needed, thanks!
very Informative and simple.. Loved your explanation..
I would really appreciate if you can use appropriate and understandable identifiers for variables.
Thankyou it's really great keep it up:)
Perfect explanation, Thank you sir!
very good explanation and very understandable code!
i have a question
why u'v used while instead we can use for like that :
def tri_insertion(L):
for i in range(1,len(l)):
for j in range(len(l[:i])):
if l[i]
why would you call a for loop, which is slower iirc, instead of maybe append value to list then just call the sort on the array? I’m still learning efficiency
best video on youtube.
Brilliant explanation. Thank you!
may you explain more about j=j-1 ? should it decreasing from last element ?
the reason why j = j -1 is used is probably because,in this algo the elements to the left are always sorted before we move further(towards right),for example
li = [2,6,5,1,3,4]
here we start the for loop from index 1 i.e from the number '6' and check if the number to the left of '6' is greater than 6,if it is we swap and since 2 is not greater than 6, we do not swap, and since, we do not swap j = j-1 doesn't get triggered in the loop ,now we move further and now j = 2 (since, j = i),we check if the number '6' is greater than the next number, which is '5',since it is,we enter the for loop and swap these two, now as we know j is equal to 2,and we need to check if the number we just swapped is also greater than the number which is left of this newly swapped number, so, we are checking if the number '5' which just now came in the place of '6', is also greater than the number '2',to check this we decrement j by one and since it is decremented, now, j again checks if the number to the left is smaller than the number present at j, since, '5' is greater than '2', no swapping takes place. But as we move, j is equal to 3,and we check if the number to the left of '1', is greater than '1' (mind you,now the li looks like this li = [2,5,6,1,3,4])
since '6' is greater than '1', we swap now the array looks like this li = [2,5,1,6,3,4],as i had told you in the beginning that this algo always has the elemente in the left soretd before it moves forward,but you can see that the array to the left of 3 is not sorted,coz '1' is in the middle when it should be at the beginning, so, we decrease j to 2 again and check if the number to the left of '1' is greater than '1' since,5 is greater than '1' we swap since a swap has happened we further decrease j to 1 and check if the number to the left of '1' is greater than '1' since '2' is greater we swap and we get li = [1,2,5,6,3,4], now we move further in the same way.
@@prashantpareek5863 Thank you so much ❤️
@@shahriarshovo3382 I hope the doubt was cleared.. 👍
@@prashantpareek5863 yes . :D
@@shahriarshovo3382 hey, Hi, are you Shariar from Dennis Ivy's course? The guy who did the front end of the Devsearch project?
Thanks brother, This helped me a lot
what is the point of j = i ? and not just use i
I know I'm seeing this video a bit late but... I wanted to ask if this same code will be acceptable in
exams like Cambridge Computer Science (9618)
Please make complete dsa playlist in python
Thank you so much, im grateful
Why do you need to define a new variable j? You can just ignore j and use i. Am i wrong?
Can you explain the condition used in program
a good explanation!
Good explanation 👏👍
superb master
muy buena explicacion, gracias por el video
how to print number 1,2,3,4,5 in ascending then descending order in a same line? the output should be 1,2,3,4,5,4,3,2,1. can you help?
do reverse list and then join this from 1::
why did we check if j is greater than zero ? we start the loop from zero
There is actually an item at index -1 and it is the last element from the list
Why does j need to be used, cant i just be used instead?
All is fine, but I'm not sure why did you create a 'j' that is 'i'? I removed the 'j' variable and the result is just the same. Is it due to some common or PEP practices or a different Python version?
I think that if you do not write "j = i" what happens is that the while loop starts from the beginning of the list each time (it goes to the right and then to the left for each iteration) so it's less efficient, whereas with "j = i" it starts at "i" position and goes backwards thanks to "j -= 1".
this algorithm is not insertion sort algo ...
this IS an Insertion sort :
def insertion(d):
for i in range(1,len(d)):
key = d[i]
j = i-1
while j >= 0 and key
I mean the algorithm in the video is NOT an insertion sort algorithm
Be continue bro.
How does this have better presentation than my online university?
hey can u give the code so i can copy and paste cause mine's not working
can someone explain whats j=i used for
thanks a lot brother!
I trust you and your console.
Does this work with numbers larger than 9?
Yes, why not😅
Everything else is clear but why did he used "j" instead of "i" ???
super helpful
Love from prayagraj
Can anyone explain why we put the j-=1?
j -= 1 means j = j - 1 it is done so that we keep on comparing the value with the left value until the while loop condition become wrong
too late haha, but i hope u have already figured it out!
i caN Trust you now sir
This seems like an inefficient bubble sort algo
yes you are 100% right
Sir continue the series in leetcode
Not showing the output
Better and shorter than the one of my teacher 👌😅
insertion sort perform shift operations rather than swap.
does that mean, this is wrong?
I didn't knew that Felix had started a programming channel apart from his PEWDIEPIE channel.
But my doubt, is why is he having so less SUBSCRIBERS.........
😂
You forgot to say that running-time in best case of Insertion sort is TETA(N)
Thank you!!
Thank you! Thank you! Thank you!
Thank you man
wow it working🥳
THANK YOU
this code is not worked
Super good!
Thank u
tq bro .
❤❤❤❤❤
Thanks
A hero
😎🤝
You forgot return arr[::-1]
return arr at the end of the function
LinusTechTips
Noice.
if anyone else is here cuz of faris foo like this comment
bro your code is not correct at all thank you
It's correct
Bro the code is wrong 😂
thank you
Thanks