The traditional way to implement a sorting algorithm
is to write a function or procedure that sorts an array of data.
This chapter presents an alternate, object-oriented approach
that is based on the notion of an
*abstract sorter* .

Think of a sorter as an abstract machine,
the sole purpose of which is to sort arrays of data.
A machine is an object.
Therefore, it makes sense that
we represent it as an instance of some class.
The machine sorts data.
Therefore, the class will have a member function,
say `Sort`,
which sorts an array of data.

Program declares the abstract class template `Sorter<T>`.
The public interface of this class consists
of the single function `Sort`.
This function takes as its lone argument
a reference to an `Array<T>` instance
and it sorts the data contained therein.
We use the `Array<T>` class defined in Section
to represent the data to be sorted
because all array subscript operations
are bounds-checked and because we can determine the length
of the array by calling the `Length` member function
of the `Array<T>` class.

**Program:** `Sorter` Class Definition

Program also declares the member variable `n`,
the static member function `Swap`,
and the pure virtual function `DoSort`.
Since `DoSort` is a pure virtual function,
an implementation must be given in a derived class.
Program gives the implementations
for `Sort` and `Swap`.

**Program:** `Sorter<T>` class `Swap` and `Sort` Member Function Definitions

The `Sort` function does not sort the data itself.
It is the `DoSort` routine,
which is provided by a derived class,
that does the actual sorting.
The `Sort` routine merely sets things up for `DoSort`.

The `Sort` function takes a reference
to an `Array<T>` instance
which allows arbitrary array subscript ranges.
E.g., the first element of an array `a`
is the one at position `a[a.Base()]`.
However, in most cases it is easier
to write the sorting algorithm for a fixed lower bound of, say, zero,
For this reason, the `Sort` function sets the array base to zero.
Of course, the caller does not expect the array base to be changed.
Therefore, the `Sort` routine restores the original
array base before it returns.

The `Swap` function is used to implement most of the sorting
algorithms presented in this chapter.
The swap function takes two references to objects of some type `T`,
and exchanges the contents of these two objects.
The exchange is done as a sequence of three assignments.
Therefore, if a `T` instance can be assigned in constant time,
the `Swap` routine runs in constant time.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.