WEBVTT 00:00.150 --> 00:03.510 Hello again! In this video, we are going to ook at sorting algorithms. 00:04.350 --> 00:09.510 And as you might expect, sorting algorithms will put the elements in an iterator range into order. 00:10.230 --> 00:15.060 By default, the ordering will be based on the less-than operator of the elements. 00:15.510 --> 00:20.040 But we can provide our own comparison function if we want to use some other form of ordering. 00:22.070 --> 00:24.680 sort() will order the elements in ascending order. 00:25.160 --> 00:28.100 Usually the quicksort algorithm is used to implement it. 00:28.490 --> 00:34.370 That is the fastest algorithm in the general case. If we have elements with the same key, the same thing 00:34.370 --> 00:35.570 that we are ordering on, 00:35.960 --> 00:39.980 they may not appear in the same order in the result, as they were in the original data. 00:40.250 --> 00:42.140 So we saw that with partitioning as well. 00:42.470 --> 00:46.010 The algorithm is allowed to move elements around, and that makes it faster. 00:49.610 --> 00:53.810 We are going to use the same student class as we had in the less-than operator example. 00:54.360 --> 01:01.310 The students with their name and ID. The less-than operatorofficer can use either one to make the comparison. 01:01.640 --> 01:04.730 We are going to use the name here, so that will be an alphabetical sort. 01:06.950 --> 01:11.460 And then, in the main() function, we do the same thing. We create some student objects, put them in 01:11.460 --> 01:13.640 the vector, and we sort the vector. 01:17.570 --> 01:23.810 So this is done alphabetically, so Jack Jones comes first and then John Smith. And in this case, 01:23.810 --> 01:26.630 they have the same relative ordering. The Jack Jones 01:26.990 --> 01:28.250 with that ID comes first. 01:29.540 --> 01:31.550 I am sure I did this before and got a different ordering. 01:31.550 --> 01:33.740 So this is not something you can rely on. 01:35.630 --> 01:42.800 If it is important, you can do a stable_sort(), and that will make sure that all the John Smith's and 01:42.800 --> 01:45.260 the Jack Jones's are in the same order as they were before. 01:48.020 --> 01:51.860 If you wanted to use some different ordering, we can supply our own comparison function. 01:52.730 --> 01:58.160 In this example, we have a vector of ints, and we are using this lambda expression for the comparison. 01:58.850 --> 02:01.370 This is just using the greater-than operator of the elements. 02:01.910 --> 02:05.780 So that is going to reverse the normal ordering, with the less-than operator. 02:06.290 --> 02:10.430 So this is going to sort them with the highest element first and the lowest element last. 02:13.040 --> 02:14.620 So let's try that out. 02:15.110 --> 02:17.630 We are going to call sort() with our lambda expression. 02:20.460 --> 02:24.060 And there we are, we get the highest element first and the lowest element last. 02:27.200 --> 02:32.650 There is an is_sorted() function, similar to is_partitioned(), and we can use this to find out whether an 02:32.660 --> 02:34.280 iterator range is already sorted. 02:37.260 --> 02:38.940 And here we have a similar program. 02:39.150 --> 02:45.480 We have a vector, we print it out and check whether it is sorted and then we call sort() and - well, you can 02:45.480 --> 02:46.320 probably guess the rest! 02:47.680 --> 02:51.220 So it is not sorted originally, and then, after we call sort(), it is sorted. 02:53.380 --> 02:58.840 And finally, there is the is_sorted_until() algorithm. This will return an iterator to the first 02:58.840 --> 03:00.700 element, which is not in order. 03:01.360 --> 03:06.490 So if we have an iterator range which is not sorted, or only partially sorted, we can find the 03:06.490 --> 03:09.070 "offending" element where it goes wrong. 03:13.080 --> 03:17.520 So in this example, we have a vector, which is almost but not quite sorted. 03:18.300 --> 03:23.160 And then we call is_sorted_until() to find the first [element] which is not in order. 03:27.950 --> 03:30.530 So there we are, the first four elements are sorted. 03:30.950 --> 03:33.920 And the first one, which is not in order, is that one with value 2. 03:34.820 --> 03:36.260 Okay, so that is it for this video. 03:36.650 --> 03:39.500 I will see you next time, but until then, keep coding!