12,507,343 members (71,388 online)
Tip/Trick
Add your own
alternative version

3.4K views
7 bookmarked
Posted

STL sortings as marathon illustrations

, 16 Dec 2012 CPOL
 Rate this:
Please Sign up or sign in to vote.
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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

 United States
No Biography provided

You may also be interested in...

 Pro Pro

Comments and Discussions

 -- There are no messages in this forum --
| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.160927.1 | Last Updated 16 Dec 2012
Article Copyright 2012 by Basil_2
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid