13,295,243 members (73,488 online)
Tip/Trick
alternative version

#### Stats

3.9K views
7 bookmarked
Posted 16 Dec 2012

# STL sortings as marathon illustrations

, 16 Dec 2012
 Rate this:
How to choose an STL sorting algorithm.

## 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.

## About the Author

 United States
No Biography provided

## Comments and Discussions

 -- There are no messages in this forum --