Insertion Sort in Python

Insertion Sort in Python


What I’m going to
do in this video is attempt to create an
implementation of the insertion sort algorithm that we talked
about in the last video, and I’ll do it as
a Python function. So I’ll call the Python
function insertion sort, and it will take in a list. So the list is its parameter
in the function definition. Someone would have to
pass list as an argument. And let’s– what we’re going
to do is we’re going to step through each of these
slots in the list. I guess we could
call it that way. So let’s say 4
index in and range. We could start at the
leftmost slot in the list. So we could just
say len– len just means it’s short for length–
so length of the list. So what this would do,
this would start index. So let’s say the list
has four elements in it. Then len list, this
right here would be 4, would evaluate to 4. Range of 4 would
produce a list that has the elements
0, 1, 2, 3 in it. And so index would
be able to step through the different indices
for this list right over here. And we could do it
that way, but you might remember from
the previous video that when you’re doing
the insertion sort, it doesn’t actually
make sense to start at the very leftmost
element, because there’s nothing to compare
it to to the left. So we can actually just start
at the second to the leftmost element. And the leftmost element
is the 0-th item, so we can start
at the first item. So now if the list
has a length of 4, this right here will
produce 1, 2, 3. So it would– 1 would be the
second to the leftmost element, 2 would be the next one to the
right, 3 would be the last one. Remember, we always
start our indices at 0. The 0-th term is the
leftmost element in a list. So fine. We can step through that. And let’s get the
value of right– at that point in time of the
element that is at that index. So that way we don’t
have to keep finding it. Value is equal to list index. And this, by no
means, is going to be the most efficient
implementation of even insertion sort. It’s just going to be my best
try writing it in real time and in a way that hopefully you
might be able to understand it. So value is just the item in the
list at each of those indexes that we’re now going to
compare to all of the items to the left of it. And what I want to do is
compare value to each item to the left of it. So let’s define a variable i. Let’s let this be the
index of the things that I want to compare value to. And right from
the get-go, I want to compare value to the
thing that is left of it. So i should have one lower
of an index than index, so index minus 1. So this is the index of the item
that is directly left to it. But we’re going to keep
taking i lower and lower, so we can keep comparing value
to things further and further to the left. And so what we
want to do is we’re going to want to keep
comparing further and further left until i has
gotten all the way to the beginning of the list. And i has gotten all
the way to the beginning of the list when
it is equal to 0. So what we want to do is
we want to perform this while i is greater
than or equal to 0, because if we keep taking i
lower and lower and lower– we’re going further and further
to the left in the list– we don’t want to try to
perform it when i is further, is a negative number. That’ll just start
doing crazy things. So while i is greater
than or equal to 0, what I’m going to
do is I’m going to keep pushing i further
and further to the left. So let’s try it this way. So the first thing
I want to do– we’ve already pushed it
to the left once. So let’s compare. So if value is less
than the– this thing keeps saying syntax
error, because it’s waiting for me to keep typing. If value is less than the
item that is now at index i, so the item at index i,
list, the item at index i is this right here. So if it is less
than that, let’s shift the item that’s over here. Let’s shift it one to the right. So the right slot is i plus 1. And I can’t just say it’s
index, because remember, I’m going to keep pulling i
in lower and lower and lower. Because right now, index is i. Right now i is index
minus 1 in the first pass through this while
loop, but I’m going to– as you’ll see in a second,
I’m going to keep lowering i. So it’ll always won’t
be one left of index. So I’m going to say wherever
i is, let’s take the spot one to the right of i. So that’s i plus 1 as its index. And let’s replace that
with whatever’s at list, or whatever is at i, at slot i. So we have essentially taken
this thing right over here, whatever number was there,
and we are putting it in the slot that is
one to the right of it. And then– and actually
the way we’re setting up that algorithm, whatever’s there
is actually going to be– well, I won’t talk about that. We’ll step through it and
see how it all plays out. And then we can shift
value to the left. So whatever was in this
slot right over here will be replaced by value. So list i will equal value. So one way to think about it–
let me write a comment here. Shift what was– shift number
in slot i to slot i plus 1. Or you can say
bucket i plus 1, I guess is one way
to think about it. And then you could say
shift number right. Let me call it this way. Shift number right in slot. Let me write it this way. Shift number in slot i
right to slot i plus 1. And then over here,
we are shifting– shift value left into slot i. And so if you remember what
we did in the last video, this is exactly describing it. We’re comparing value to
the thing to the left of it. If it’s less than it, then
whatever number was in that box to the left of it,
the slot to the left, shift it to the right, and
then shift value to the left. And now compare value to
something 1 lower than that. So we want to decrement i. We want to lower i. Decrement is just
increment down. So i is equal to i minus 1. And then we’ll perform
the loop over again. And now value will
be compared– now i is two to the left of index. Compare it to that. If it is less than it,
shift that to the right and shift value
again to the left. Now, what if we have the
situation where value is not less than the item that
you’re comparing it to? Well, if it’s not
less than the item that you’re comparing it to
and that that means that value is already going to
be in the right place, it also means that you’re
done, that you don’t need to shift value
any more to the left, and you don’t have to
shift any of the stuff to the left any
more to the right. So then we are done. And I think this
could work unless I’ve made some silly mistake. So let’s try to see
if I can get this– if this actually works
as a sorting algorithm. So let me save it– insertion
sort– and let me run it. All right. So I didn’t have any at
least syntax mistakes. Syntax just means the
actual characters I use. I didn’t forget to put a colon
here or a greater than sign. It was actually able to process
this, interpret this right over here. But let’s see if
it actually works. So let me define a list. Let’s say it is
7, 1, 3, 5, 9, 2. And let me put
another 3 in there. So that is a, and
then let me see. This is the moment of truth. Insertion sort of a–
let’s see what happens. So remember, we’re
sorting it in place. This function doesn’t
return anything, but it should take whatever
list that was and had changed up all of the elements so
that now they are in order. So this is the moment of truth. Let’s see what a looks like. There you go. It is sorted. So I don’t think I made
any major mistakes. So there you go. You have insertion– a
version of insertion sort.

