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.
