STL sortings as marathon illustrations

Preamble

How often have you been asked a question at the interview, the answer to which can be found in the Internet within 3 minutes? Annoying, isn't? I think such types of questions are quite stupid. However, there is one exclusion. We are going to analyse it in this article.

Question  

This question is as follows: how many sorting algorithms in STL do you know? The search on the Web can take one minute, but... In real programming if you do not know that STL has several sorting algorithms, you will not even try to search, will you? You could use std::sort() or std::stable_sort() for all the purposes and it does work. But there are three more sorting functions. Each of them can be more useful and explanatory than just sort(). Let's familiarise with them through real life examples.

Sortings  

Imagine you are writing a program for a marathon. This program gets a list of participants with their times and is going to print the winners. The obvious solution is to use std::sort() and take the first three results. It is simple but redundant. Instead of it you can use STL partial_sort() which sorts only specified number of best elements. It is much faster. And, that I suppose is even more important, it is more explanatory than sort():

// This finds and sorts three best competitors:
partial_sort(stayers.begin(), stayers.begin() + 3, stayers.end(), timeCompare);  

 Now imagine you are writing a program for a charity marathon. The participants are disabled people on wheelchairs. The first ten para-olympians should get a diploma and an encouragement prize. Now you are a more experienced developer and therefore you could make use of partial_sort() and its result. However it is redundant too because the winner is not specified. In such a case you can use a further sorting algorithm: std::nth_element(). It produces best n elements regardless of sorting. Again it is faster and more explanatory than the partial_sort:

// This gets ten best competitors without sorting:
nth_element(olimpians.begin(), olimpians.begin() + 10, olimpians.end(), timeCompare);  

And finally you are writing a program for a school marathon. To get a "pass" pupils must cover a certain distance within a set period of time. As usual you can use std::sort() and then binary search of the last successful pupil. However, as you can guess, there is a dedicated function for this task. It is std::partition(). Algorithm puts all the elements which fit the criterion first:

// This returns an iterator to the end of successful pupils:
iterator firstFailedPupil = partition(pupils.begin(), pupils.end(), isInTime); 

I wish you a proper sorting and may the Source be with you!

P.S. More information can be found in "Effective STL" by Scott Meyers, advice #31.