WEBVTT 00:00.480 --> 00:06.780 Hello again! In this video, we are going to continue looking at sorting algorithms. The algorithms we 00:06.780 --> 00:10.470 looked at in the last video do a sort of the entire 00:10.470 --> 00:11.340 iterator range. 00:11.910 --> 00:17.520 So when the sotr call returns, every element in the iterator range will be in the correct place for 00:17.520 --> 00:20.910 the entire range to be in order. To be sorted. 00:22.020 --> 00:25.260 Sometimes we do not necessarily want a complete sort. 00:25.620 --> 00:28.230 We might only be interested in the first 20 elements, 00:28.240 --> 00:34.590 for example. If we have some results and the screen is only big enough to show 20 results, then we 00:34.590 --> 00:38.730 just want to pick out the first 20 and have those sorted. And we are not too worried about the ones 00:38.730 --> 00:39.390 which come after. 00:41.240 --> 00:42.980 As an example of this, you can think of Google. 00:43.550 --> 00:48.380 They have queries which can produce thousands or maybe even millions of results, but they just show 00:48.380 --> 00:49.160 the first few. 00:51.970 --> 00:54.130 And there is such a thing as a partial sort. 00:54.580 --> 01:00.040 So this will pick out the first, say, 20 elements and put those into order, and the ones which come 01:00.040 --> 01:01.210 after are not ordered. 01:01.600 --> 01:04.750 And that is considerably faster than doing a complete sort. 01:07.280 --> 01:11.500 C++ provides a partial sort in the algorithms header. 01:12.290 --> 01:14.150 This takes an extra iterator. 01:14.570 --> 01:19.700 So this will indicate the end of the group of elements that we want to have sorted. 01:20.390 --> 01:26.180 For example, if we have begin +5 as this iterator, then this will give us the first five elements 01:26.180 --> 01:29.030 in order, and the rest will be unsorted. 01:32.090 --> 01:38.150 So we could have a call where we take the begin and end iterator of some string, for example. 01:38.960 --> 01:43.130 So when this returns, the string will have the first five characters alphabetically at the start of 01:43.130 --> 01:45.350 the string and then the rest will follow. 01:48.950 --> 01:51.290 So let's look at this. We have our string here. 01:52.250 --> 01:54.440 We do our call to partial sort. 01:54.860 --> 01:58.610 We have this iterator, which is initially at the start of the string. 01:59.870 --> 02:06.530 The iterator for the end of the partial sort is begin + 5. And then we are going to print out 02:06.530 --> 02:12.560 the first five elements of this string, so we can see if we do get the first five characters. And 02:12.560 --> 02:14.900 we will also print out the entire string, to see what that has done. 02:17.660 --> 02:18.290 So there we are. 02:18.290 --> 02:26.060 The first five characters are "adefg", and the characters behind that are in no particular order. 02:28.860 --> 02:34.580 If we want to get the next 5 characters, then we can do the partial sort again, starting from this iterator. 02:35.160 --> 02:39.450 So we take the iterator, which was at the beginning of the string, and move it forwards 02:39.450 --> 02:42.150 five. So we have now moved past the 5 characters we just got. 02:43.290 --> 02:48.210 So we use that as the start of the range. Then we add 5 again, to get the next five characters. 02:49.290 --> 02:49.830 And there we are. 02:49.830 --> 02:52.320 The next five characters are "hijkl". 02:52.680 --> 02:59.880 So the sort started from this position, and then it found the next 5 characters in this part of 02:59.880 --> 03:02.340 the string, which are "hijkl". 03:06.130 --> 03:12.700 There is also a partial_sort_copy, which will do a partial sort and copy the result to a destination. 03:13.300 --> 03:14.710 This works slightly differently. 03:15.730 --> 03:18.000 We do not give it an iterator. Instead, 03:18.070 --> 03:24.370 the algorithm will look at the container - the destination container - and work out how many elements 03:24.370 --> 03:28.900 this can hold. And it will sort just enough elements to fill this container. 03:29.620 --> 03:35.860 So if we give it a container, which, say, takes 10 elements, then this will find the first 10 elements, 03:36.130 --> 03:38.590 sort them and store the result in this container. 03:40.480 --> 03:46.090 If the destination is large enough to contain the entire range that is being sorted, then it will actually 03:46.090 --> 03:47.200 sort the entire range. 03:49.810 --> 03:55.000 So here we are, the same string again. We have another string which we are going to copy the result 03:55.000 --> 04:01.690 into, and then the algorithm is going to find the first 5 characters in here, and store them in here. 04:04.720 --> 04:07.060 So there we are, because "adefg" again. 04:09.040 --> 04:13.600 And then finally, there is the nth_element algorithm, and to be honest, I found this slightly difficult 04:13.600 --> 04:14.920 to understand when I first met it. 04:16.030 --> 04:21.430 So if we think of the partial sort as picking out the top 5 elements and making sure the first 5 04:21.430 --> 04:26.530 are in the right position, and not worrying about the rest, this takes the partial sort a bit further. 04:26.890 --> 04:32.530 You can just have one element from the result. So you can say, for example, you want the fourth highest 04:33.190 --> 04:37.990 score, the fourth placed element, and you want that to be in the correct order, but you are not worried 04:37.990 --> 04:38.620 about the rest. 04:40.090 --> 04:45.910 So this takes iterator again, like the partial sort did. When it returns, 04:45.910 --> 04:53.020 the element with this iterator will be the one with the fourth rank, the ones [before] it will be the first, 04:53.020 --> 04:54.940 second and third, but not necessarily in order. 04:56.050 --> 05:00.370 And the ones after it will be fifth, sixth, seventh, or possibly equal fourth. 05:02.080 --> 05:08.710 So you can also think of this as doing a partition in a way. The predicate is that the element is 05:08.710 --> 05:10.840 less than the fourth ranked one. 05:11.740 --> 05:15.310 So if it is the first, second or third, it will go before the fourth element. 05:15.940 --> 05:17.650 And if it is not, it will go afterwards. 05:22.420 --> 05:27.580 So another way to think about this is that it looks at the iterator range, as it would be if it 05:27.580 --> 05:30.430 were sorted, and then it picks out the element that you asked for. 05:31.330 --> 05:37.870 For example, if we have this range here, it will sort the elements and then it will pick the one which 05:37.870 --> 05:39.190 comes out in the fourth place. 05:40.510 --> 05:41.680 So to try and see what is happening, 05:41.680 --> 05:47.170 we are going to make a copy of this vector and sort it, so we can compare that, and then we can compare 05:47.170 --> 05:49.210 that to the result of calling nth_element(). 05:51.720 --> 05:54.900 So there is the original vector. There is the sorted vector. 05:55.200 --> 05:58.800 So the element corresponding to begin + 4 is this one, with value 5. 05:59.820 --> 06:05.640 And then in the result, the begin plus four iterator has the value 5. The elements before 06:05.640 --> 06:11.070 it have a lower value, and the elements after it have an equal or higher value. 06:11.430 --> 06:12.510 So they are not lower. 06:13.590 --> 06:14.010 OK. 06:16.330 --> 06:17.770 So that is it for video. 06:17.860 --> 06:21.130 I will see you next time, but until then, keep coding!