- [Narrator] Selection sort.
In the previous two videos, we saw bubble sort.
Selection sort is another algorithm
that works by swapping elements in a vector.
Selection sort is designed
to make the fewest swaps possible.
So for a vector of n elements,
selection sort will make n swaps.
Taking a few liberties, we can write pseudo code
for this algorithm in two lines.
While this is a little too concise,
it shows how simple the idea is.
We iterate through a vector n times,
and at each iteration we swap the element at index i
with the minimum element found
between indices i and n minus one.
Notice that this implies
a division of the vector into two parts.
The part with indices less than i,
that's the part that's already been sorted,
and the indices greater than or equal to i,
that's the part we have yet to sort.
So let's expand on this pseudo code just a bit.
Here's the expanded pseudo code
to show that there is an inner loop,
one that scans the unsorted values
to find the minimum unsorted value.
Again, the vector is divided into two parts,
the part that's already sorted,
and the part we have yet to sort.
It is this latter part that gets processed
in the inner loop.
So in that inner loop, we just update the index
of the minimum value when we find a smaller value.
And when that's done,
and we've found a minimum value, we perform the swap.
Let's look at this with a diagram.
Here we have a vector,
and everything to the left of the arrow is sorted.
You'll notice there's nothing to the left of the arrow,
so we start with nothing sorted.
Then we scan through the list,
and we find the minimum element
in the portion of the vector to the right of the arrow.
And then we swap it with the leftmost unsorted element.
Here we swap zero with seven.
Now the first element in the list is sorted.
And then we perform the same steps
on the balance of the list.
We find the minimum value in the unsorted portion,
here it's one, and we swap it
with the left most unsorted element.
We just repeat this process until the list is sorted.
Let's watch a demonstration on the Visualgo website.
Here we have a little larger vector,
but I've set the speed to move pretty quickly.
You'll see that sorted elements,
elements that are already sorted are colored orange.
The minimum that's been found,
and the element it's swapped with or marked in red,
and the element that's being scanned
at the moment is in green.
Now, you'll see 36 doesn't change position there
because it was already in the correct position.
Again, 46 here won't change position.
And now we have a sorted list.
Is selection sort stable?
No, selection sort does not guarantee
that if duplicate values appear on the vector,
that their relative positions
will be preserved after sorting.
Why is this?
Well, let's consider the vector three, five, six,
seven, three, one.
We have two threes, so we have duplicate values.
But after the first pass,
the three that was in the left-most position
will be swapped with the value one,
the far right-hand side of the vector,
and this changes the relative position of the two threes.
Yes, it's true that the next two passes
will move the two threes
to the second and third positions in the vector,
and that that operation
will preserve their relative positions,
but their relative positions
were already changed in the first step,
so selection sort is not stable.
What about its time complexity?
Well, we have an inner loop and an outer loop,
and selection sort makes n passes through the vector,
and in the ith pass, it performs n minus i comparisons,
so the complexity analysis is similar
to that of bubble sort.
We have a sequence of terms that goes from n down to one.
And if we simplify that we get n squared minus n over two,
so the complexity is O of n squared.
Let's do a quick comparison.
Here's a comparison of selection sort and bubble sort.
We see they both have time complexity events squared,
they both have constant space complexity,
bubble sort is stable while selection sort is not,
bubble sort can tell if the list is already sorted.
So, the one thing bubble sort has going for it
is that if you give it an already sorted list,
it will terminate almost immediately,
but selection sort performs the fewest swaps.
Now, how did we get that value
for constant space complexity?
We considered the extra memory
needed to implement the algorithm.
Bubble sort and selection sort
both require a temporary variable for swapping,
and selection sort also requires a variable
representing the current minimum found so far.
But in both cases, this is constant
and does not vary with the size of the input.
Hence their space complexities are big O of one.
Now, a little comprehension check.
Given this vector of integers,
zero, one, six, five, three, nine,
two, four, seven, eight,
what will the vector look like
after one pass of bubble sort?
How many swaps will take place?
Well, we're gonna swap six with five
and then six is gonna be next to three
and we'll swap six with three,
six and nine are gonna be in the correct order.
So now we're gonna swap nine with two,
nine with four, nine with seven,
nine with eight, that's six swaps.
And so our vector will look like
zero, one, five, three, six, two,
four, seven, eight, nine.
What will it look like with selection sort,
given that zero and one are already sorted
and in the correct positions.
What will the vector look like after one pass?
And how many swaps will take place?
Well, it's selection sort,
so we know we're only going to swap once per pass,
so there's only going to be one swap.
And we're gonna swap the minimum value
that we find in the unsorted portion of the vector
with the left most unsorted value.
So we're gonna swap two and six.
And so we'll get the vector
zero, one, two, five, three, nine,
six, four, seven and eight with one swap.
Now let's return to our comparison with bubble sort
for another moment.
Despite both algorithms having O of n squared complexity,
selection sort typically outperforms bubble sort.
Why is that?
Well, changing the value of a variable and memory,
that is writing to the variable is more expensive,
it takes a longer time than reading the value.
And selection sort is designed
to make the fewest swaps possible.
Therefore it performs fewer rights than bubble sort does,
hence it tends to be faster.
We're going to investigate this in greater depth
when we get to project four.
So in summary, selection sort has O of n squared complexity,
it's not stable,
it's designed to perform the fewest swaps possible.
And again, I encourage you to visit visualgo.net
to try it out on your own.
In the next video, we'll code up a version
of selection sort in C++, but that's all for now.
Thanks.