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.