|
/********************************************************************************************
* MOD-NAME : QArray.h
* LONG-NAME : QuickSort algorithm enabled CArray
*
* AUTHOR : Martin Ziacek, Martin.Ziacek@swh.sk, http://www.swh.sk
* COPYRIGHT : 1999 Martin Ziacek
* DEPARTMENT : SWH s.r.o
* TELEPHONE : +421 7 59684147
* CREATION-DATE : 1.5.1999 8:27:23
* SP-NO :
* FUNCTION : Implementation of QuickSort algorithm as template for array class
* and template for simple function QuickSort()
*
*********************************************************************************************/
#ifndef _QuickSortCArrayAndFunctionTemplate_7EB8E364_1A47_11d3_AFD1_0080ADB99E81_
#define _QuickSortCArrayAndFunctionTemplate_7EB8E364_1A47_11d3_AFD1_0080ADB99E81_
//////////////////////////////////////////////////////////////////////////
// QuickSort functions
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
// QuickSortRecursive - core of algorithm, do not call it, use QuickSort,
// see below
template <class T> void QuickSortRecursive(T *pArr, int d, int h, BOOL bAscending)
{
int i,j;
T str;
i = h;
j = d;
str = pArr[((int) ((d+h) / 2))];
do {
if (bAscending) {
while (pArr[j] < str) j++;
while (pArr[i] > str) i--;
} else {
while (pArr[j] > str) j++;
while (pArr[i] < str) i--;
}
if ( i >= j ) {
if ( i != j ) {
T zal;
zal = pArr[i];
pArr[i] = pArr[j];
pArr[j] = zal;
}
i--;
j++;
}
} while (j <= i);
if (d < i) QuickSortRecursive(pArr,d,i,bAscending);
if (j < h) QuickSortRecursive(pArr,j,h,bAscending);
}
//////////////////////////////////////////////////////////////////////////
// QuickSort - entry to algorithm
//
// T *pArr ... pointer of array to sort
// int iSize ... size of array T *pArr
// BOOL bAscending ... if bAscending == TRUE, then sort ascending,
// otherwise descending
//
// return TRUE if no error, error can be bad parameter, call ::GetLastError()
// if QuickSort returned FALSE
template <class T> BOOL QuickSort(T *pArr, int iSize, BOOL bAscending = TRUE)
{
BOOL rc = TRUE;
if (iSize > 1) {
try {
int low = 0,
high = iSize - 1;
QuickSortRecursive(pArr,low,high,bAscending);
} catch (...) {
::SetLastError(ERROR_INVALID_PARAMETER);
rc = FALSE;
}
} else {
::SetLastError(ERROR_INVALID_PARAMETER);
rc = FALSE;
}
return rc;
}
//////////////////////////////////////////////////////////////////////////
// CQArray
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
// CQArray declaration
template <class T, class PT> class CQArray : public CArray <T, PT>
{
public:
void QuickSort(BOOL bAscending = TRUE);
};
//////////////////////////////////////////////////////////////////////////
// CQArray implementation
//////////////////////////////////////////////////////////////////////////
// QuickSort - entry to algorithm
//
// BOOL bAscending ... if bAscending == TRUE, then sort ascending,
// otherwise descending
//
template <class T, class TP> void CQArray<T,TP>::QuickSort(BOOL bAscending/* = TRUE*/)
{
if (GetSize() > 1) {
::QuickSort(GetData(),GetSize(),bAscending);
}
}
#endif /* _QuickSortCArrayAndFunctionTemplate_7EB8E364_1A47_11d3_AFD1_0080ADB99E81_ */
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.