So let's start talking about our sorting algorithms.
We need to start off by having a general understanding of what sorting is.
And I just want to be clear and I want everybody to be on the same page, even though I'm sure everyone
already has a good idea of what it means to sort something.
But again, just so that we are all on the same page, sorting is when we place items in either ascending
or descending order.
So let's depict what that means.
So we'll start off and we'll have a vector of four, three, one and two.
So it's completely unsorted right now.
Unsorted.
If we want to go into ascending order, we have one, two, three and four.
And that would mean that our vector is now sorted in ascending order.
So this is ascending.
So ascending means that our values are in increasing order.
Therefore, if we wanted to do a descending sort, our values would decrease as we sort them out.
So they would be descending.
So what is the purpose of sorting values when we have our items sorted?
It's going to allow us to do a much quicker lookup of an item and there are different algorithms that
we can use to sort a series of values.
And in this lecture we're going to start off by talking about selection sort.
So let's start to look at what selection sort is and how we can perform it.
So we have a selection sort.
So to start off, we will use the exact same vector of values that we had above of four, three, one
and two.
So we want to use selection sort to sort these values.
So we'll do a quick iteration of sorting this using selection sort.
And then we'll look at some pseudocode and then we will do one more selection sort of as an example.
So what we'll do is we'll start here at value four and we'll say that value four is our smallest value.
So we will say the smallest value is currently four.
And now we'll look ahead.
So we will say I plus 1i4 index.
So we are currently at index zero and we will look through the rest of the array and find the smallest
value.
So three is smaller than four.
So our new smallest value is technically three, but then our next index, we have one.
So our new smallest value is now one, and then we have two and two is not less than one.
So what we will do is we will swap one and four.
So our new array looks like one, three, four and two.
So now that we have done one iteration through the array and we know that one is in the correct spot,
we will now start with this index and then this will be a plus one.
So now we have three.
So our smallest value now is three.
Actually, we'll do it this way.
So we went for we had four, three.
One.
So now we will have our smallest vowel here and it is currently three.
So we look at four.
Four is not less than three, but so now we look at two.
Two is less than three.
So we can get rid of three, put two there and now we will swap.
Three and two.
So now we have one, two, four and three.
So we know that one and two are sorted now.
So we are back to looking at four and then this is AI plus one.
So in this case, our smallest vowel is four.
Again, when we compare four and three, we see that three is obviously less.
So we swap them now and we have one, two, three and four.
So now our vector is sorted and ascending order just like how we wanted.
So now that we have a general idea of how selection sort works, how could we code this out?
Well, we could say four I in zero two, size minus one, and then we want four J So I in this case
is referring to where we start at.
So this was I here, this was I here, I was here and then we were sorted and then J was always one
step ahead.
So this was J plus one J plus one J plus one.
So now we have four J.
In one to size.
So that gives us the correct index that we are looking for.
And then we want to just do our simple checks.
So we have our smallest value.
Well, let's get rid of that.
If.
Smallest vow.
Is greater.
Then I.
Then we want to make our small value.
Equal to AI, because then we know AI is less than our smallest value.
And then when we have iterated through all of the elements, we want to simply swap I in the smallest
value.
And that is all we really have to do.
For this code to work.
We just go through each iteration and we want to find the smallest value and then swap them, because
then we know that that index is completely sorted and in the correct order.
So when we're looking at this pseudo code, we see that our big zero notation, just keeping this in
mind is going to be o of n squared.
We have two nested for loops that are iterating the size of of of our vector, so we know that our big
O is going to be in squared.
So not the most performant method, but it does the job.
So let's do one more example of this.
So let's get down here some and we will do a new array of values.
510, one.
For an 11.
So this is our new vector, and we're going to keep our algorithm, our pseudocode, up here in mind.
So this is going to be our AI value, and this is going to be our plus one value, which means our small
value in this case is equal to five.
So J plus one is ten.
Is is five greater than ten?
No.
Is five greater than one?
Yes, it is.
So now we will replace the smallest value with one.
Is one greater than four?
No.
Is one greater than 11?
No.
So now we do our swap.
So now we swap five because that was I and our smallest value of one.
So our new array now looks like 110, five, four, 11.
And now that we know that one is completely separate, completely sorted, and definitely in the correct
order.
Our new eye is now ten.
And this is our plus one.
So our small vowel is equal to ten.
Is ten greater than five?
Yes, it is.
Is five greater than four?
Yes, it is.
Is four greater than 11?
No.
So now we want to swap ten, because that is I and our four.
So now we have one, four, five, ten and 11.
So now this is our eye.
This is our plus one.
We do our comparisons.
We see our small vowel.
Is equal to five.
Is five greater than ten?
No.
Is five greater than 11?
No.
So now we can do we don't have to do anything increment up.
So ten is now our IE and 11 is our plus one.
In this case, our small vowel is equal to ten.
Is ten greater than 11?
No.
We now hit the end of the array, so we know for sure that our array is now sorted.
So now that is how selection sort works.
We are now going to implement this algorithm in our next lecture and if you have any questions at any
point, please feel free to ask them in the Q&A section.