Program declares
the abstract `QuickSorter<T>` class template.
The `QuickSorter` class declares two versions
of the `DoSort` routine,
as well as the pure virtual function `SelectPivot`.
Since `SelectPivot` is a pure virtual function,
its implementation is given in a derived class.

**Program:** `QuickSorter` Class Definition

Program defines the `DoSort` routine
of the `QuickSorter<T>` class
that takes three arguments--a reference to the array to be sorted, `array`,
and two integers, `left` and `right`,
which denote left and right ends, respectively,
of the sequence of the array to be sorted.
I.e., this `DoSort` routine sorts

.

**Program:** `QuickSorter<T>` class Recursive `DoSort` Member Function Definition

As discussed above, the `QuickSorter` only sorts sequences
whose length exceeds the *cut-off* value.
Since the implementation shown only works correctly
when the number of elements in
the sequence to be sorted is three or more,
the *cut-off* value of two is used (line 5).

The algorithm begins by calling the function `SelectPivot` which
chooses one of the elements to be the pivot (line 7).
The implementation of `SelectPivot` is discussed below.
All that we require here is that the value *p* returned by `SelectPivot`
satisfies .
Having selected an element to be the pivot,
we *hide* the pivot by swapping it with the right-most element
of the sequence (line 8).
The pivot is *hidden* in order
to get it out of the way of the next step.

The next step partitions the remaining elements into two sequences--one comprised of values less than or equal to the pivot,
the other comprised of values greater than or equal to the pivot.
The partitioning is done using two array indices, `i` and `j`.
The first, `i`, starts at the left end and moves to the right;
the second, `j`, starts at the right end and moves to the left.

The variable `i` is increased
as long as `array[i]` is less than the pivot (line 14).
Then the variable `j` is decreased
as long as `array[j]` is greater than the pivot (line 15).
When `i` and `j` meet,
the partitioning is done (line 16).
Otherwise,
but .
This situation is remedied
by swapping `array[i]` and `array[j]` (line 17).

When the partitioning loop terminates,
the pivot is still in `array[right]`;
the value in `array[i]` is greater than or equal to the pivot;
everything to the left is less than or equal to the pivot; and
everything to the right is greater than or equal to the pivot.
We can now put the pivot in its proper place
by swapping it with `array[i]` (lines 19-20).
This is called *restoring* the pivot.
With the pivot in its final resting place,
all we need to do is sort the subsequences
on either side of the pivot (lines 21-24).

Program defines the main `DoSort` routine
of the `QuickSorter` class.
The main `DoSort` acts as the front end
to the recursive `DoSort` given in Program .
This routine takes as its lone argument a reference to the array to be sorted.
It calls the recursive `DoSort` routine
with `left` set to zero
and `right` set to *n*-1,
where *n* is the length of the array to be sorted.
Finally, it uses a `StraightInsertionSorter<T>`
to finish sorting the list.

**Program:** `QuickSorter<T>` Class Main `DoSort` Member Function Definition

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