TOMMY: Let's take a look at selection sort, an algorithm for taking a list of numbers and sorting them. An algorithm, remember, is simply a step-by-step procedure for accomplishing a task. The basic idea behind selection sort is to divide our list into two portions-- a sorted portion and an unsorted portion. At each step of the algorithm, a number is moved from the unsorted portion to the sorted portion until eventually the entire list is sorted. So here's a list of six numbers-- 23, 42, 4, 16, 8, and 15. Right now the entire list is considered unsorted. Even though a number like 16 may already be in its correct location, our algorithm has no way of knowing that until the entire list is sorted. So we'll consider every number to be unsorted until we sort it ourselves. We know that we want the list to be in ascending order. So we'll want to build up the sorted portion of our list from left to right, smallest to largest. To do that, we'll need to find the minimum unsorted element and put it at the end of the sorted portion. Since this list is not sorted, the only way to do that is to look at each element in the unsorted portion, remembering which element is the lowest and comparing each element to that. So we'll first look at the 23. This is the first element we've seen, so we'll remember it as the minimum. Next we'll look at 42. 42 is larger than 23, so 23 is still the minimum. Next is the 4 which is less than 23, so we'll remember 4 as the new minimum. Next is 16 which is larger than 4, so 4 is still the minimum. 8 is larger than 4, and 15 is larger than 4, so 4 must be the smallest unsorted element. So even though as humans we can immediately see that 4 is the minimum element, our algorithm needs to look at every unsorted element, even after we've found the 4-- the minimum element. So now that we've found the minimum element, 4, we'll want to move it into the sorted portion of the list. Since this is the first step, this means we want to put 4 at the beginning of the list. Right now 23 is at the beginning of the list, so let's swap the 4 and the 23. So now our list looks like this. We know that 4 must be in its final location, because it is both the smallest element and the element at the beginning of the list. So this means that we don't ever need to move it again. So let's repeat this process to add another element to the sorted portion of the list. We know that we don't need to look at the 4, because it's already sorted. So we can start at the 42, which we'll remember as the minimum element. So next we'll look at the 23 which is less than 42, so we remember 23 is the new minimum. Next we see the 16 which is less than 23, so 16 is the new minimum. Now we look at the 8 which is less than 16, so 8 is the new minimum. And finally 8 is less than 15, so we know that 8 is a minimum unsorted element. So that means we should append 8 to the sorted portion of the list. Right now 4 is the only sorted element, so we want to place the 8 next to the 4. Since 42 is the first element in the unsorted portion of the list, we'll want to swap the 42 and the 8. So now our list looks like this. 4 and 8 represent the sorted portion of the list, and the remaining numbers represent the unsorted portion of the list. So let's continue with another iteration. We start with 23 this time, since we don't need to look at the 4 and the 8 anymore because they've already been sorted. 16 is less than 23, so we'll remember 16 as the new minimum. 16 is less than 42, but 15 is less than 16, so 15 must be the minimum unsorted element. So now we want to swap the 15 and the 23 to give us this list. The sorted portion of the list consists of 4, 8 and 15, and these elements are still unsorted. But it just so happens that the next unsorted element, 16, is already sorted. However, there's no way for our algorithm to know that 16 is already in its correct location, so we still need to repeat exactly the same process. So we see that 16 is less than 42, and 16 is less than 23, so 16 must be the minimum element. It's impossible to swap this element with itself, so we can simply leave it in this location. So we need one more pass of our algorithm. 42 is greater than 23, so 23 must be the minimum unsorted element. Once we swap the 23 and the 42, we end up with our final sorted list-- 4, 8, 15, 16, 23, 42. We know 42 must be in the correct place since it's the only element left, and that's selection sort. Let's now formalize our algorithm with some pseudocode. On line one, we can see that we need to integrate over every element of the list. Except the last element, since the 1 element list is already sorted. On line two, we consider the first element of the unsorted portion of the list to be the minimum, as we did with our example, so we have something to compare to. Line three begins a second loop in which we iterate over each unsorted element. We know that after i iterations, the sorted portion of our list must have i elements in it since each step sorts one element. So the first unsorted element must be in position i plus 1. On line four, we compare the current element to the minimum element that we've seen so far. If the current element is smaller than the minimum element, then we remember the current element as the new minimum on line five. Finally, on lines six and seven, we swap the minimum element with the first unsorted element, thereby adding it to the sorted portion of the list. Once we have an algorithm, an important question to ask ourselves as programmers is how long did that take? We'll first ask the question how long does it take for this algorithm to run in the worst case? Recall we represent this running time with big O notation. In order to determine the minimum unsorted element, we essentially had to compare each element in the list to every other element in the list. Intuitively, this sounds like an O of n squared operation. Looking at our pseudocode, we also have a loop nested inside another loop, which indeed sounds like an O of n squared operation. However, remember that we didn't need to look over the entire list when determining the minimum unsorted element? Once we knew that the 4 was sorted, for example, we didn't need to look at it again. So does this lower the running time? For our list of length 6, we needed to make five comparisons for the first element, four comparisons for the second element, and so on. That means that the total number of steps is the sum of the integers from 1 to the length of the list minus 1. We can represent this with a summation. We won't go into summations here. But it turns out that this summation is equal to n times n minus 1 over 2. Or equivalently, n squared over 2 minus n over 2. When talking about asymptotic runtime, this n squared term is going to dominate this n term. So selection sort is O of n squared. Recall that in our example, selection sort still needed to check if a number that was already sorted needed to be moved. So that means that if we ran selection sort over an already sorted list, it would require the same number of steps as it would when running over a completely unsorted list. So selection sort has a best case performance of n squared, which we represent with omega n squared. And that's it for selection sort. Just one of the many algorithms we can use to sort a list. My name is Tommy, and this is cs50.