- [Instructor] Hi, in this session
we're going to implement insertion sort in C++,
and so without further ado, let's begin.
We'll create a source file
and we'll call it insertion sort, okay?
And now we're going to need, just two includes,
we're gonna need vector and iostream,
and I'm going to go back
and borrow a little snippet of code from our selection sort.
Again we're gonna grab that print vector function
and we're gonna paste it in there.
Now let's get to insertion sort.
We're gonna use templating as before,
and call this Comparable to reinforce the idea
that our elements have to be comparable.
And then our function void insertion sort
takes a standard vector of comparables,
pass that in by reference,
and then as you recall,
we're gonna have an inner loop and an outer loop.
So here's the outer loop
for int i equal one, i less than the size of the vector,
and we increment i.
Remember our metaphor, "pulling cards from the deck."
We're going to pull a value out of the vector,
Comparable value, we'll call it,
is whatever's at the sub-i in our vector.
This is the value we're going to insert
in its correct place, all right?
And so then we're going to work with,
as your recall only the portion
of the list that's already sorted.
So that's going to begin at int j
is gonna be our index, i minus 1.
And then we have a while loop,
while j greater than or equal to zero,
and the value of our vector at j is greater than
this value that we're trying to find a home for.
We're gonna shift stuff,
we're gonna shift to the right.
So v(j + i) = v(j),
that's where we shift to the right, okay?
And remember we're moving backwards
through the sorted portion of our vector.
So that's going to be --j.
We're going to decrement j instead of
increment j during this while loop,
we're going from i minus one down to zero, if we need to.
And that completes our inner loop
and then we're going to insert our value.
We know we found the correct position for our value,
and so we're going to insert, that's v(j + 1)
is gonna be equal to our value,
this is our insertion.
I'm just gonna add one more line here
so we can monitor what's going on
while we're working on our sorting.
We're gonna use that print factor function and pass in v.
That is it, that is our insertion sort.
That's all there is to it.
Now let's write a main function to see it in operation,
int main, and we need to create a vector so we can sort it,
std::vector and we'll make it a vector of int
and we'll call it v as we have in earlier examples,
and we'll just give it 4, 9, 7, 8, 5, 0, 1, 2, 6, okay.
And that's our vector, has all the digits from zero to nine
and let's print that vector.
And then we're gonna run insertion sort,
and at every iteration of the outer loop
we'll print the vector to see what it looks like,
then return zero, okay.
So now let's build,
and let's run it.
Okay.
So let's inspect this output.
Here is our original vector
and recall that we're going to treat
four as already having been sorted,
and then we're gonna look at nine
and we're not gonna shift four over
because nine is already in the correct position
with respect to four,
with respect to what we already have sorted,
so that stays as is.
Then the next element that we're gonna look at is seven,
and notice that we have to shift nine over one
to put seven in the correct position.
All these digits are still untouched.
The next one we look at is three,
so we have to shift four, seven and nine
over one to the right each and then insert three.
And so this looks like it's performing as expected
and we get our sorted vector here
in the end, zero through nine.
So that's great.
Now I have another little bit of code here,
I've already prepared this.
We're not gonna walk through all the details
of the implementation, but the idea is this,
we're going to use the chrono library
and the random library.
The random library we'll use to randomize a vector
so that we have a random input to our sorting algorithms.
And chrono is a library that we're going to use
to set timers so we can keep track
of how much actual clock time is taken up
while a algorithm is sorting a vector,
and you should recognize this here, we have insertion sort.
I've taken out that print statement
'cause we don't want it.
We want to time the performance of insertion sort
without worrying about output to the screen
which tends to be very slow.
I've also added in a bubble sort,
this should look familiar from a few lectures back,
from a few videos back and selection sort.
So we have all three of the algorithms
that we've looked at so far.
And then in our main function,
what we're going to do is
we're going to keep track of the total time
that insertion sort spends working,
the total time selection sort spends working
and the total time bubble sort spends working.
And so we're gonna create a,
what I'm calling this base vector,
a vector of digits from 0 to 999.
We just iterate through those numbers
and push them into the vector.
And then we're going to use this shuffle function here,
this is going to randomize our vector.
Now, why are we doing this in a loop?
When we're working with random things,
we don't want to bias our results
by picking just one random vector
and then testing our programs.
We might get a very good vector,
one that's almost already sorted.
We might get one that's very bad,
that's almost in reverse order.
So we take a sample,
we sample, we're gonna do a thousand random vectors here
and we're going to feed each one of these random vectors,
a thousand different random vectors to insertion sort,
to selection sort and to bubble sort.
And we're gonna set these timers where
we're gonna capture the start time and the end time
and then we'll calculate the duration
and then add that to the total time
that it takes for us to do all these sorts,
for insertion sort, for selection sort and for bubble sort.
And then because we've done this 1000 times,
we'll divide by a thousand to get the average amount of time
and then we'll print out our results.
So this is going to say the average time to
sort a randomized vector of 1000 distinct elements.
And we're gonna calculate this time and print it out
for bubble sort, selection sort, insertion sort.
Now let's go back to the previous videos
in our minds for a second.
The first thing we looked at was bubble sort,
and then when we presented selection sort,
I mentioned that selection sort
tends to work a little faster than bubble sort.
Why?
As you recall, selection sort is designed
to perform the fewest swaps possible.
It performs fewer swaps than bubble sort
and swaps take more time.
It takes more time to write a value
than it does to read a value.
And then in the case of insertion sort,
insertion sort I've said is faster than
selection sort and bubble sort,
because it only looks at the sorted part of the vector
and ignores all of the unsorted values,
save the one that it's trying to find a place for.
And so what we expect in this experiment is to see
that bubble sort has the longest amount of time,
selection sort is going to be in the middle
and the fastest of the three is going to be insertion sort.
Let's see if that is in fact the case.
So we're gonna run this.
Oops! I'm writing the wrong thing sorry,
call that TC, gonna run TC,
and it's gonna take a couple seconds,
'cause it's randomizing a thousand vectors
and sorting a thousand vectors three times,
one for each of our algorithms,
and there's our result.
The average time to sort of randomized factor
of 1000 distinct elements
for bubble sort is 11,017 microseconds,
for selection sort, it's 5,500 microseconds,
and for insertion sort, it's about 3,100 microseconds.
And so clearly insertion sort is the faster of the three,
just what we expected to find.
That's all for now.