0:01

The first elementary sorting method that we're going to take a look at is an easy

method known as selection sort. The idea of selection sort, is start out with a

unsorted array and we'll use these playing cards as an example. And in the ith iteration,

we go through the array to try to find the smallest remaining entry, in this case,

the 2 is the 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 ith

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. 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 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 our code for the selection sort implementation. We identify the, the

length of the array that's n. Then we have a for 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 have an

inter-for loop that for j, if it finds a smaller one, resets min and then once

we've looked at all the elements to the right of i we exchange the smallest one

with i. That's a complete implementation of selection sort. Now it's easy to

develop on mathematical model for the cost of selection sort and here's the

proposition that describes that. Selections or uses about N^2 / 2

compares and exactly n exchanges. And just looking at this trace of selection

sort and operation really is a proof, visual proof of this proposition. In this

diagram, the entries in black, are the ones that are examined in order to find

the minimum each time with the minimum in red. Entries in gray are not touched,

they're in their final position. Well, you can see that this isn't going to be in

general an N by N square and about half of the elements in the square are black or about

N^2 / 2 and you can see also the exact formula (N - 1) + (N - 2) and so forth

is the total number of compares used. And then on each of the Ns values of the

variable i there's an exchange so that's the cost in terms of the number of

exchanges. Now, what's interesting about this proposition about selection sort is

that, it doesn't matter what order the input is. Selection sort is going to use

quadratic time because it always has to go through the whole thing to look for the

minimum. And another property is that you can't sort moving less data because

selection sort does just a linear number of exchanges. Every item is put in to

it's final position with just one exchange. Let's look at an animation of

selection sort in operation. [cough] You can see our pointer moving from right to

left every time it finds the smallest element to the right, it exchanges it into

position. Now, if the array is partially sorted, it doesn't matter to selection

sort. Still has to go through, even if it's totally sorted, still has to go

through to the side where that minimum element is. That selection sort, our first

elementary sorting method.