Environment: Visual C++ 5.0 & SP3, Windows NT 4.0 & SP5, Unicode, MBCS
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/* = TRUE*/)
{
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;
...
// do some stuff to fill array
...
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.
History
Date Updated: 12 June, 1999