31 thoughts to “Insertion Sort in Python”

  1. Wow I just noticed this Computer Science playlist, I'm going to be studying this in university next year, so this will be some nice preparation! Thanks a lot! =)

  2. @mauroprovatos the part of the list to the left of index never decreases left-to-right when beginning the outer for loop (because the list is sorted from left to right). You can think of the inner while loop as marching what was originally list[index] to the left as far as it needs. For each step of that loop the same value is getting assigned from right to left. So list[i+1] == value (equals) will be true. If the left list part weren't already sorted then the algorithm wouldn't be correct.

  3. The if statement in the loop is obsolete. It could and should be included in the while condition. This way the break statement would be avoided.

  4. I've meant something like this – gist.github.com/hkdobrev/4726813

    But when I looked again it is better to leave it as is, because of the fewer cycles in your code.

  5. Don't use "list" as your variable.  list is already defined.  Although it works in this case, redefining important things like list is really a pretty bad idea.

  6. I find my way more intuitive and efficient maybe

    i = 0
    ____while i <= len(L) – 2:
    ________if L[i] <= L[i+1]:
    ____________i += 1
    ________else:
    ____________temp = L[i]
    ____________L[i] = L[i+1]
    ____________L[i+1] = temp
    ____________i = 0

  7. I am looking for more sorting algorithms like Bubble Sort, Selection Sort, Merge Sort, Quick Sort … etc

  8. def insertion_sort(A):
        for j in range(1, len(A)):
            key = A[j]
            i = j – 1
            while i >= 0 and A[i] > key:
                A[i + 1] = A[i]
                i = i – 1
            A[i+1] = key
        return A

  9. def insertionSort(alist):
    for index in range(1,len(alist)):
    currentvalue=alist[index]
    position=index
    while position>0 and alist[position-1]>currentvalue:
    alist[position]=alist[position-1]
    position-=1
    alist[position]=currentvalue

  10. I like to use sum([i, 1]). Even though it's more typing, the sum function seems similar to the variable sum from for & while loops in python

  11. I thought insertion sort used two lists, one unsorted and one empty (where it will sort the data). this is essentially a bubble sort…

  12. I think we can also use this program as it is much easier than one you show
    def insertion_sort(slist):
       for i in range(1,len(slist)):     currentvalue = slist[i]
         position = i     while position>0 and slist[position-1]>currentvalue:
             slist[position]=slist[position-1]
             position = position-1     slist[position]=currentvalueslist = [14,46,43,27,57,41,45,21,70]
    insertion_sort(slist)
    print(slist)
    It does not need to interpreted

  13. Thank you so much for explaining this in detail. There's actually a minor problem with your code. The while loop doesn't break if the second item is greater than first item.
    So one suggestion is that you decrement i by 1 at the end of the while loop besides the decrement of i within if function.

  14. Can someone please help me? :(((((((((((

    I am trying to write a program that would print both the ascending and descending order(without a built-in function),
    this is my code:

    def selectionSort(nlist,order):

    for indx in range(0, len(nlist)):

    min = nlist[indx]

    for L in range(indx+1,len(nlist)):

    if(order=="ASC"):

    nlist[L]<min

    else:

    nlist[L]>min

    min = nlist[L]

    Location = L

    temp = nlist[indx]

    nlist[indx] = min

    nlist[Location] = temp

    nlist = [29, 72, 98, 13, 87, 66, 52, 51, 36]

    order ="ASC"

    selectionSort(nlist,order)

    print(nlist)

    However I got this as my output: [29, 72, 98, 13, 87, 66, 52, 51, 36]

Leave a Reply

Your email address will not be published. Required fields are marked *