Hello again! In this video, we are going to ook at sorting algorithms.
And as you might expect, sorting algorithms will put the elements in an iterator range into order.
By default, the ordering will be based on the less-than operator of the elements.
But we can provide our own comparison function if we want to use some other form of ordering.
sort() will order the elements in ascending order.
Usually the quicksort algorithm is used to implement it.
That is the fastest algorithm in the general case. If we have elements with the same key, the same thing
that we are ordering on,
they may not appear in the same order in the result, as they were in the original data.
So we saw that with partitioning as well.
The algorithm is allowed to move elements around, and that makes it faster.
We are going to use the same student class as we had in the less-than operator example.
The students with their name and ID. The less-than operatorofficer can use either one to make the comparison.
We are going to use the name here, so that will be an alphabetical sort.
And then, in the main() function, we do the same thing. We create some student objects, put them in
the vector, and we sort the vector.
So this is done alphabetically, so Jack Jones comes first and then John Smith. And in this case,
they have the same relative ordering. The Jack Jones
with that ID comes first.
I am sure I did this before and got a different ordering.
So this is not something you can rely on.
If it is important, you can do a stable_sort(), and that will make sure that all the John Smith's and
the Jack Jones's are in the same order as they were before.
If you wanted to use some different ordering, we can supply our own comparison function.
In this example, we have a vector of ints, and we are using this lambda expression for the comparison.
This is just using the greater-than operator of the elements.
So that is going to reverse the normal ordering, with the less-than operator.
So this is going to sort them with the highest element first and the lowest element last.
So let's try that out.
We are going to call sort() with our lambda expression.
And there we are, we get the highest element first and the lowest element last.
There is an is_sorted() function, similar to is_partitioned(), and we can use this to find out whether an
iterator range is already sorted.
And here we have a similar program.
We have a vector, we print it out and check whether it is sorted and then we call sort() and - well, you can
probably guess the rest!
So it is not sorted originally, and then, after we call sort(), it is sorted.
And finally, there is the is_sorted_until() algorithm. This will return an iterator to the first
element, which is not in order.
So if we have an iterator range which is not sorted, or only partially sorted, we can find the
"offending" element where it goes wrong.
So in this example, we have a vector, which is almost but not quite sorted.
And then we call is_sorted_until() to find the first [element] which is not in order.
So there we are, the first four elements are sorted.
And the first one, which is not in order, is that one with value 2.
Okay, so that is it for this video.
I will see you next time, but until then, keep coding!