Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Another Use For Stable Sorting

July 20, 2011

My earlier discussion of sorting introduced an idea that is worth stating more explicitly: Sorting a sequence stably preserves earlier orderings where they don't conflict. In other words, if you sort a sequence, and then sort it again under different criteria, the original ordering is preserved as much as possible. Moreover, there is no need to use the values of the sequence's elements directly. It can be useful to sort those elements based on indirect criteria.

Here's a simple example that shows where these properties might be useful. Suppose you have a sequence of student grade records, which you have sorted into alphabetical order by student name. Suppose that you now sort these records by grade. Each group of students with exactly the same grade will still appear in alphabetical order within that group.

This claim may seem obvious. What may be less obvious is that the claim remains true even if there are only two possible grades: pass and fail. We can exploit this property by writing a "comparison" function along these lines:

bool check_passfail(const Student& s1, const Student& s2)
 {
       return !s1.pass() && s2.pass();
 }

Here, by way of an unrealistically simple example, I am imagining a class Student with a member function named pass that returns true if the student is passing and false if the student is failing. I've written a function named check_passfail that, given two Students, returns true if and only if the first Student is failing and the second one is passing.

What happens if we use this function as a comparison function in a stable sort?

stable_sort(students.begin(), students.end(), check_passfail);

Because of how stable sorting works, students will be rearranged so that the "smallest" students — that is, the ones that are failing — will be at the beginning of the sequence, and the others will be at the end. In other words, the sequence will be divided into two subsequences. The first subsequence will contain all the failing student records; the second will contain all the passing students. Moreover, because the sort is stable, within each group, any previous order will be retained.

Therefore, if we first sort our sequence of students by name, and then use stable_sort to group them into passing and failing, each group will remain sorted by name.

This example shows that the idea of sorting includes, as a special case, what we often think of as partitioning. We have a collection of values that we want to collect into categories. The number of categories might be as small as two, as we have illustrated here, or might be larger.

Whatever the number, as long as it is possible for us to look at two elements of the sequence and determine whether the first element should go into a category that (strictly) precedes the second element's category, we can write a "comparison" function that stable_sort can use to rearrange the sequence's elements appropriately. Moreover, if the sort is stable, it will preserve any previously existing order within each individual category.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video