Download demo project - 15 Kb
Download source files - 2 Kb
This is an updated version - thanks to Donald R. Kichline.

## Motivation

From time to time, I need to sort arrays containing custom data types,
structures, or simple data types provided by C++. Because I use MFC and CArray,
I was looking for a nice solution. Here it is - my CQArray template class that
includes a quick sort method. In the first version I just provided array
template with quick sort method implemented. This is updated version, with
function template too. Good news, this release is faster than first one, and of
course, faster than `qsort()`

function. Second one is, I extended it by
`QuickSort()`

function template.

## Description of solution

Sorry, I don't describe the quick sort algorithm. You should be aware that
the quick sort algorithm is the fastest sorting algorithm. It is recursive, and
based on partitioning the input array by some element.

In this release is new function template - `QuickSort()`

. This template is
also used by `CQArray`

template. Therefore, now it is possible to sort any array,
not just a `CArray`

like array.

I kept it as simple as possible. With `CQArray`

, you can construct any
template class. After construction, by simply calling `QuickSort()`

, you will
sort the array. The function template `QuickSort()`

works the same way.

## Description of CQArray template

CQArray declaration and implementation:

template <class T, class PT> class CQArray : public CArray <T, PT>
{
public:
void QuickSort(BOOL bAscending = TRUE);
};
template <class T, class TP> void CQArray<T,TP>::QuickSort(BOOL bAscending)
{
if (GetSize() > 1)
{
::QuickSort(GetData(),GetSize(),bAscending);
}
}

Above you can see whole CQArray template. One and only method is
`QuickSort()`

, parameter bAscending means sorting ascending (if TRUE), or
descending. Note, this method calls `QuickSort(`

) function.

## Description of function template QuickSort

Declaration of QuickSort() function:

template <class T> BOOL QuickSort(T *pArr, int iSize, BOOL bAscending = TRUE);

Implementation is quite longer, please see to sources. First parameter is
address of array to sort. Second one is size of this array. Last one has same
meaning like `CQArray::QuickSort()`

parameter. Function returns TRUE if success,
otherwise it returns FALSE. However, only one error can occur - bad
parameters.

## Usage

Usage of `CQArray`

is similar to a `CArray`

:

...
CQArray <int, int &> intArr;
...
...
intArr.QuickSort();
...

Usage of `QuickSort()`

function:

int data[100];
QuickSort(data,100);

Note, if you want to sort a custom type, you'll need to overload the
operators '<' and '>'.

## Demo project

I provide simple demo project. You can see usage of template class and
function and compare performance of `QuickSort(`

) function with `qsort()`

function.

You can set array size, type of elements in array and direction of sorted
array. My 'user defined type' is simple structure.

### Comparision with qsort

As you can see on previous picture, in demo program you
can sort array in three ways. First one is with CQArray template, second
one `QuickSort()`

function template and last one is` qsort()`

function. Time
bellow is in seconds. My templates are faster than `qsort()`

function.
It is not every time seven times faster, sometimes it is more or less. It
is based on array size, a larger array produces a better ratio.