Hello again! In this video, we are going to continue looking at sorting algorithms. The algorithms we
looked at in the last video do a sort of the entire
iterator range.
So when the sotr call returns, every element in the iterator range will be in the correct place for
the entire range to be in order. To be sorted.
Sometimes we do not necessarily want a complete sort.
We might only be interested in the first 20 elements,
for example. If we have some results and the screen is only big enough to show 20 results, then we
just want to pick out the first 20 and have those sorted. And we are not too worried about the ones
which come after.
As an example of this, you can think of Google.
They have queries which can produce thousands or maybe even millions of results, but they just show
the first few.
And there is such a thing as a partial sort.
So this will pick out the first, say, 20 elements and put those into order, and the ones which come
after are not ordered.
And that is considerably faster than doing a complete sort.
C++ provides a partial sort in the algorithms header.
This takes an extra iterator.
So this will indicate the end of the group of elements that we want to have sorted.
For example, if we have begin +5 as this iterator, then this will give us the first five elements
in order, and the rest will be unsorted.
So we could have a call where we take the begin and end iterator of some string, for example.
So when this returns, the string will have the first five characters alphabetically at the start of
the string and then the rest will follow.
So let's look at this. We have our string here.
We do our call to partial sort.
We have this iterator, which is initially at the start of the string.
The iterator for the end of the partial sort is begin + 5. And then we are going to print out
the first five elements of this string, so we can see if we do get the first five characters. And
we will also print out the entire string, to see what that has done.
So there we are.
The first five characters are "adefg", and the characters behind that are in no particular order.
If we want to get the next 5 characters, then we can do the partial sort again, starting from this iterator.
So we take the iterator, which was at the beginning of the string, and move it forwards
five. So we have now moved past the 5 characters we just got.
So we use that as the start of the range. Then we add 5 again, to get the next five characters.
And there we are.
The next five characters are "hijkl".
So the sort started from this position, and then it found the next 5 characters in this part of
the string, which are "hijkl".
There is also a partial_sort_copy, which will do a partial sort and copy the result to a destination.
This works slightly differently.
We do not give it an iterator. Instead,
the algorithm will look at the container - the destination container - and work out how many elements
this can hold. And it will sort just enough elements to fill this container.
So if we give it a container, which, say, takes 10 elements, then this will find the first 10 elements,
sort them and store the result in this container.
If the destination is large enough to contain the entire range that is being sorted, then it will actually
sort the entire range.
So here we are, the same string again. We have another string which we are going to copy the result
into, and then the algorithm is going to find the first 5 characters in here, and store them in here.
So there we are, because "adefg" again.
And then finally, there is the nth_element algorithm, and to be honest, I found this slightly difficult
to understand when I first met it.
So if we think of the partial sort as picking out the top 5 elements and making sure the first 5
are in the right position, and not worrying about the rest, this takes the partial sort a bit further.
You can just have one element from the result. So you can say, for example, you want the fourth highest
score, the fourth placed element, and you want that to be in the correct order, but you are not worried
about the rest.
So this takes iterator again, like the partial sort did. When it returns,
the element with this iterator will be the one with the fourth rank, the ones [before] it will be the first,
second and third, but not necessarily in order.
And the ones after it will be fifth, sixth, seventh, or possibly equal fourth.
So you can also think of this as doing a partition in a way. The predicate is that the element is
less than the fourth ranked one.
So if it is the first, second or third, it will go before the fourth element.
And if it is not, it will go afterwards.
So another way to think about this is that it looks at the iterator range, as it would be if it
were sorted, and then it picks out the element that you asked for.
For example, if we have this range here, it will sort the elements and then it will pick the one which
comes out in the fourth place.
So to try and see what is happening,
we are going to make a copy of this vector and sort it, so we can compare that, and then we can compare
that to the result of calling nth_element().
So there is the original vector. There is the sorted vector.
So the element corresponding to begin + 4 is this one, with value 5.
And then in the result, the begin plus four iterator has the value 5. The elements before
it have a lower value, and the elements after it have an equal or higher value.
So they are not lower.
OK.
So that is it for video.
I will see you next time, but until then, keep coding!