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.

I love you Sal. I truly do.

Sooo… what DON'T you do???

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! =)

by list[i+1] = list [i

wont the initial value of list[i+1] be lost forevah?

i wonder how many days a week Sal has

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

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.

please please please give more lectures on algorithms 🙂

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.

Thanks

a = [5,1,7,2,8,3,9]

a.sort()

print a

done.

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.

I dont understand why you decrease i… it begins with value zero then later you minus 1… confused

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

What if the number is 0?

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

holy sh&t, Khan is also a programmer?

plz upload some more vidoes of python…… i want to learn everything from a to z in python..and u teach awesome!

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

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

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

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

is this break necessary?

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

HE IS INTO ALL

This code doesn't work on my Apple device.

Thanks bro you nailed it.

buffone non funziona

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.

Sure, there may be a shorter (i.e., more dry way ) to do this, but the explanation is clear. Thanks.

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]