# Quick Sort Algorithm Comparing Any Data Type

General:

I wanted a way to sort any column in a CListCtrl, so I came to CodeGuru.com to get some ideas (and possible a solution) to solve my problem. Unfortunately, I had troubles understanding and getting some of the sorting examples to function. So did what any good programmer does. I took some code and attempted to improve upon it.

What I have come up with is my solution for using the quick sort alogrithm so that you can sort by any column of any data type.

## Acknowledgements:

Source code:

I am only showing the relavent code to add into your derived CListCtrl class header and implementation files.

```
enum ListCompareType {  ELCT_INTEGER = 0,
ELCT_DOUBLE,
ELCT_STRING_CASE,
ELCT_STRING_NOCASE };
enum ListOperatorType { ELOT_LT = 0,    //  <   less than
ELOT_GT,  //  >   greater than
ELOT_LTE, //  <=  less than or equal
ELOT_GTE, //  >=  greather than or equal
ELOT_EQ}; //  ==  equal
class CMyListCtrl  : public CListCtrl
{
//////////////////////////////////////////////////////////////////////
// Constructors and Deconstructors
//////////////////////////////////////////////////////////////////////
..
//////////////////////////////////////////////////////////////////////
// Operations
//////////////////////////////////////////////////////////////////////
public:
BOOL SwapRow(int nRow1, int nRow2);
int GetColumnCount() const;
protected:
void QuickSort(int p, int r);
int Partition(int p, int r);

//////////////////////////////////////////////////////////////////////
// Overridables
//////////////////////////////////////////////////////////////////////
public:
virtual void Sort();
virtual void Sort(int nColumn, BOOL bAscending, ListCompareType
nCompareAs);
protected:
virtual BOOL CompareBy(CString str1, CString str2, ListOperatorType
op);
//////////////////////////////////////////////////////////////////////
// Message Maps
//////////////////////////////////////////////////////////////////////
protected:
//{{AFX_MSG(OGPuiODListCtrl)
afx_msg void OnHeaderClicked(NMHDR* pNMHDR, LRESULT* pResult);
//}}AFX_MSG
//////////////////////////////////////////////////////////////////////
// Attributes
//////////////////////////////////////////////////////////////////////
protected:
//sorting attributes
int m_nSortedColumn;
BOOL m_bSortAscending;
ListCompareType m_nCompareAs;
};
CMyListCtrl::CMyListCtrl() : CListCtrl(),
m_nSortedColumn(-1),
m_bSortAscending(TRUE),
m_nCompareAs(ELCT_STRING_CASE)
{
}
//////////////////////////////////////////////////////////////////////
// Message Maps
//////////////////////////////////////////////////////////////////////
BEGIN_MESSAGE_MAP(OGPuiODListCtrl, CListCtrl)
//{{AFX_MSG_MAP(OGPuiODListCtrl)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
//////////////////////////////////////////////////////////////////////
message.
//        LRESULT - Contains the result from the message
// Action:     Sort the column that the user clicks on. If it is not
//        the same column as the last sorting then sorting ascending.
//        If is the same column then toggle the sorting style. The
//        list only recieves this message if the "no sort header" is
//        NOT checked in the resource.
// Returns:    Nothing.
//////////////////////////////////////////////////////////////////////
{
HD_NOTIFY *phdNotify = (HD_NOTIFY *)pNMHDR;
if (phdNotify->iButton == 0)
{
m_bSortAscending = (phdNotify->iItem == m_nSortedColumn) ?
!m_bSortAscending : TRUE;
m_nSortedColumn = phdNotify->iItem;
Sort();
}
*pResult = 0;
}
//////////////////////////////////////////////////////////////////////
// Sort()
// Parameters:  None.
// Action:      This function is called when the user clicks on a column
//              header. Derived classes should override this function
//              if they want to change the m_nCompareAs based on the
//              the column that was selected.
// Returns:     Nothing.
//////////////////////////////////////////////////////////////////////
void OGPuiODListCtrl::Sort()
{
Sort(m_nSortedColumn, m_bSortAscending, m_nCompareAs);
}
//////////////////////////////////////////////////////////////////////
// Sort()
// Parameters:  nColumn - column to sort by
//              bAscending - TRUE ascending sort, FALSE descending
//              nCompareAs - How to compare the values as
// Action:      Set all the sorting attributes then do a quick sort
//              on the whole list. Derived class may want to override
//              this if they want to use a different sort algorithm or
//              want to use a different range
// Returns:     Nothing.
//////////////////////////////////////////////////////////////////////
void OGPuiODListCtrl::Sort(int nColumn, BOOL bAscending, ListCompareType
nCompareAs)
{
m_nSortedColumn = nColumn;
m_bSortAscending = bAscending;
m_nCompareAs = nCompareAs;
QuickSort(0, GetItemCount() - 1);
}
//////////////////////////////////////////////////////////////////////
// QuickSort()
// Parameters:  p - start position, usually index 0
//              q - end position, usually last index
// Action:      Standard quick sort algorthim
// Returns:     Nothing.
//////////////////////////////////////////////////////////////////////
void OGPuiODListCtrl::QuickSort(int p, int r)
{
if (p < r)
{
int q = Partition(p, r);
QuickSort(p, q);
QuickSort(q + 1, r);
}
}
//////////////////////////////////////////////////////////////////////
// Partition()
// Parameters:  p - start position
//              q - end position
// Action:      Partition of the array in the quick sort algorithm
// Returns:     Nothing.
////////////////
int CMyListCtrl::Partition(int p, int r)
{
CString tmp;
CString x = GetItemText( p, m_nSortedColumn);
int i = p - 1;
int j = r + 1;

while (i < j)
{
do
{
j--;
tmp = GetItemText(j,  m_nSortedColumn);
} while (CompareBy(tmp, x, m_bSortAscending ? ELOT_GT :
ELOT_LT));

do
{
i++;
tmp = GetItemText(i, m_nSortedColumn);
} while (CompareBy(tmp, x, m_bSortAscending ? ELOT_LT :
ELOT_GT));

if (i < j)
{
SwapRow(i, j);
}
}

return j;
}

//////////////////////////////////////////////////////////////////////
// CompareBy()
// Parameters:  str1 - string 1 (left operand)
//              str2 - string 2 (right operand)
//              op - operator type
// Action:      Convert strings to new data type based on m_nCompareAs'
//              value. Compare the strings using the operator.
// Returns:     The result of (str1 op str2)
//////////////////////////////////////////////////////////////////////
BOOL CMyListCtrl::CompareBy(CString str1, CString str2, ListOperatorType
op)
{
BOOL bReturn = FALSE;

switch (m_nCompareAs)
{
case ELCT_INTEGER:
{
int val1 = atoi(str1);
int val2 = atoi(str2);

if (op == ELOT_LT)
bReturn =  (val1 < val2);
else if (op == ELOT_GT)
bReturn =  (val1 > val2);
else if (op == ELOT_LTE)
bReturn =  (val1 <= val2);
else if (op == ELOT_GTE)
bReturn =  (val1 >= val2);
else
bReturn =  (val1 == val2);
break;
}
case ELCT_DOUBLE:
{
double val1 = atof(str1);
double val2 = atof(str2);

if (op == ELOT_LT)
bReturn =  (val1 < val2);
else if (op == ELOT_GT)
bReturn =  (val1 > val2);
else if (op == ELOT_LTE)
bReturn =  (val1 <= val2);
else if (op == ELOT_GTE)
bReturn =  (val1 >= val2);
else
bReturn =  (val1 == val2);
break;
}
case ELCT_STRING_NOCASE:
{
str1.MakeUpper();
str2.MakeUpper();
}
case ELCT_STRING_CASE:
default:
{
if (op == ELOT_LT)
bReturn =  (str1 < str2);
else if (op == ELOT_GT)
bReturn =  (str1 > str2);
else if (op == ELOT_LTE)
bReturn =  (str1 <= str2);
else if (op == ELOT_GTE)
bReturn =  (str1 >= str2);
else
bReturn =  (str1 == str2);
break;
}
}

return bReturn;
}

//////////////////////////////////////////////////////////////////////
// GetColumnCount()
// Parameters:  None.
// Action:
// Returns:     The number of columns in the list control
//////////////////////////////////////////////////////////////////////
int CMyListCtrl::GetColumnCount() const
{

//Return the number of items in it (i.e. the number of columns)
}

//////////////////////////////////////////////////////////////////////
// SwapRow()
// Parameters:  nRow1 - row index (zero based)
//              nRow2 - row index (zero based)
// Action:      Swap nRow1 with nRow2
// Returns:     TRUE if successful, else FALSE
//////////////////////////////////////////////////////////////////////
BOOL CMyListCtrl::SwapRow(int nRow1, int nRow2)
{
BOOL bOk = FALSE;

int nMaxRows = GetItemCount();

if ((nRow1 >= 0) && (nRow1 < nMaxRows) &&
(nRow2 >= 0) && (nRow2 < nMaxRows) &&
(nRow1 != nRow2))
{
int nMaxColumns = GetColumnCount();

//swap rows
LV_ITEM lvItem1, lvItem2;

//hold all text for a single row
CStringArray rowText;
rowText.SetSize(nMaxColumns);

//save all the text in row
for(int i = 0; i < nMaxColumns; i++)
{
rowText[i] = GetItemText(nRow1, i);
}

//setup parameters to get item data
lvItem1.mask = LVIF_IMAGE | LVIF_PARAM | LVIF_STATE;
lvItem1.iItem = nRow1;
lvItem1.iSubItem = 0;
lvItem1.stateMask = LVIS_CUT | LVIS_DROPHILITED |
LVIS_FOCUSED | LVIS_SELECTED |
lvItem2 = lvItem1;
lvItem2.iItem = nRow2;

//get item data
GetItem(&lvItem1);
GetItem(&lvItem2);

//set the text for the lo (left)
for(i = 0; i < nMaxColumns; i++)
{
SetItemText(nRow1, i, GetItemText(nRow2, i));
}

lvItem2.iItem = nRow1;
SetItem(&lvItem2);

for(i = 0; i < nMaxColumns; i++)
{
SetItemText(nRow2, i, rowText[i]);
}

lvItem1.iItem = nRow2;
SetItem(&lvItem1);
}

return bOk;
}
```

