Материал готовится,

пожалуйста, возвращайтесь позднее

пожалуйста, возвращайтесь позднее

Now, we look at insertion sort which is

another elementary method and

interestingly has quite different

performance, characteristics than

selection sort. Let's look at a demo of

insertion sort. For insertion sort, what

we're going to do is we'll move an index i

from left to right as before. But now, in

the ith iteration we're going to move a(i)

into position among the elements to its

left. Let's look at how that works on our

example with cards. So now we start by

initializing i to first card and we take

the idea that everything from i to its

left is going to be sorted and everything

from the right, we're not going to look

at, at all. So, everything to the left of

i is in ascending order everything to the

right we haven't seen at all yet. So now,

when we increment i, well, in this case

it's already an order, we don't have

anything else to do. In the third case

now, when i at the third entry in the

array. Now, we start a index j and we move

that starting at i to the left and what we

need to do is just exchange the five with

every element to its left that's greater.

So, first we exchange it with the ten.

It's still not in place so we exchange it

with the seven. Now, we get to the

beginning array, of the array and once

we've done that or we've hit a smaller

element then we have everybody to the left

of i in order. [cough] So now we increment

i again and we come to the three. Again,

we exchange as long as the card

immediately to the left is greater. And

once we've done that, then we have

everything to the left of i in ascending

order. Now, in this case, we have the

eight and we only have to exchange one and

now, it's got the seven to its left and

everything is in order. So, we've achieved

putting it in order with less work in this

case. We don't always have to go all the

way back to the beginning. For exchange it

with everybody to its left that's greater,

until we find a smaller element done in

its ascending order. Two has to go all the

way back to the begin ning [cough]. But

then the very next one, the nine, has to

only go back one position. And the sixth

has to go about halfway back. [cough] And

then, we have the entire array sorted.

Again, we can look at insertion sort in

terms of invariants. Our pointers still

scans from left to right but now, the

elements of the left of the pointer,

including it, are in order. But the

elements to the right have not yet been

seen at all. So, we have to look at the

code that's going to maintain that

invariant as the pointer increments. Move

the pointer to the right, it's incremented

again. Now, the invariant is broken

because the elements the element on the

pointer is not in sorted order to put it

in sorted order, we have to move from

right to left exchanging it with every

larger elements to its left. And that's

with the code at the bottom does starts j

at i and decrements j exchanging j with

the elements to its left. A(j) with the

element to its left, a(j) - one as long as

a(j) is less than a(j) - one or j is

bigger than zero. And that immediately

gives the, this code for insertion sort

which is similar to our code for selection

sort and just as simple it gets two nested

for loops. Selection sort head to nested

four loops a test to comparison and an

exchange inside the four loop. And that's

a fine implementation of an elementary

sorting method. What about the analysis of

insertion sort?

another elementary method and

interestingly has quite different

performance, characteristics than

selection sort. Let's look at a demo of

insertion sort. For insertion sort, what

we're going to do is we'll move an index i

from left to right as before. But now, in

the ith iteration we're going to move a(i)

into position among the elements to its

left. Let's look at how that works on our

example with cards. So now we start by

initializing i to first card and we take

the idea that everything from i to its

left is going to be sorted and everything

from the right, we're not going to look

at, at all. So, everything to the left of

i is in ascending order everything to the

right we haven't seen at all yet. So now,

when we increment i, well, in this case

it's already an order, we don't have

anything else to do. In the third case

now, when i at the third entry in the

array. Now, we start a index j and we move

that starting at i to the left and what we

need to do is just exchange the five with

every element to its left that's greater.

So, first we exchange it with the ten.

It's still not in place so we exchange it

with the seven. Now, we get to the

beginning array, of the array and once

we've done that or we've hit a smaller

element then we have everybody to the left

of i in order. [cough] So now we increment

i again and we come to the three. Again,

we exchange as long as the card

immediately to the left is greater. And

once we've done that, then we have

everything to the left of i in ascending

order. Now, in this case, we have the

eight and we only have to exchange one and

now, it's got the seven to its left and

everything is in order. So, we've achieved

putting it in order with less work in this

case. We don't always have to go all the

way back to the beginning. For exchange it

with everybody to its left that's greater,

until we find a smaller element done in

its ascending order. Two has to go all the

way back to the begin ning [cough]. But

then the very next one, the nine, has to

only go back one position. And the sixth

has to go about halfway back. [cough] And

then, we have the entire array sorted.

Again, we can look at insertion sort in

terms of invariants. Our pointers still

scans from left to right but now, the

elements of the left of the pointer,

including it, are in order. But the

elements to the right have not yet been

seen at all. So, we have to look at the

code that's going to maintain that

invariant as the pointer increments. Move

the pointer to the right, it's incremented

again. Now, the invariant is broken

because the elements the element on the

pointer is not in sorted order to put it

in sorted order, we have to move from

right to left exchanging it with every

larger elements to its left. And that's

with the code at the bottom does starts j

at i and decrements j exchanging j with

the elements to its left. A(j) with the

element to its left, a(j) - one as long as

a(j) is less than a(j) - one or j is

bigger than zero. And that immediately

gives the, this code for insertion sort

which is similar to our code for selection

sort and just as simple it gets two nested

for loops. Selection sort head to nested

four loops a test to comparison and an

exchange inside the four loop. And that's

a fine implementation of an elementary

sorting method. What about the analysis of

insertion sort?

Загрузка...

Выбрать следующее задание

Ты добавил

Выбрать следующее задание

Ты добавил