Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

The Right Way To Teach Sorting

June 08, 2011

Last week, I said that C++ textbooks often make what I consider to be four mistakes:

  • They teach readers how to write their own sorting algorithms before using the standard library.
  • The first sort algorithm they teach has quadratic performance.
  • They never teach how to write a sort algorithm that performs better; and
  • They never get around to explaining what a stable sort is or why it is useful.

I also said that I had what I thought was a better way to do it. This article describes that better way.

Programs that sort often have to deal with three separate, but interrelated, problems:

  • Sorting
  • Merging
  • Comparison

I am mentioning comparison as a separate problem because students so often get it wrong. For example, I've lost count of how many times I've seen code like this:

    struct Point { int x, y; };

bool compare(const Point& p, const Point& q)
{
    if (p.x < q.x && p.y < q.y)
           return true;
     else
           return false;
}

Of course, the compare function could have used one line in place of four:

          return p.x < q.x && p.y < q.y;

but either way, the code is wrong — at least if the intent is to use compare for sorting.

In order to avoid this common mistake, I think that it is important to be sure that students understand what comparison means before they learn how to sort. In order to do so, I think that it is a good idea to begin with merging, which is an easier problem than sorting.

Not only that, but once you know how to merge, you know how to sort, because of the following algorithm:

  1. Is your sequence of length 0 or 1? If so, you're done.
  2. Divide the sequence approximately in half, yielding two subsequences with lengths that differ by no more than 1.
  3. Sort each subsequence.
  4. Merge the two sorted subsequences.

You might think that (3) is problematic: How can we sort a sequence without first knowing how to sort it? However, (1) shows us how to sort very short sequences, and each time we reach (3), we make a recursive call that deals with ever-shorter sequences until eventually we reach (1).

This algorithm is, of course, a recursive implementation of Mergesort. If it is implemented correctly, it is stable, and it runs in O(n log n) time. Of course, it consumes extra space; but O(n) extra space is usually much better than O(n2) time.

Therefore, I think that a reasonable way to teach students about sorting is:

  1. Use the standard sort algorithm.
  2. Show students how to write a comparison function, explaining about order relations along the way.
  3. Show how to merge sorted sequences, first using the standard merge algorithm and then writing it explicitly.
  4. Show how to write Mergesort by combining merging and recursion.

It is probably true that these four steps together take more teaching time than simply instructing students on how to write a bubble sort or an insertion sort. However, not only do the students learn about sorting, but they also learn about merging, comparison, and recursion. Moreover, they do so without picking up any bad habits along the way.

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