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

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

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

The first elementary sorting method that

we're going to take a look at is the easy

method known as selection sort. The idea

of selection sort, this start out with a

unsorted array and we'll use these playing

cards as an example. And in the iteration,

we go through the array to try to find the

smallest remaining entry, in this case,

the 2s are smallest from any entry. And

then we'll swap that with the first entry

in the array and then we know we've got

one step done. Selection sort is based on

iterating that idea. Okay. So, the basic

selection sort method is to, in the

iteration, find the smallest remaining

entry and to the right of i or bigger

index than i and then swap that with i.

So, we start out i is at the left end and

then the remaining, all the remaining

entries to the right. We scan through and

the smallest one is the two, three entries

from the right so we swap that. So that's

the first step. Now, that part of the

array to the left of i is in it's final

order and we simply continue. So now, the

smallest is the three. Swap that with i,

increment i. So now, we have the two and

three in order, continuing that way. Find

the smallest, the four. Swap that one with

i, increment i. Find the smallest, it's

five, swap that with i, increment i. Find

the smallest, swap that with i, increment

i. [cough] Each time we have to scan

through all the remaining entries in order

to find the smallest. But then, once we

found it, we only have to swap two cards

those are both key properties of selection

sort. Now the eight is the smallest and we

swap. And now, we know they're in order

but the program doesn't so we have to look

and decide that i and n are the same and

then it swaps it with itself and does the

same thing for the last. And so, after

that process, then we know that the entire

array is in its final order, all sorted.

Alright. So let's, one way to understand

the way that an algorithm works is to

think about invariants . So, for the

selection sort, we have a pointer that was

our variable i, that scans from left to

right. Now, it's indicated by a little red

arrow in this representation. The

invariants are that the entries on onto

the left of the arrow are never changed

and they're in ascending order. No entry

to the right of the arrow is smaller than

any entry to the left of it. That's the

way that we set it up. And the algorithm

maintains those invariants by finding the

smallest entry to the right and exchange

it with the next one. So the code

implements the invariants. So, to move the

pointer to the right, we increment i. So,

now the invariant might be violated so we

have to fix it. It might be violated

because you might have an element to the

right of the pointer that is [cough]

smaller than some, the element on the

pointer. So, what we have to do is

identify the index or that minimum entry

and exchange it. Then once we've exchanged

it, again, we preserved our invariant.

After that point, no element to the left

of the pointer is going to change and all

the element, there's no smaller element to

the right. [cough] and that gives us

immediately are code for the selection

sort implementation. We identify the, the

length of the array that's min. Then we

have a four loop that goes through every

element in the array, we keep a variable

min in that is the index of the going to

be the index of the smallest element to

the right of pointer i.

we're going to take a look at is the easy

method known as selection sort. The idea

of selection sort, this start out with a

unsorted array and we'll use these playing

cards as an example. And in the iteration,

we go through the array to try to find the

smallest remaining entry, in this case,

the 2s are smallest from any entry. And

then we'll swap that with the first entry

in the array and then we know we've got

one step done. Selection sort is based on

iterating that idea. Okay. So, the basic

selection sort method is to, in the

iteration, find the smallest remaining

entry and to the right of i or bigger

index than i and then swap that with i.

So, we start out i is at the left end and

then the remaining, all the remaining

entries to the right. We scan through and

the smallest one is the two, three entries

from the right so we swap that. So that's

the first step. Now, that part of the

array to the left of i is in it's final

order and we simply continue. So now, the

smallest is the three. Swap that with i,

increment i. So now, we have the two and

three in order, continuing that way. Find

the smallest, the four. Swap that one with

i, increment i. Find the smallest, it's

five, swap that with i, increment i. Find

the smallest, swap that with i, increment

i. [cough] Each time we have to scan

through all the remaining entries in order

to find the smallest. But then, once we

found it, we only have to swap two cards

those are both key properties of selection

sort. Now the eight is the smallest and we

swap. And now, we know they're in order

but the program doesn't so we have to look

and decide that i and n are the same and

then it swaps it with itself and does the

same thing for the last. And so, after

that process, then we know that the entire

array is in its final order, all sorted.

Alright. So let's, one way to understand

the way that an algorithm works is to

think about invariants . So, for the

selection sort, we have a pointer that was

our variable i, that scans from left to

right. Now, it's indicated by a little red

arrow in this representation. The

invariants are that the entries on onto

the left of the arrow are never changed

and they're in ascending order. No entry

to the right of the arrow is smaller than

any entry to the left of it. That's the

way that we set it up. And the algorithm

maintains those invariants by finding the

smallest entry to the right and exchange

it with the next one. So the code

implements the invariants. So, to move the

pointer to the right, we increment i. So,

now the invariant might be violated so we

have to fix it. It might be violated

because you might have an element to the

right of the pointer that is [cough]

smaller than some, the element on the

pointer. So, what we have to do is

identify the index or that minimum entry

and exchange it. Then once we've exchanged

it, again, we preserved our invariant.

After that point, no element to the left

of the pointer is going to change and all

the element, there's no smaller element to

the right. [cough] and that gives us

immediately are code for the selection

sort implementation. We identify the, the

length of the array that's min. Then we

have a four loop that goes through every

element in the array, we keep a variable

min in that is the index of the going to

be the index of the smallest element to

the right of pointer i.

Загрузка...

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

Ты добавил

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

Ты добавил