Algorithms

A Template-Based Quicksort

Kenneth Van Camp

Want to get a taste of the benefits of template libraries before you swallow all of STL? Heres our old friend quicksort decked out in more modern clothes.

One of the improvements C++ made over C was improved type safety. C++ brought us typesafe linkage, dynamic casts, and templates, for instance. In fact, prototypes werent even a regular part of C until the C++ language introduced them.

For the most part, C++ now allows you to write type-safe programs. The printf/scanf family of functions has been virtually replaced by the stream classes. This plugged a major hole in C program type safety. Unfortunately, there are still some unsafe vestiges of C that are difficult to replace in C++. One of these is qsort.

It is impossible for a standard compiler to do any type checking on the parameters to qsort. You can pass it an array of integers and tell qsort to compare them using strcmp. It will merrily chug along and try to fulfill your request. qsort is error-prone, and difficult to use.

As quicksort implementations go, qsort is not so quick, either. Since youre required to provide a comparison function, and since this comparison function gets called many times during any sort, that one qsort call may translate into hundreds or thousands of calls to your comparison function. This function cant be inlined, either.

One approach that C programmers typically take to avoid the external comparison function is to write their own quicksort and hard code the appropriate comparisons in it. This also addresses the type safety issue, but at the price of maintainability. If you need to sort five different types of data, or use five different sorting rules, you will need to maintain five different quicksort functions.

Using Templates

Fortunately, C++ lets you resolve most of these problems. By implementing a quicksort function using templates, you can add the type safety you need. And by carefully crafting your sortable objects, you can even have them sorted without any calls to non-inline functions.

Listing 1 shows the prototypes for two template-based quicksort functions. Note that these are stand-alone functions, just like qsort. The only difference is that they are parameterized to accept an object type that can be checked at compile time. Most C++ programmers are familiar with template classes, but many do not realize that even functions outside a class can be parameterized with templates.

The reason there are two versions of the sorting function is because they support two different types of arrays. The first (qsortVT) sorts an array of objects (stored values) of any type. The second (qsortPT) sorts an array of pointers to any type of object. Listing 2 shows the implementation of each. My functions are based on a quicksort function that was published in CUJ several years ago (Reference 1) . The articles author, Mark Nelson, did an excellent job of discussing performance issues so I wont cover them here.

These functions will sort any type of array you provide. This includes the implicit types (int, float, char, etc.) as well as new types you invent (i.e., classes). When defining your own types, the only requirements are that your class must define an equality operator (operator==) and a less-than operator (operator<). These replace the comparison function that qsort requires. If youre using the value-based sorting function (qsortVT), your class must also define the assignment operator (operator=). The pointer-based function does not require an assignment operator since only the pointers are moved in the course of a sort.

Listing 3 shows how easy it is to sort an array of float. Here I have used the value-based function because I am sorting an array of objects, not pointers. (Note that the array is a pointer, but what it points to is an object.) The output from running this program is as follows:

1006.79
8056
10078.2
90023

Notice that the type of object you are sorting (in this case a float) is a template parameter to the function.

Listing 4 demonstrates the use of a user-defined type, and also uses the pointer-based sorting function. The program reads the first 100 words from a text file (which you provide on the standard input stream), sorts them, and prints the list. I have defined a new class, called Word, which is designed to hold a single word from the text file. This could just as easily be replaced by a standard string type, but I wanted to show how to use your own type. All that was needed to make this class sortable were the two comparison operators; other member functions are just there to serve interfacing needs.

Testing the Code

For testing this program, I used the following input:

All mimsy were the borogroves.

The program produces the following output:

All
borogroves.
mimsy
the
were

In some cases, it may be useful to supply a more complicated sorting rule. In real applications, there may be a primary sorting criterion, and a secondary criterion for tie breaking. The rule I will use for demonstration, in English, is as follows:

1. Shorter words should precede longer words.
2. Words of the same length should be sorted alphabetically.

To modify Listing 4 for this rule, we need only change the less-than operator to the following:

int operator<(const Word &wd) const 
  { 
   if (strlen(buf) < strlen(wd.buf))
      return 1; 
   if (strlen(buf) > strlen(wd.buf))
      return 0; 
    return (strcmp(buf, wd.buf) < 0);
    }

The output from running this program with the same input as in the previous example is:

All
the
were
mimsy
borogroves.

In my implementation of the Word class, I have used the strcmp function for my comparisons. I could have easily replaced this with an inline equivalent and avoided using an external function.

Quicksort in Perspective

I am not the first to notice the need for a template-based sorting function. In fact, the Standard Template Library (STL), which has been accepted by the ANSI/ISO C++ committees, includes a template-based sort function. So why would you want to use mine? A good reason is that mine is here today, whereas most commercial compilers are not yet providing an STL implementation. Another reason is that mine is compact and easy to understand, if that is important to you. There is a nontrivial learning curve to overcome in using STL.

To be honest, my quicksort implementation fails in one area of type safety. The value-based function (qsortVT) accepts any data type as its template parameter, as long as the type has equality, less-than and assignment operators. In fact, a pointer is a data type that has all of these operators. Therefore, your compiler will not trap the case where you accidentally provide an array of pointers instead of an array of values. It will simply sort the pointers according to their address. The pointer-based function does not have this problem; you will get a compilation error if you provide an array of values to qsortPT (although you could provide an array of pointers to pointers and it would not be caught).

Whatever your sorting requirements are, however, it is certain that qsort is not the answer to all your needs. Its slow speed due to the need for an external comparison function, and its lack of any type safety, make it an obvious target for replacement. o

References

1. Mark Nelson. Writing Your Own Quicksort, CUJ, August 1990.

Kenneth Van Camp is a Vice President at Bear Stearns Securities Corporation. He has been programming in C++ for about four years, and in C for about twelve years. His applications experience includes securities, databases, graphics, product planning, contact management, engineering simulations, real-time control, and robotics. He may be reached via e-mail at camp@bear.com.