• #### Uh, no.

Posted by Legacy on 08/08/2003 12:00am

Originally posted by: HlpMe

Uh, no. You should rethink what is means to be a "good programmer".

Anyway, this is much better:
http://www.codeguru.com/listview/sort_on_col_click.shtml

• #### what is OGPuiODListCtrl ?

Posted by Legacy on 04/28/2003 12:00am

Originally posted by: hotdog

The are many errors when comping the file.
such as:
F:\Project\VC\new\HFTP\ctrlext.cpp(32) : error C2653: 'OGPuiODListCtrl' : is not a class or namespace name

• #### Thanks!

Posted by Legacy on 09/25/2001 12:00am

Originally posted by: Jungle Lee

```Your perfect code ought to be contained in the MS CListCtrl class.
```

• #### Sorting Image items

Posted by Legacy on 12/29/1999 12:00am

Originally posted by: Tony D. Abel

```I added the following code to handle Images.

/******************************************************
**
**	This function will partition the CListCtrl array.
**
**  TDA
*/

int CSortListCtrl::Partition( int iStartPosition, int iEndPosition )
{

CString TempStr;
CString ItemStr = GetItemText( iStartPosition,                                         m_iSortedColumn );

LVITEM TempItem;
LVITEM CurrentItem;

// clear structs
memset( &TempItem, 0, sizeof( LVITEM ) );
memset( &CurrentItem, 0, sizeof( LVITEM ) );

// setup parameters to set image data
CurrentItem.iImage	= I_IMAGECALLBACK;
CurrentItem.iItem	= iStartPosition;
GetItem( &CurrentItem );

int iSortPositionStart	= iStartPosition - 1;
int iSortPositionStop	= iEndPosition + 1;

while( iSortPositionStart < iSortPositionStop )
{

if( m_iSortedColumn == ELECT_IMAGE )
{
do
{
iSortPositionStop--;

TempItem.iImage	= I_IMAGECALLBACK;
TempItem.iItem	= iSortPositionStop;
GetItem( &TempItem );

}while( CompareBy( TempItem, CurrentItem, m_bSortAscending
? ELECTOPTYPE_GT : ELECTOPTYPE_LT ) );

do
{
iSortPositionStart++;

TempItem.iImage	= I_IMAGECALLBACK;
TempItem.iItem	= iStartPosition;
GetItem( &TempItem );

}while( CompareBy( TempItem, CurrentItem, m_bSortAscending
? ELECTOPTYPE_GT : ELECTOPTYPE_LT ) );
}
else
{
do
{
iSortPositionStop--;
TempStr = GetItemText( iSortPositionStop,
m_iSortedColumn );

}while( CompareBy( TempStr, ItemStr, m_bSortAscending
? ELECTOPTYPE_GT : ELECTOPTYPE_LT ) );

do
{
iSortPositionStart++;
TempStr = GetItemText( iSortPositionStart,
m_iSortedColumn );

}while( CompareBy( TempStr, ItemStr, m_bSortAscending
? ELECTOPTYPE_LT : ELECTOPTYPE_GT ) );
}

if( iSortPositionStart < iSortPositionStop )
SwapRow( iSortPositionStart, iSortPositionStop );

}

return iSortPositionStop;
}

Overload the CompareBy() function. A function template will also work nicely.

/******************************************************
**
**	This function will compare the TempItem image and
**	CurrentItem image the partition function sends down.
**
**  TDA
*/

BOOL CSortListCtrl::CompareBy(  const LVITEM& TempItem,
const LVITEM& CurrentItem,
LISTOPERATORTYPEenum kOperatorType )
{

BOOL bReturn = FALSE;

switch( m_kCompareAs )
{
case ELECT_IMAGE:
{
int iIntVal1 = TempItem.iImage;
int iIntVal2 = CurrentItem.iImage;

if( kOperatorType == ELECTOPTYPE_LT )
{
bReturn = ( iIntVal1 < iIntVal2 );
break;
}
else if( kOperatorType == ELECTOPTYPE_GT )
{
bReturn = ( iIntVal1 > iIntVal2 );
break;
}
else if( kOperatorType == ELECTOPTYPE_LTE )
{
bReturn = ( iIntVal1 <= iIntVal2 );
break;
}
else if( kOperatorType == ELECTOPTYPE_GTE )
{
bReturn = ( iIntVal1 >= iIntVal2 );
break;
}
else
{
bReturn = ( iIntVal1 == iIntVal2 );
break;
}
}

// Should never get here
default:
ASSERT(0);
}

return bReturn;
}

```

• #### Two small corrections

Posted by Legacy on 10/07/1999 12:00am

Originally posted by: Shekar Venkatappa

Method ::SwapRows(...)

This method does not return TRUE on success. Variable bOk is updated to do so.

Platform: NT
In Message mapping

works better( for sure) than

• You must have javascript enabled in order to post comments.

## Top White Papers and Webcasts

• IT is in a continual battle to simplify and "do more with the same, or less," but the continued growth of data has drastically increased the complexity and cost of deploying, managing, and processing data using traditional IT infrastructure components. One key component — enterprise storage and the underlying software that controls the storage — is fortunately evolving nearly as fast as the data is growing. This ESG Lab Review documents the results of hands-on testing of the WekaIO Matrix …

• The need for swift digital transformation is leading to broader utilization of hybrid IT infrastructure by financial services organizations. Banks, investment firms and insurance companies continue to leverage a mix of premises-based and cloud–based technology infrastructure to dramatically improve operational performance, and are networking distributed resources to create business value. Read this white paper to learn why having the right network resources in place is key to benefiting from the cost, …