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

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

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

Now, we'll look at Shellsort which is a

bit elementary on the face of it but it's

not at all elementary as you'll see. The

idea of Shellsort is that Insertion Sort

is inefficient because elements really

move only one position at the time even

when we're kind of know that they have a

long way to go. The idea behind Shellsort

is that we'll move entries several

positions at a time and the way we're

going to do it, it's called h-sorting the

array. So, an h-sorted array is h

different inter leaves sorted

sub-sequences so in this case with h=4

if we start at L and look at every

fourth element - M, P, T - then it's sorted. If

we start in the second place at E and look

at every fourth element, it's sorted. So

this is 4 interleave sequences, that's

a 4-sorted array. And what we're going

to do is implement a sorting method that

h-sort for decreasing sequences of values

of h. This is one of the oldest sorting

methods invented by Shell in 1959. So, in

this case, it starts out with the input

example shown and then the 13-sort -

a few items are moved, 4-sort - a few

more are moved, and then finally, a 1-sort.

And the idea is that each of the

sorts can be implemented with only a few

exchanges given that the previous ones

happened. So first thing is how do we get an

array h-sorted? That's actually pretty

easy. We just use Insertion Sort but

instead of going one back every time we

come with a new item, we go h back. So for

example when we come to this A in the

Insertion Sort, then it's, we look at the

array before that and then there was M and

E in the positions three back so we

exchange the A with the larger one to its

left, that's M and then the other larger

one to its left, that's E and then put it

into position. So the code is the same as

insertion, as for Insertion Sort, except

that when we go backwards through the

array we skip by h instead of just by one.

That's how we h-sort an array. And the

idea is we're going to use Insertion Sort

because of two reasons based on our

understanding of how Insertion Sort works.

While the first thing is if the increments

are big then the size of the sub arrays

that we're sorting are pretty small so any

sorting method including Insertion Sort is

going to work well. But the other thing is

if the increments are small because we've

done previous h-sorts for bigger

values of h, the array is partially sorted

and so Insertions Sort is going to be

fast. You wouldn't work to use Shellsort

as the basis for h-sorting because that

always takes quadratic time no matter what

order there is in the array. So let's look

at example of Shellsort with increment

7, 3, and 1. So, we start with

this sort example and then 7-sorting

it - just involves doing insertion

sort but just reaching back

7 each time. In this case, the 4

subfiles stretched out at seven each only

have two elements in them. And then we

3-sort. Now, because it's 7-sorted

and a 3-sort elements are either

already in placed or on a go back a few

strides. On this case, it's only the A

that goes back two. And then we 1-sort

and again because of the fact that it's

been 7-sorted and 3-sorted, the

arrays are almost in order when it comes

time to do the 1-sort and most of the

items only go back one or two positions.

So we have to do a few extra passes to do

the higher sorts but the each element

moves only a little bit on each path and

that's how Shellsort gains its efficiency.

bit elementary on the face of it but it's

not at all elementary as you'll see. The

idea of Shellsort is that Insertion Sort

is inefficient because elements really

move only one position at the time even

when we're kind of know that they have a

long way to go. The idea behind Shellsort

is that we'll move entries several

positions at a time and the way we're

going to do it, it's called h-sorting the

array. So, an h-sorted array is h

different inter leaves sorted

sub-sequences so in this case with h=4

if we start at L and look at every

fourth element - M, P, T - then it's sorted. If

we start in the second place at E and look

at every fourth element, it's sorted. So

this is 4 interleave sequences, that's

a 4-sorted array. And what we're going

to do is implement a sorting method that

h-sort for decreasing sequences of values

of h. This is one of the oldest sorting

methods invented by Shell in 1959. So, in

this case, it starts out with the input

example shown and then the 13-sort -

a few items are moved, 4-sort - a few

more are moved, and then finally, a 1-sort.

And the idea is that each of the

sorts can be implemented with only a few

exchanges given that the previous ones

happened. So first thing is how do we get an

array h-sorted? That's actually pretty

easy. We just use Insertion Sort but

instead of going one back every time we

come with a new item, we go h back. So for

example when we come to this A in the

Insertion Sort, then it's, we look at the

array before that and then there was M and

E in the positions three back so we

exchange the A with the larger one to its

left, that's M and then the other larger

one to its left, that's E and then put it

into position. So the code is the same as

insertion, as for Insertion Sort, except

that when we go backwards through the

array we skip by h instead of just by one.

That's how we h-sort an array. And the

idea is we're going to use Insertion Sort

because of two reasons based on our

understanding of how Insertion Sort works.

While the first thing is if the increments

are big then the size of the sub arrays

that we're sorting are pretty small so any

sorting method including Insertion Sort is

going to work well. But the other thing is

if the increments are small because we've

done previous h-sorts for bigger

values of h, the array is partially sorted

and so Insertions Sort is going to be

fast. You wouldn't work to use Shellsort

as the basis for h-sorting because that

always takes quadratic time no matter what

order there is in the array. So let's look

at example of Shellsort with increment

7, 3, and 1. So, we start with

this sort example and then 7-sorting

it - just involves doing insertion

sort but just reaching back

7 each time. In this case, the 4

subfiles stretched out at seven each only

have two elements in them. And then we

3-sort. Now, because it's 7-sorted

and a 3-sort elements are either

already in placed or on a go back a few

strides. On this case, it's only the A

that goes back two. And then we 1-sort

and again because of the fact that it's

been 7-sorted and 3-sorted, the

arrays are almost in order when it comes

time to do the 1-sort and most of the

items only go back one or two positions.

So we have to do a few extra passes to do

the higher sorts but the each element

moves only a little bit on each path and

that's how Shellsort gains its efficiency.

Загрузка...

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

Ты добавил

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

Ты добавил